Similarity Join in Metric Spaces Using eD-Index

Warning

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

DOHNAL Vlastislav GENNARO Claudio ZEZULA Pavel

Year of publication 2003
Type Article in Proceedings
Conference Database and Expert Systems Applications, DEXA 2003
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords similarity join; index structures; performance; metric data
Description Similarity join in distance spaces constrained by the metric postulates is the necessary complement of more famous similarity range and the nearest neighbor search primitives. However, the quadratic computational complexity of similarity joins prevents from applications on large data collections. We present the eD-Index, an extension of D-index, and we study an application of the eD-Index to implement two algorithms for similarity self joins, i.e. the range query join and the overloading join. Though also these approaches are 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.