Currently the way I compute histograms for data is by generating grid in $N$ dimensions (where $N$ is the dimension of the data) and searching through the $M$ data points in each dimension to see in which bin each one of them fits.This is the same as an exhaustive search and takes very long if $N$ and $M$ are large (in my case $N=6$, $M=125,000$).My question is: is there a faster way to accurately compute (or possibly estimate) the number of samples in each bin given a grid and data?Alternatively, if there is no way to estimate/compute a histogram, is there an alternative method for construct distributions that is fast for high-dimensional large datasets? I've used kernel density estimators, but they are sensitive to which type of kernel you use and depend on prior knowledge of the nature of the data to get good results. (I have no prior knowledge of the nature of the data.)
Is there a fast way to compute histograms for high-dimensional large datasets?
algorithms;statistics;data visualization;data management
Histograms are not useful for high dimensional data. The curse of dimensionality affects one quite fast. As in your case if the grid is of size 7**6, you have on average one point in one bin. Kernel density estimator are better suited as long as you keep the kernel bandwidth large enough. In my experience the top hat kernel as k-nearest neighbor yields reasonable results up to D=10, if sampling is sufficient. There is also a quite efficient algorithm for calculating k-nearest neighbors in higher dimensions, which I can recommend.Also, the kernel shape doesn't really matter so much, because you need to keep the bandwidth large enough due to lack of data. If you see a dependency on the kernel shape your bandwidth is likely too small.There are a couple of rule of thumbs how to select the bandwidth. If you calculate some other property from the probability density, in nearly all cases you are better off not computing the density at all.Edit to properly comment on the commentI am afraid you cannot capture nuanced differences in high dimensional data with histograms if you check the statistical error for each bin. Go ahead and do some simple random number experiment and check the fluctuation in each bin with your sample size. Unless you use a really small grid size like 2**6, which is pointless to begin with, you will only see noise as nuanced differences.For calculating entropies == Jensen Shannon divergences I recommend following papers which I used in my phd thesis. Article (Hnizdo2007) Hnizdo, V.; Darian, E.; Fedorowicz, A.; Demchuk, E.; Li, S. & Singh, H. Nearest-neighbor nonparametric method for estimating the configurational entropy of complex molecules. Journal of computational chemistry, J Comput Chem, 2007, 28, 655Article (Hnizdo2008) Hnizdo, V.; Tan, J.; Killian, B. & Gilson, M. Efficient calculation of configurational entropy from molecular simulations by combining the mutual-information expansion and nearest-neighbor methods Journal of computational chemistry, NIH Public Access, 2008, 29, 1605I have no idea for the earth mover distance and have never used that before though. It kinda looks like that you need the work for a phase space transformation bringing two distributions together. It seems to me that is similar to a free energy difference between the two systems given by the distributions.