An Access Structure for Similarity Search in Metric Spaces

Warning

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

DOHNAL Vlastislav

Year of publication 2004
Type Article in Proceedings
Conference Current Trends in Database Technology - EDBT 2004
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords similarity search; access structure; metric space
Description Similarity retrieval is an important paradigm for searching in environments where exact match has little meaning. Moreover, in order to enlarge the set of data types for which the similarity search can efficiently be performed, the mathematical notion of metric space provides a useful abstraction of similarity. In this paper, we present a novel access structure for similarity search in arbitrary metric spaces, called D-Index. D-Index supports easy insertions and deletions and bounded search costs for range queries with radius up to $\rho$. D-Index also supports disk memories, thus, it is able to deal with large archives. However, the partitioning principles employed in the D-Index are not very optimal since they produce high number of empty partitions. We propose several strategies of partitioning and, finally, compare them.
Related projects:

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