Publications

Stats

View publication

Title Improving the Space Cost of k-NN Search in Metric Spaces by Using Distance Estimators
Authors Benjamin Bustos, Gonzalo Navarro
Publication date January 2009
Abstract Similarity searching in metric spaces has a vast number of applications in several fields like multimedia databases, text retrieval, computational biology, and pattern recognition. In this context, one of the most important similarity queries is the $k$ nearest neighbor ($k$-NN) search. The standard best-first $k$-NN algorithm uses the
lower bound distance to prune objects during the search. Although optimal in several aspects, the disadvantage of this method is that its space requirements for the priority queue that stores unprocessed clusters can be linear in the database size. Most of the optimizations used in spatial access methods (e.g., pruning using MinMaxDist) cannot be applied in metric spaces, due to the lack of geometric properties. We propose a new $k$-NN algorithm that uses \emph{distance estimators}, aiming to reduce the storage requirements of the search algorithm. Experimental results with synthetic and real datasets confirm the savings in storage space of our proposed algorithm.
Downloaded 0 times
Pages 215-233
Volume 41
Journal name Multimedia Tools and Applications
Publisher Springer (New York, NY, USA)
PDF View PDF
Reference URL View reference page