Istituto di Scienza e Tecnologie dell'Informazione     
Dohnal V., Gennaro C., Savino P., Zezula P. Similarity Join in Metric Spaces. In: European Conference on IR Research (Pisa, Italy, April 2003). Proceedings, pp. 452 - 467. Fabrizio Sebastiani (ed.). (Lecture Notes in Computer Science, vol. 2633). Springer, 2003.
Similarity join in distance spaces constrained by the metric postulates is the necessary complement of more famous similarity range and the nearest neighbors search primitives. However, the quadratic computational complexity of similarity joins prevents from applications on large data collections. We first study the underlying principles of such joins and suggest three categories of implementation strategies based on filtering, partitioning, or similarity range searching. Then we study an application of the D-index to implement the most promising alternative of range searching. Though also this approach is not able to eliminate the intrinsic quadratic complexity of similarity joins, significant performance improvements are confirmed by experiments.
Subject Metric Space
Similarity Join
Access structures
Performance Evaluation
H.3.4 Systems and Software. Performance evaluation (efficiency and

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional