Data structure for efficient high dimensional histogramming

Question

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.

Answer 1

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.

You will of course need a good hash function. The easy way to represent the bin index is to use a std::array<size_t, d>; unfortunately there's no built-in hash function for arrays, so you'll have to specialize std::hash for your use case. You can combine the hashes of two numbers m and n by computing p * hash(m) + hash(n) where p is a large prime number. Applying this iteratively to the whole array should give you a good hash function. You could also use boost::hash_combine or boost::hash_range, but boost is a big dependency. In any case, you might want to do some amount of benchmarking on realistic input to make sure that there aren't lots of hash collisions.

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.