image thumbnail

fast_search_histogr​am

version 1.0.0 (3.47 MB) by Bryce Henson
fast 1d histogramming algorithms based on binary search. (faster than histcounts)

46 Downloads

Updated 28 Jun 2020

From GitHub

View license on GitHub

This project demonstrates superior speed to Matlab's inbuilt histcounts function and provides an adaptive function (hist_adaptive_method) that automatically picks the fastest method.

The brute force approach to histogramming is to compare each bin to each data value (or *count*) and gives a complexity **O(n·m)** where *n* is the number of data values and *m* is the number of bins. This can be improved by two algorithms.

1. **Bin Search, O(n·log(m))**: For each count do a binary search for the histogram bin that it should go into and then increment that bin. Because the bins are already ordered then there is no sorting needed. Best when m>>n (sparse histogramming).
to use:
bin_counts=hist_bin_search(data,edges)

2. **Count Search, O(m·log(n))**: For each bin edge do a binary search to find the nearest data index. Use the difference in this data index between bins to give the number of counts. Must have ordered data for the search to work, sorting first would cost **O(n·log(n))** and would make this method slower unless repeated histogramming was needed. Best when n>>m (dense histogramming) which is the more common use case. (this is the method shown in the logo)
to use:
bin_counts=hist_count_search(data,edges) (WARNING SORTED DATA REQUIRED)

I observe empirically (see /figs/scaling_comparison.png & hist_scaling_test) that there is a fairly complex dependence of which algorithm is best on the value of n and m. I have implemented a function that does a good job of picking the fastest method.

Cite As

Bryce Henson (2021). fast_search_histogram (https://github.com/brycehenson/fast_search_histogram), GitHub. Retrieved .

MATLAB Release Compatibility
Created with R2019a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
To view or report issues in this GitHub add-on, visit the GitHub Repository.
To view or report issues in this GitHub add-on, visit the GitHub Repository.