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 / P. Ciaccia; M. Patella. - STAMPA. - (2009), pp. 99-106. (Intervento presentato al convegno Second International Workshop on Similarity Search and Applications (SISAP 2009) tenutosi a Praga, Repubblica Ceca nel 29-30 Agosto 2009).
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.