New Prune Rules for Similarity Search

T. Ban and Y. Kadobayashi (Japan)


Computing, metric space, similarity search, range search, prune rule.


In this paper, we present a novel class of prune rules for metric indexing algorithms. The rules are derived from the geometrical properties in the low dimensional embed ding space and are applicable to positive semi-deļ¬nite met rics. The proposed prune rules are cheap both in computa tion and storage cost and can be readily incorporated with available metric indexing structures. In the simulation ex periments, the Geometric Near-neighbor Access Tree with the proposed prune rules shows preferable pruning ability especially on large datasets with high dimensions.

Important Links:

Go Back