Similarity Search in High-Dimensional Data Spaces.

This paper summarizes analytical and experimental results for the nearest neighbor similarity search problem in high-dimensional vector spaces using some kind of space-or data-partitioning scheme and formally shows that conventional approaches to the nearest neighbor problem degenerate if the dimensionality of the data space becomes large.

Abstract

This paper summarizes analytical and experimental results for the nearest neighbor similarity search problem in high-dimensional vector spaces using some kind of space- or datapartitioning scheme. Under the assumptions of uniformity and independence of data, we are able to formally show and to demonstrate that conventional approaches to the nearest neighbor problem degenerate if the dimensionality of the data space becomes large. Given the experimental results, we recommend to use scan based algorithms for nearest neighbor search whenever the dimensionality is larger than around 5. 1 Introduction An important paradigm of systems for multimedia, decision support and data mining is the need for similarity search, i.e. the need to find a small set of objects which are similar or close to a given query object. Mostly, similarity is not measured on the objects directly, but rather, on abstractions of objects termed features. In many cases, features are points in some highdimensional vector...