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 and that their performance is indeed the best among practical schedules.

Marco Patella, Paolo Ciaccia (2009). Approximate similarity search: A multi-faceted problem. JOURNAL OF DISCRETE ALGORITHMS, 7(1), 36-48 [10.1016/j.jda.2008.09.014].

Approximate similarity search: A multi-faceted problem

PATELLA, MARCO;CIACCIA, PAOLO
2009

Abstract

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 and that their performance is indeed the best among practical schedules.
2009
Marco Patella, Paolo Ciaccia (2009). Approximate similarity search: A multi-faceted problem. JOURNAL OF DISCRETE ALGORITHMS, 7(1), 36-48 [10.1016/j.jda.2008.09.014].
Marco Patella; Paolo Ciaccia
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/72425
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 60
  • ???jsp.display-item.citation.isi??? ND
social impact