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