3
$\begingroup$

I have a 20-dimensional dataset, with a large amount of data points. I would like to have each dimension discretized into bins. Per bin, I would like to be able to access two neighbours per dimension (i.e. +1 and -1 per dimension). Basically I want to be able to easily access 2*d (where d is the dimensionality) neighbours. For lower dimensions, this would be quite easy to do using a multidimensional array (i.e. for point data[0][1][2] I would access its neighbours data[0][1][3] and data[0][1][1] for the third dimension). However, when this approach is scaled up to higher dimensions, memory becomes an issue.

What kind of data structures would be suitable to use, where the most important criterium is the quick and easy access to its +1 and -1 neighbours?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ So, just to be clear, you want easy access to your one million closest neighbors? $\endgroup$ – JeffE Jun 5 '14 at 11:48
  • $\begingroup$ No, I would like access to my 2*d closest neighbours. So in the case of d=20, this would mean 40 closest neighbours. $\endgroup$ – danielvdende Jun 5 '14 at 11:53
  • 1
    $\begingroup$ What are the non-functional requirements? For instance, why is a simple grid graph not suitable? $\endgroup$ – Raphael♦ Jun 5 '14 at 12:30
  • 1
    $\begingroup$ Did you try k-d trees? Nearest neighbour search is fairly efficient if the number of elements is on the order of $2^d$ or higher. $\endgroup$ – Pseudonym Jul 6 '14 at 6:29
  • 1
    $\begingroup$ @Pseudonym I have tried k-d trees. A number of articles have pointed out thought that k-d trees are inefficient when the dimensionality goes up to 20 or more dimensions. Moreover, when I tried k-d trees I hit recursion depth issues with my code. Another issue is of course that k-d trees search for the nearest neighbour, when in fact I already know which neighbour I want, I just want to fetch this neighbour. $\endgroup$ – danielvdende Jul 7 '14 at 7:36
2
$\begingroup$

I would suggest you to use a hierarchical K-means, or a hierarchical vocabulary tree approach. For example:

http://gecco.org.chemie.uni-frankfurt.de/hkmeans/H-k-means.pdf http://www.vlfeat.org/overview/hikm.html

CVPR Paper with application: http://www.vis.uky.edu/~stewe/publications/nister_stewenius_cvpr2006.pdf

FLANN also has some kind of hierarchical capabilities.

Improve this answer
$\endgroup$
2
$\begingroup$

You can compress sparse multi-dimensional array by using a hash table. Calculate hash key for the required coordinates and use that as O(1) look-up to the cells in the array. If the cell is empty it doesn't exist in the hash table. This is trivial to implement with std::unordered_map if you use C++.

Improve this answer
$\endgroup$
0
$\begingroup$

Use a quantization scheme, but not vector quantization as this will quantize a feature vector as a whole and you mention in the question, you need a quantization per vector coordinate (i.e per dimension)

The thresholds you will use for quantization will affectthe classification or clustering or whatever scope this is used for

For example you can try to cluster the data in each separate dimension coordinate and then this will provide the quantization and the neighbors (for this coordinate)

Possibly an implementation detail is that you would need to keep track of the feature vector index (or id or a unique identifier) in order to be able to mix the data back into feature vectors and still maintain the per-coordinate clustering

Improve this answer
$\endgroup$
2
  • $\begingroup$ Will this not lose out of a number of subspace clusters, because you are clustering within dimensions and thus losing information on this dimension? $\endgroup$ – danielvdende Jul 7 '14 at 7:37
  • $\begingroup$ @danielvdende, well this is possible, but most of the times this is a desired feature of quantization (i.e. classification/dimensionality reduction), on the other hand i have the impresion this is waht is asked for $\endgroup$ – Nikos M. Jul 7 '14 at 9:40
0
$\begingroup$

I would suggest you k-d Tree for High Dimensions Data, best use of this data structure in Nearest Neighbor Searching.

Improve this answer
$\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.