Back to Search
Start Over
Metric Index: An efficient and scalable solution for precise and approximate similarity search
- Source :
-
Information Systems . Jun2011, Vol. 36 Issue 4, p721-733. 13p. - Publication Year :
- 2011
-
Abstract
- Abstract: 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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03064379
- Volume :
- 36
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Information Systems
- Publication Type :
- Academic Journal
- Accession number :
- 59328286
- Full Text :
- https://doi.org/10.1016/j.is.2010.10.002