The Many Facets of Approximate Similarity Search

none2In this article, we review the major paradigms for approximate similarity queries and propose a classification schema that easily allows existing approaches to be compared along several independent coordinates. Then, we discuss the impact that scheduling of index nodes can have on performance and show that, unlike exact similarity queries, no provable optimal scheduling strategy exists for approximate queries. On the positive side, we show that optimal-on-the-average schedules are well-defined. We complete by critically reviewing methods for evaluating the quality of approximate results.SISAP 2008 è stato accettato come workshop della conferenza internazionale ICDE (si veda http://www.sisap.org/2008/index.php?f=venue), e i suoi atti appaiono quindi anche nel volume "ICDE Workshop 2008", cui si riferisce la copia del lavoro allegato (con numerazione delle pagine da 309 a 321)mixedM. Patella; P. CiacciaM. Patella; P. Ciacci