Similarity Join in Metric Spaces

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

DOHNAL Vlastislav GENNARO Claudio SAVINO Pasquale ZEZULA Pavel

Year of publication 2003
Type Article in Proceedings
Conference Proceedings of the European Conference on Information Retrieval Research
MU Faculty or unit

Faculty of Informatics

Citation
Field Computer hardware and software
Keywords similarity join; index structures; performance; text management
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.