4
$\begingroup$

I'm looking for a good way to partition a large, fairly high-dimensional dataset in order to perform fast kNN searches not just in the full $N$-dimensional space, but also in lower-dimensional subspaces of that space.

For example, consider a point $p$ in a 3-dimensional space, $\{X, Y, Z\}$. On the one hand, I want to find its nearest neighbour $i$:

$$ \DeclareMathOperator*{\argmin}{argmin} \argmin_{i} max{\{\| x_p - x_i \|, \|y_p - y_i\|, \|z_p - z_i\| }\} $$

But I also want to be able to efficiently find the nearest neighbour $j$ in the $\{X, Y\}$ subspace, i.e.:

$$ \DeclareMathOperator*{\argmin}{argmin} \argmin_{j} max{\{\| x_p - x_j \|, \|y_p - y_j\|}\} $$

In my case there are usually many more than 3 dimensions, and I want to be able to find the $k^{th}$ nearest neighbour distances considering multiple different subsets of those dimensions.

To give you some more background, my goal is to use kNN distances to estimate conditional mutual information from continuous data without having to discretize it and compute histograms.

What would be an appropriate way to partition my data?

Some more information:

  • My dimensionality will vary between about 3 and 30
  • The number of datapoints will probably be on the order of about 200000
Improve this question
$\endgroup$
2
  • $\begingroup$ My first instinct for multi-dimensional k-NN searches would be to construct a k-d tree for your data for the dimensions in which you want to perform the search, but I'm not sure if you could use this approach without reconstructing the tree for each set of dimensions that you were interested in. Out of curiousity, how large is the dataset and how many dimensions do you have? This approach would only be useful if $N >> 2^k$ (N = number of points, k=num dimensions). k-d trees can be constructed in O(N logN) time, so without knowing more about your data this is the approach I'd recommend. $\endgroup$
    – Tyler Olsen
    May 19, 2014 at 21:06
  • $\begingroup$ @TylerOlsen I've updated my question with a bit more info about my dataset. The dimensionality of my data will vary, and in some cases I expect $N << 2^{k}$. $\endgroup$
    – ali_m
    May 20, 2014 at 9:34

3 Answers 3

Reset to default
1
$\begingroup$

Since your dimension is only 3 for the moment, I guess a naive approach would be to create separate trees for each subspace.

I would recommend you to use Flann (http://www.cs.ubc.ca/research/flann/) as it is very well implemented and reported to be quite fast for the datasets of your concern (http://www.cs.ubc.ca/research/flann/uploads/FLANN/flann_visapp09.pdf , http://www.cs.ubc.ca/research/flann/uploads/FLANN/binary_matching_crv2012.pdf).

Flann is implemented in a parallel fashion (it even supports MPI), but you could tweak it to retrieve parallel queries for each subspace, which will nevertheless reduce the computation time significantly. So there are already options for you to try out.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sorry I neglected this answer for a long time. For the time being I'm basically doing something similar to what you proposed, i.e. by creating separate trees for each subspace. However, this really doesn't work well for >10 dimensions. I'm hoping that a non-hierarchical method might do better for very high-dimensional datasets - I've been trying to cobble something together using KGraph, but my C++ coding skills aren't that great... $\endgroup$
    – ali_m
    Nov 11, 2014 at 3:27
0
$\begingroup$

As the subspace is simply defined as a subset of dimensions, it may be possible to use a projection of your data in a reduced dimensionality (1) and a eucliedean distance method to partition it. I had some good results with SVD and kmeans in data problem similar to yours. Taking

$ A = U \Sigma V^{T} $

$ A_{k} = \Sigma_{k}V_{k}^{T} $

and applying kmeans to $A_{k}$ matrix.

Ref

  1. infolab.stanford.edu/~ullman/mmds/ch11.pdf
Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm not interested in doing dimensionality reduction per se. Rather, for a particular point I need to find points that are nearest neighbors of that point according to their distances within a specific subset of the dimensions in my dataset. $\endgroup$
    – ali_m
    Nov 11, 2014 at 3:21
0
$\begingroup$

The Spatial library allows to define a custom Metric, which can ignore some specific dimensions, or more generally project the points onto the specified subspace before calculating the difference.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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