3
$\begingroup$

I have a very skewed, 10-dimensional data set. I need approximate nearest neighbours for my use case and I was looking into Locality senstive hashing. However after scaling and randomly generating hyperplanes through the origin and coding the data points like that I got very skewed buckets because of the nature of the data. After thinking about it for a bit I came up with an idea to take random points from the data and use these as cluster centers for the hash. Every point will be mapped to the ID of the closest randomly picked center. My question is if the expected size of the bucket of a specific point is the same for all the other data points. I think that is the case but others say it shouldn't. My rationale is that more dense areas have more randomly decided cluster points while outliers will not be picked very often. I can't find anything about this in literature.

Edit: I did run some tests and they seem to support my hypothesis somewhat but variance is relatively high because there is a high dependence between sizes of clusters (data points wise)

Improve this question
$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

If you want to compute (approximate) nearest neighbors in 10-dimensional data, I would recommend using a k-d tree. A k-d tree can handle skewed/non-uniform data sets and adjusts naturally to that.

More generally, you could look at data structures for nearest neighbor search, including binary space partitioning trees and metric trees. But k-d trees are a good starting point, and they support both exact nearest neighbor queries as well as approximate nearest neighbor queries.

I would expect this to work better than locality-sensitive hashing (LSH).

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

It's not a proof, but I just found a paper that claims this empirically, and also had the exact same idea for the same problem.

http://web.kaist.ac.kr/~kyomin/2012BigLearn.pdf

If someone does happen to have a proof for this, I'm still very interested though.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The link broken. $\endgroup$
    – horaceT
    Commented Feb 3, 2017 at 2:43
0
$\begingroup$

A counterexample in dimension 1: take three points: 1, 3 and 4 on the x axis. When you sample two points at random, the expected sizes of the bucket each point falls in are 4/3, 2 and 5/3 respectively.

But maybe your hypothesis is "approximately true" for data from some good enough distribution (for example, uniformly random points on a sphere).

Improve this answer
$\endgroup$
1
  • $\begingroup$ That is a good point, thank you. My intuition behind this is that this is mostly an issue around the borders (not just of the whole data set but also of dense parts of the space). I'll just implement it on my set and see how big the buckets become. Thanks $\endgroup$
    – Jan van der Vegt
    Commented Jan 8, 2016 at 12:35

Your Answer

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

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