Approximate similarity retrieval with M-trees

Sommario non disponibile.

Motivated by the urgent needs to improve efficiency of similarity queries, approximate similarity retrieval is investigated in the environment of a metric tree index called the M-tree. Three different approximation techniques are proposed -- distinguishing in the principle how to give up the query precision for the sake of improved performance. Measures, able to quantify the improvements of performance efficiency and the quality of approximations are defined and the proposed approximation techniques tested on different synthetic and real-life files. The evidence obtained from the experiments confirms the initial hypothesis that a high quality approximated similarity search can be obtained at much lower cost than that which is needed to get the exact results. Future research directions as well as extensions of the proposed approximation techniques to the environments of other similarity search indexes are also discussed. Possible applications of the approach to practical data and index management problems are discussed.