New prune rules for similarity search
Tao Ban, Youki Kadobayashi · 2007
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 embedding space and are applicable to positive semi-definite metrics. The proposed prune rules are cheap both in computation and storage cost and can be readily incorporated with available metric indexing structures. In the simulation experiments, the Geometric Near-neighbor Access Tree with the proposed prune rules shows preferable pruning ability especially on large datasets with high dimensions.