Articolo in rivista, 2003, ENG, 10.1023/A:1025026030880

D-Index: Distance Searching Index for Metric Data Sets, Multimedia Tools and Applications

Dohnal V.; Gennaro C.; Savino P.; Zezula P.

Masaryk University, Brno, Czech Republic; CNR-ISTI, Pisa, Italy; CNR-ISTI, Pisa, Italy; Masaryk University, Brno, Czech Republic

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.

Multimedia tools and applications 21 , pp. 9–33

Keywords

metric spaces, similarity search, index structures, performance

CNR authors

Savino Pasquale, Gennaro Claudio

CNR institutes

ISTI – Istituto di scienza e tecnologie dell'informazione "Alessandro Faedo"

ID: 43688

Year: 2003

Type: Articolo in rivista

Creation: 2009-06-16 00:00:00.000

Last update: 2020-01-20 14:18:45.000

External IDs

CNR OAI-PMH: oai:it.cnr:prodotti:43688

DOI: 10.1023/A:1025026030880

ISI Web of Science (WOS): 000184619000002

Scopus: 2-s2.0-0042194447