Detailed Information on Publication Record
2011
Metric index: an efficient and scalable solution for precise and approximate similarity search
NOVÁK, David, Michal BATKO and Pavel ZEZULABasic information
Original name
Metric index: an efficient and scalable solution for precise and approximate similarity search
Name in Czech
Metric index: efektivní a škálovatelné řešení pro přesné i aproximované podobnostní vyhledávání
Authors
NOVÁK, David (203 Czech Republic, guarantor, belonging to the institution), Michal BATKO (203 Czech Republic, belonging to the institution) and Pavel ZEZULA (203 Czech Republic, belonging to the institution)
Edition
Information Systems, Elsevier, 2011, 0306-4379
Other information
Language
English
Type of outcome
Článek v odborném periodiku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Netherlands
Confidentiality degree
není předmětem státního či obchodního tajemství
Impact factor
Impact factor: 1.198
RIV identification code
RIV/00216224:14330/11:00073198
Organization unit
Faculty of Informatics
UT WoS
000289395000003
Keywords in English
Metric space; Similarity search; Data structure; Approximation; Scalability
Tags
Tags
International impact, Reviewed
Změněno: 23/5/2015 11:53, RNDr. Pavel Šmerk, Ph.D.
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.
In Czech
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.
Links
| GAP103/10/0886, research and development project |
| ||
| GPP202/10/P220, research and development project |
| ||
| VF20102014004, research and development project |
|