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 | 2 times |
| Pages | 215-233 |
| Volume | 41 |
| Journal name | Multimedia Tools and Applications |
| Publisher | Springer (New York, NY, USA) |
|
|
| Reference URL |
|