Similarity search in high-dimensional vector spaces
Roger Weber · CERN Document Server (European Organization for Nuclear Research) · 2001
This dissertation addresses the problem of identifying the most similar objects in a database given a set of reference objects and a set of features. It investigates the so-called Curse of Dimensionality, and presents an organization for NN-Search (Nearest Neighbour Search) optimized for high-dimensional spaces - the so-called Vector Approximation File (VA-File). The text shows the superiority of the VA-File theoretically and through experiments. The VA-File is also discussed with reference to approximate search and parallel search in a cluster of workstations. This dissertaion also provides an indexing technique that allows for interactive-time similarity search even in huge databases.