D 2004

An Access Structure for Similarity Search in Metric Spaces

DOHNAL, Vlastislav

Basic information

Original name

An Access Structure for Similarity Search in Metric Spaces

Name in Czech

Indexová struktura pro podobnostní hledání v metrických prostorech

Authors

DOHNAL, Vlastislav (203 Czech Republic, guarantor)

Edition

LNCS 3268. Berlin, Germany, Current Trends in Database Technology - EDBT 2004, p. 133-143, 11 pp. 2004

Publisher

Springer-Verlag Heidelberg

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Czech Republic

Confidentiality degree

není předmětem státního či obchodního tajemství

RIV identification code

RIV/00216224:14330/04:00010798

Organization unit

Faculty of Informatics

ISBN

3-540-23305-9

UT WoS

000226132200013

Keywords in English

similarity search; access structure; metric space

Tags

International impact, Reviewed
Změněno: 22/10/2010 16:13, doc. RNDr. Vlastislav Dohnal, Ph.D.

Abstract

V originále

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.

In Czech

Podobností hledání je důležité v prostředích, ve kterých hledání na přesnou shodu má malý význam. Pro zvýšení okruhu aplikovatelnosti podobnostního hledání se jako matematická abstrakce používá pojem metrického prostoru. V tomto článku popisujeme novou indexovou metodu pro podobnostní hledání nazvanou D-Index. D-Index vkládá a maže datové objekty s velmi nízkými náklady. Rozsahové dotazy s poloměrem menším než rho jsou řešeny v čase, který je shora omezený. D-Index také podporuje disková úložiště a tím je schopen pracovat i s velkými objemy dat, které překračují velikost vnitřní paměti. Protože metody pro dělení prostoru použité v D-Indexu nejsou příliš optimální a vytvářejí velké množství prázdných oblastí, navrhujeme několik metod dělení a porovnáváme je.

Links

MSM 143300004, plan (intention)
Name: Digitální knihovny
Investor: Ministry of Education, Youth and Sports of the CR, Digital libraries