Abstract

In this chapter we consider the following problem: given a set P of points in a high-dimensional space, construct a data structure which given any query point q finds the point in P closest to q. This problem, called nearest neighbor search ¹ , is of significant importance to several areas of computer science, including pattern recognition, searching in multimedia data, vector compression [GG91], computational statistics [DW82], and data mining. Many of these applications involve data sets which are very large (e.g., a database containing Web documents could contain over one billion documents). Moreover, the dimensionality of the points is usually large as well (e.g., in the order of a few hundred). Therefore, it is crucial to design algorithms which scale well with the database size as well as with the dimension.