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.