Use of permutation prefixes for efficient and scalable approximate similarity search
Esuli A
Compression Management Science and Operations Research Computer Science Applications Dynamic Programming Library and Information Sciences Media Technology Information Systems Coding and Information Theory Information theory
We present the Permutation Prefix Index (this work is a revised and extended version of Esuli (2009b), presented at the 2009 LSDS-IR Workshop, held in Boston) (PP-Index), an index data structure that supports efficient approximate similarity search. The PP-Index belongs to the family of the permutation-based indexes, which are based on representing any indexed object with "its view of the surrounding world", i.e., a list of the elements of a set of reference objects sorted by their distance order with respect to the indexed object. In its basic formulation, the PP-Index is strongly biased toward efficiency. We show how the effectiveness can easily reach optimal levels just by adopting two "boosting" strategies: multiple index search and multiple query search, which both have nice parallelization properties. We study both the efficiency and the effectiveness properties of the PP-Index, experimenting with collections of sizes up to one hundred million objects, represented in a very high-dimensional similarity space.
Source: INFORMATION PROCESSING & MANAGEMENT, vol. 48 (issue 5), pp. 889-902
Metrics
Cited in SectionsSee how this article has been cited at scite.ai
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Back to previous page
@article{oai:it.cnr:prodotti:199514,
title = {Use of permutation prefixes for efficient and scalable approximate similarity search},
author = {Esuli A},
doi = {10.1016/j.ipm.2010.11.011},
year = {2012}
}
0000-0002-5725-4322