A flexible framework to ease nearest neighbor search in multidimensional data spaces

摘要

Similarity search is a very active area of research because of its usefulness in a set of modern applications, such as content-based image retrieval (CBIR), time series, spatial databases, data mining and multimedia databases in general. The usual way to do a similarity search is to map the objects to feature vectors and to model the search as a nearest neighbor query in the multidimensional space where vectors reside. The main critical issues to this process are: the distance function used to measure the proximity between vectors and the index method to accelerate the search. In this paper we propose a formal framework to perform similarity search that provides the user with a high degree of freedom in the choice of both the distance and the index structure used to organize the feature space. More specifically, we introduce a function to approximate eventually any distance function that can be used in conjunction with index structures that divide the feature space in multidimensional rectangular regions. Cases of use and experimental work are presented to demonstrate the applicability and the overhead of the framework.