Data structure for efficient high dimensional histogramming

What data structure (or C++ library implementing it) is most suitable for efficient high dimensional histogramming?

I have an application where I need to compute something similar to a histogram in a high dimensional space ($d=10..20$). Even with a large linear bin size, there would be too many bins in total. However, I know in advance that only a tiny fraction of the bins will hold a non-zero value after finishing the computation (though it is very hard to estimate which).

Thus, I need a "sparse array" which supports very fast indexing and fast updates. There are many possible representations for sparse arrays.

To save me a lot of benchmarking, I was wondering which one (or better: which particular C++ implementation) will perform "the best" for this task.

• If you are really interested in densities for spaces d>3, histograms are quite a bad choice. You already saw the curse of dimensionality in the number of bins. It applies as well to the number of data points required in a bin to be significant.
– Bort
Aug 18 '17 at 11:22

If the index for a bin is some $d$-tuple of integers $\{k_1, \ldots, k_d\}$, one approach that might work is to come up with a hash function $h$ for bin indices and use an unordered_map from the C++ standard template library. It's hard to beat a well-tuned hash table implementation for serial performance.
A hash table will work fine just for storage purposes, but it'll be inadequate if you need more sophisticated spatial queries. For example, given a non-empty bin, you might want to find the $m$ nearest non-empty bins. Conventional data structures like k-d trees or octrees do very badly on high-dimensional data. I haven't used them so I can't comment on their efficiency, but X-trees and PK-trees that are supposed to handle high-dimensional input gracefully.