1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bort Aug 18 '17 at 11:22
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.