J 2011

Metric index: an efficient and scalable solution for precise and approximate similarity search

NOVÁK, David, Michal BATKO a Pavel ZEZULA

Základní údaje

Originální název

Metric index: an efficient and scalable solution for precise and approximate similarity search

Název česky

Metric index: efektivní a škálovatelné řešení pro přesné i aproximované podobnostní vyhledávání

Autoři

NOVÁK, David (203 Česká republika, garant, domácí), Michal BATKO (203 Česká republika, domácí) a Pavel ZEZULA (203 Česká republika, domácí)

Vydání

Information Systems, Elsevier, 2011, 0306-4379

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

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

Impakt faktor

Impact factor: 1.198

Kód RIV

RIV/00216224:14330/11:00073198

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000289395000003

Klíčová slova anglicky

Metric space; Similarity search; Data structure; Approximation; Scalability

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 23. 5. 2015 11:53, RNDr. Pavel Šmerk, Ph.D.

Anotace

ORIG CZ

V originále

Metric space is a universal and versatile model of similarity that can be applied in various areas of information retrieval. However, a general, efficient, and scalable solution for metric data management is still a resisting research challenge. We introduce a novel indexing and searching mechanism called Metric Index (M-Index) that employs practically all known principles of metric space partitioning, pruning, and filtering, thus reaching high search performance while having constant building costs per object. The heart of the M-Index is a general mapping mechanism that enables to actually store the data in established structures such as the B+ - tree or even in a distributed storage. We implemented the M-Index with the B+ - tree and performed experiments on two datasets - the first is an artificial set of vectors and the other is a real-life dataset composed of a combination of five MPEG-7 visual descriptors extracted from a database of up to several million digital images. The experiments put several M-Index variants under test and compare them with established techniques for both precise and approximate similarity search. The trials show that the M-Index outperforms the others in terms of efficiency of search-space pruning, I/O costs, and response times for precise similarity queries. Further, the M-Index demonstrates excellent ability to keep similar data close in the index which makes its approximation algorithm very efficient - maintaining practically constant response times while preserving a very high recall as the dataset grows and even beating approaches designed purely for approximate search.

Česky

Metrický prostor je univerzální a flexibilní model podobností, kterký může být aplikován v různých oblastech zpacování informací. Představujeme nový indexační a vyhledávací mechanismus M-Index, který využívá prakticky všechny známé principy metrického dělení, prořezávání a filtrování a tak dosahuje vysoké vyhledávací účinnosti a současně má konstantní náklady na vložení jednoho objektu.

Návaznosti

GAP103/10/0886, projekt VaV
Název: Vizuální vyhledávání obrázků na Webu (Akronym: VisualWeb)
Investor: Grantová agentura ČR, Vizuální vyhledávání obrázků na Webu
GPP202/10/P220, projekt VaV
Název: Podobnostní vyhledávání s konstantní škálovatelností (Akronym: SIM-SCALE)
Investor: Grantová agentura ČR, Podobnostní vyhledávání s konstantní škálovatelností
VF20102014004, projekt VaV
Název: Multimediální analýza (Akronym: Multimediální analýza)
Investor: Ministerstvo vnitra ČR, Multimediální analýza