An Access Structure for Similarity Search in Metric Spaces

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F04%3A00010797" target="_blank" >RIV/00216224:14330/04:00010797 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

An Access Structure for Similarity Search in Metric Spaces

Original language 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 ofmetric 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.

Czech name

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

Czech description

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ímje 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.

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2004

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of ICDE/EDBT 2004 Joint Ph.D. Workshop, 18 March 2004, Heraklion, Greece and 29 March 2004, Boston, MA, USA

ISBN

960-524-177-3

ISSN

—

e-ISSN

—

Number of pages

10

Pages from-to

149-158

Publisher name

Crete University Press

Place of publication

Greece

Event location

Boston, MA, USA

Event date

Mar 29, 2004

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—