Updated 28 Jun 2020
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).
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)
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.
Bryce Henson (2021). fast_search_histogram (https://github.com/brycehenson/fast_search_histogram), GitHub. Retrieved .
Hi Michal Kvasnicka, Yes! I have been working on using these methods to speed up histcn(https://www.mathworks.com/matlabcentral/fileexchange/23897-n-dimensional-histogram). You can see my progress here https://github.com/brycehenson/fast_search_histogram/tree/dev/dev/ check out the histcn_search folder for an implementation of the bin search algorithm (for sparse N-d histograms). The algorithm provides a speedup if you just want a list of the bin indexes( for each dimension) for each count. Unfortunately turning this into an n-d array with the inbuilt accumarray function (https://www.mathworks.com/help/matlab/ref/accumarray.html) ends up removing all the speed advantage which is a bit disappointing!
Any possibility to generalize for n-d case?
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!