Informační systém Masarykovy univerzity 

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

česky | in English

NOVÁK, David, Michal BATKO a Pavel ZEZULA. Metric index: an efficient and scalable solution for precise and approximate similarity search. Information Systems, Elsevier, 2011, roč. 36, č. 4, s. 721-733. ISSN 0306-4379. doi:10.1016/j.is.2010.10.002.
Další formáty:   BibTeX LaTeX RIS
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
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor Informatika
Stát vydavatele Nizozemsko
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 http://dx.doi.org/10.1016/j.is.2010.10.002
UT WoS 000289395000003
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: 23. 5. 2015 11:53.
Anotace
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.
Anotace č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 VaVNázev: Vizuální vyhledávání obrázků na Webu (Akronym: VisualWeb)
Investor: Grantová agentura ČR, Standardní projekty
GPP202/10/P220, projekt VaVNázev: Podobnostní vyhledávání s konstantní škálovatelností (Akronym: SIM-SCALE)
Investor: Grantová agentura ČR, Postdoktorské projekty
VF20102014004, projekt VaVNázev: Multimediální analýza (Akronym: Multimediální analýza)
Investor: Ministerstvo vnitra ČR, Jiné dotační projekty
VytisknoutZobrazeno: 19. 10. 2017 14:41

Relevantní odkazy 


Nahoru | Aktuální datum a čas: 19. 10. 2017 14:41, 42. (sudý) týden

Kontakty: istech(zavináč/atsign)fi(tečka/dot)muni(tečka/dot)cz, studijní odd., správci práv, is-technici, e-technici, IT podpora | Použití cookies | Více o Informačním systému