Nearest neighbors in high-dimensional data?

by

I currently study such problems — classification, nearest neighbor searching — for music information retrieval.

You may be interested in Approximate Nearest Neighbor (ANN) algorithms. The idea is that you allow the algorithm to return sufficiently near neighbors (perhaps not the nearest neighbor); in doing so, you reduce complexity. You mentioned the kd-tree; that is one example. But as you said, kd-tree works poorly in high dimensions. In fact, all current indexing techniques (based on space partitioning) degrade to linear search for sufficiently high dimensions [1][2][3].

Among ANN algorithms proposed recently, perhaps the most popular is Locality-Sensitive Hashing (LSH), which maps a set of points in a high-dimensional space into a set of bins, i.e., a hash table [1][3]. But unlike traditional hashes, a locality-sensitive hash places nearby points into the same bin.

LSH has some huge advantages. First, it is simple. You just compute the hash for all points in your database, then make a hash table from them. To query, just compute the hash of the query point, then retrieve all points in the same bin from the hash table.

Second, there is a rigorous theory that supports its performance. It can be shown that the query time is sublinear in the size of the database, i.e., faster than linear search. How much faster depends upon how much approximation we can tolerate.

Finally, LSH is compatible with any Lp norm for 0 < p <= 2. Therefore, to answer your first question, you can use LSH with the Euclidean distance metric, or you can use it with the Manhattan (L1) distance metric. There are also variants for Hamming distance and cosine similarity.

A decent overview was written by Malcolm Slaney and Michael Casey for IEEE Signal Processing Magazine in 2008 [4].

LSH has been applied seemingly everywhere. You may want to give it a try.

[1] Datar, Indyk, Immorlica, Mirrokni, “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions,” 2004.

[2] Weber, Schek, Blott, “A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces,” 1998.

[3] Gionis, Indyk, Motwani, “Similarity search in high dimensions via hashing,” 1999.

[4] Slaney, Casey, “Locality-sensitive hashing for finding nearest neighbors”, 2008.

More Related Contents:

  1. Finding all possible combinations of numbers to reach a given sum
  2. Binary Search in Array
  3. Custom Weighted Scale [closed]
  4. How do I search for a number in a 2d array sorted left to right and top to bottom?
  5. How to convert floats to human-readable fractions?
  6. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  7. Why is quicksort better than mergesort?
  8. Generate an integer that is not among four billion given ones
  9. Pseudorandom Number Generator – Exponential Distribution
  10. Natural Sorting algorithm
  11. What is the fastest integer factorization algorithm?
  12. Is there an algorithm for color mixing that works like mixing real colors?
  13. Find the missing and duplicate elements in an array in linear time and constant space
  14. Function for creating color wheels [closed]
  15. Efficiently reverse the order of the words (not characters) in an array of characters
  16. A simple explanation of Naive Bayes Classification [closed]
  17. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  18. O(klogk) time algorithm to find kth smallest element from a binary heap
  19. Compute rank of a combination?
  20. Efficiently selecting a set of random elements from a linked list
  21. Skip List vs. Binary Search Tree
  22. reconstructing a tree from its preorder and postorder lists
  23. Generating shuffled range using a PRNG rather than shuffling
  24. Randomly choosing from a list with weighted probabilities
  25. Print the biggest K elements in a given heap in O(K*log(K))?
  26. Path generation for non-intersecting disc movement on a plane
  27. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  28. Find local minimum in n x n matrix in O(n) time
  29. Tournament bracket placement algorithm
  30. What is the difference between Linear search and Binary search?

Leave a Comment