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.