The traditional problem of similarity search requires to find, within a set of points, those that are closer to a query point q, according to a distance function d. In this paper we introduce the novel problem of metric filtering: in this scenario, each data point xi possesses its own distance function di and the task is to find those points that are close enough, according to di, to a query point q. This minor difference in the problem formulation introduces a series of challenges from the point of view of efficient evaluation. We provide basic definitions and alternative pivot-based resolution strategies, presenting results from a preliminary experimentation that show how the proposed solutions are indeed effective in reducing evaluation costs.

Principles of Information Filtering in Metric Spaces

CIACCIA, PAOLO;PATELLA, MARCO
2009

Abstract

The traditional problem of similarity search requires to find, within a set of points, those that are closer to a query point q, according to a distance function d. In this paper we introduce the novel problem of metric filtering: in this scenario, each data point xi possesses its own distance function di and the task is to find those points that are close enough, according to di, to a query point q. This minor difference in the problem formulation introduces a series of challenges from the point of view of efficient evaluation. We provide basic definitions and alternative pivot-based resolution strategies, presenting results from a preliminary experimentation that show how the proposed solutions are indeed effective in reducing evaluation costs.
Proceedings of the Second International Workshop on Similarity Search and Applications (SISAP 2009)
99
106
P. Ciaccia; M. Patella
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/86777
 Attenzione

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

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