Approximate similarity retrieval with M-trees

Motivated by the urgent need to improve the efficiency of similarity querie s, approximate similarity retrieval is investigated in the environment of a metric tree index called the M-tree. Three different approximation techniq ues are proposed, which show how to forsake query precision for improved pe rformance. Measures are defined that can quantify the improvements in perfo rmance efficiency and the quality of approximations. The proposed approxima tion techniques are then tested on various synthetic and real-life files. T he evidence obtained from the experiments confirms our hypothesis that a hi gh-quality approximated similarity search can be performed at a much lower cost than that needed to obtain the exact results. The proposed approximati on techniques are scalable and appear to be independent of the metric used. Extensions of these techniques to the environments of other similarity sea rch indexes are also discussed.