Nearest neighbor search : the old, the new, and the impossible

[摘要] (cont.) Motivated by the above impossibility results, we develop a new approach to the NN problem, where the classical approaches fail. Using this approach, we give a new efficient NN algorithm for a variant of the edit distance, the Ulam distance, which achieves a double-logarithmic approximation. This is an exponential improvement over the lower bound on the approximation achievable via the previous classical approaches to this problem. Data structure lower bounds. To complement our algorithms, we prove lower bounds on NN data structures for the Euclidean distance and for the mysterious but important case of the ... distance. In both cases, our lower bounds are the first ones to hold in the same computational model as the respective upper bounds. Furthermore, for both problems, our lower bounds are optimal in the considered models. External applications. Although our main focus is on the NN problem, our techniques naturally extend to related problems. We give such applications for each of our algorithmic tools. For example, we give an algorithm for computing the edit distance between two strings of length d in near-linear time. Our algorithm achieves approximation 20 ..., improving over the previous bound of ... . We note that this problem has a classical exact algorithm based on dynamic programming, running in quadratic time.

[发布机构] Massachusetts Institute of Technology