A Unified Model for Similarity Searching

Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates and José Luis Marroquín

The indexing algorithms and data structures for similarity searching in metric spaces seem to emerge from a great diversity, and different approaches have been proposed and analyzed separately, often under different assumptions. Currently, the only realistic way to compare two different algorithms is to apply them to the same data set. We present a unified model for studying similarity searching algorithms, defining common complexity measures allowing comparison between different approaches.