Expectation number of points in initial clustering for LSH 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)
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).