Exact L∞-Nearest-Neighbor Search in High Dimensions

Abstract

In this thesis we consider the nearest-neighbor problem, which is defined as follows: given a fixed set P of n data points in some metric space X, build a data structure such that for each given query point q a data point from P closest to q can be found efficiently. The underlying metric space is usually the d-dimensional real space Rd together with one of the Lp-metrics, 1<= p <=∞. In many applications, the dimension d of the search space is quite high and can reach several hundreds or even several thousands. Therefore, running times and storage requirements exponential in d are prohibitive in these cases. Because of their exponential dependence on the dimension, all known techniques for exact nearest-neighbor problem are in fact in high dimensions not competitive with the brute-force method, which just determines the distance of q to each point in P and selects the minimum. This thesis presents algorithms for solving the high-dimensional exact nearest-neighbor problem with respect to the L∞-distance. We analyze the average-case situation when the data points are chosen independently at random under uniform distribution. The algorithms considerably improve the brute- force method, they are simple and easy to implement. In Chapter 2 we consider query algorithms that need no preprocessing and require storage only for the point set P. Their average running time is O( n+(nd / ln(n)) ). In Chapter 3 we present two strategies which speed up the search by using preprocessing. The query algorithm introduced in Section 3.1.2 requires linear storage and has an expected running time of O(n ln(d / ln( n)+1)+n). The data structure developed in Section 3.2 is based on a preprocessed partition of the data set into sequences, which are monotone with respect to some of the dimensions. The query algorithm has an expected running time of O( √dn1-1/√dln(n)) for dimensions d<(ln(n)/ln(ln(n)))2. Chapter 4 presents several generalizations, in particular to the important problem of finding the k nearest neighbors to a query point. We generalize the analysis of the considered algorithms to other "well-behaved" probability distributions. Furthermore, we develop extensions of the algorithms which work efficiently in the external-memory model of computation. In Chapter 5 we present a method which provides tradeoffs between the space complexity of the data structure and the time complexity of the query algorithm.

Das Thema dieser Dissertation ist die exakte Nächster-Nachbar-Suche. Das Problem besteht darin, effiziente Datenstrukturen und Algorithmen zu entwickeln, die zu einer festen Menge P von n Punkten aus Rd und einem beliebigen Anfragepunkt q in Rd, den oder die nächsten Nachbarn aus P zu q finden. Der Abstand wird meist in einer der Minkowski-Metriken L1, L2 ,...,L∞ definiert. Die Dimension d des Suchraumes ist in vielen Anwendungen dieses Problems sehr groß; sie liegt in der Grössenordnung von Hunderten bis Tausenden. Die bekannten Algorithmen für das exakte Nächster-Nachbar-Problem benötigen eine in d exponentielle Laufzeit oder einen in d exponentiellen Speicherplatz. Sie sind daher ineffizient für hochdimensionale Anwendungen, und können mit der brute-force Methode nicht konkurrieren, welche alle n Distanzen zu dem Anfragepunkt berechnet und den Punkt mit minimaler Distanz auswählt. In dieser Dissertation werden effiziente Algorithmen für die exakte Nächster- Nachbar-Suche in einem hochdimensionalen (Rd, L∞) Raum entwickelt. Wir untersuchen die erwartete Laufzeit unserer Algorithmen unter der Voraussetzung, dass die Punkte aus P gleichverteilt im d-dimensionalen Einheitswürfel sind. Die Algorithmen sind einfach zu implementieren und verbessern die brute-force Methode bezüglich der erwarteten Laufzeit wesentlich. Kapitel 2 stellt Methoden für das exakte Nächster-Nachbar Problem vor, die keine Vorverarbeitung und nur Speicherplatz für die n Punkte benötigen. Deren erwartete Laufzeit ist O( n+(nd / ln(n)) ). Wir entwickeln in Kapitel 3 Algorithmen, die auf der Basis einer einfachen Vorverarbeitung eine effizientere Suche ermöglichen. Der im Abschnitt 3.1.2 entwickelte Suchalgorithmus hat eine erwartete Laufzeit von O(n ln(d / ln( n)+1)+n), einen linearen Speicherbedarf und O(nd ln(n)) Vorverarbeitungszeit. Im Abschnitt 3.2 geben wir einen Suchalgorithmus an, der eine in der Vorverarbeitung berechnete Zerlegung der Punktmenge P benutzt. Die Zerlegung besteht aus Folgen von Punkten, die monoton in Rd sind. Die erwartete Laufzeit beträgt O( √dn1-1/√dln(n)) für Dimensionen d<(ln(n)/ln(ln(n)))2. Die vorgestellten Methoden und deren Laufzeitanalyse werden in Kapitel 4 für das k-Nächste-Nachbarn-Problem verallgemeinert. Außerdem werden die erwarteten Laufzeiten der entwickelten Methoden bei Zugrundelegung von anderen Wahrscheinlichkeitsverteilungen analysiert. Weiterhin betrachten wir die Anpassung der Algorithmen für die L∞-Nächster-Nachbar-Suche unter Verwendung von externen Speicher. In Kapitel 5 wird eine Methode entwickelt, die einen Tradeoff zwischen dem erwarteten Speicherbedarf der Datenstruktur und der erwarteten Laufzeit des dazugehörigen Suchalgorithmus erlaubt.