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, 9 s. ISBN 978-0-7695-3765-8.
Další formáty:   BibTeX LaTeX RIS
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 (203 Česko, garant, domácí) a Michal BATKO (203 Česko, domácí).
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
Originální 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"
WWW 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
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 14. 3. 2016 14:48.
Anotace
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.
Anotace č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 VaVNázev: Vyhledávání v rozsáhlých multimediálních databázích
Investor: Grantová agentura ČR, Standardní projekty
VytisknoutZobrazeno: 13. 7. 2020 14:23