D-Index: Distance Searching Index for Metric Data Sets

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 SAVINO Pasquale ZEZULA Pavel

Year of publication 2003
Type Article in Periodical
Magazine / Source Multimedia Tools and Applications
MU Faculty or unit

Faculty of Informatics

Citation
Web http://ipsapp008.kluweronline.com/content/getfile/5025/47/2/abstract.htm
Field Computer hardware and software
Keywords metric spaces; similarity search; index structures; performance evaluation
Description In order to speedup retrieval in large collections of data, index structures partition the data into subsets so that query requests can be evaluated without examining the entire collection. As the complexity of modern data types grows, metric spaces have become a popular paradigm for similarity retrieval. We propose a new index structure, called D-Index, that combines a novel clustering technique and the pivot-based distance searching strategy to speed up execution of similarity range and nearest neighbor queries for large files with objects stored in disk memories. We have qualitatively analyzed D-Index and verified its properties on actual implementation. We have also compared D-Index with other index structures and demonstrated its superiority on several real-life data sets. Contrary to tree organizations, the D-Index structure is suitable for dynamic environments with a high rate of delete/insert operations.
Related projects:

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