Metric Index: An Efficient and Scalable Solution for Similarity Search

NOVÁK, David a Michal BATKO. Metric Index: An Efficient and Scalable Solution for Similarity Search. In Proceedings of the 2009 Second International Workshop on Similarity Search and Applications. Washington, DC, USA: IEEE Computer Society, 2009, s. 65-73. ISBN 978-0-7695-3765-8.

Základní údaje

Originální název

Metric Index: An Efficient and Scalable Solution for Similarity Search

Název česky

Metrický index: Efektivní a Škálovatelné řešení pro podobnostní vyhledávání

Autoři

NOVÁK, David a Michal BATKO

Vydání

Washington, DC, USA, Proceedings of the 2009 Second International Workshop on Similarity Search and Applications, od s. 65-73, 9 s. 2009

Nakladatel

IEEE Computer Society

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

ACM Portal Link

Kód RIV

RIV/00216224:14330/09:00029661

Organizační jednotka

Fakulta informatiky

ISBN

978-0-7695-3765-8

UT WoS

000282087600008

Klíčová slova anglicky

metric space; similarity search; data structure; approximation; scalability

Štítky

DISA

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

Metric space as a universal and versatile model of similarity can be applied in various areas of non-text 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. The heart of the M-Index is a general mapping mechanism that enables to actually store the data in well-established structures such as the B+-tree or even in a distributed storage. We have implemented the M-Index with B+-tree and performed experiments on a combination of five MPEG-7 descriptors in a database of hundreds of thousands digital images. The experiments put under test several M-Index variants and compare them with two orthogonal approaches - the PM-Tree and the iDistance. 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. Furthermore, the M-Index demonstrates an 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.

Česky

Metrický prostor je univerzálním modelem podobnosti, který může být použit v různých oblastech netextového vyhledávání. Představujeme nový indexační a vyhledávácí mechanismus s názvem "Metric Index" (M-Index), který využívá prakticky všechny známé principy dělení, prořezávání a filtrování metrického prostoru. Experimenty ukazují, že M-Index poráží ostatní struktury v efektivitě omezování vyhledávácího prostoru, nákladech na V/V a době odezvy pro přesné podobnostní vyhledávání. Navíc M-Index prokazuje vyjimečnou schopnost držet podobná data blízko u sebe, což velmi zefektivňuje jeho aproximační algoritmus - dosahuje téměř konstantní doby odezvy pro rostoucí velikost databáze přičemž udržuje vysokou kvalitu odpovědi.

---

Návaznosti

GA201/09/0683, projekt VaV

Název: Vyhledávání v rozsáhlých multimediálních databázích Investor: Grantová agentura ČR, Vyhledávání v rozsáhlých multimediálních databázích