| CSE 254 Handout Nearest Neighbor Preserving Embeddings 1 Nearest Neighbor Search (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Problem 1 (The nearest neighbor problem). Given a set X ⊂ R n, build a data structure which given any query x ∈ R n, quickly reports the point x ′ in X that is (approximately) closest to x. There are efficient data structures for this problem. In particular, there exist (1 + ɛ)-approxmate nearest neighbor data structures with space complexity O(|X|/ɛ n) and query time O(n log (|X|/ɛ)) [HP01, AM02]. However, in case the dimension n is big, the complexity of these data structures is not satisfactory. Indeed, some special methods are known for the case the “intrinsic ” dimension of X is smaller than the dimension of its containing space R n. Their complexity depends on the “intrinsic ” dimension k rather than explicitly given dimension n. In contrast, Indyk and Naor do not provide any new data structure or algorithm for the nearest neighbor problem. What they do is they construct a function f that embeds set X ⊂ R n into space R k, where k corresponds to the “intrinsic ” dimension of X. This embedding somewhat preserves the property of being the closest neighbor. Consequently, in order to find the nearest neighbor of x, we may find the nearest neighbor f(x ′ ) of f(x) in f(X). The property of embedding guarantees that x ′ is a (1 + ɛ)-nearest neighbor of x. 2 Nearest Neighbor Preserving Embedding | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||