PP-Index: using permutation prefixes for efficient and scalable similarity search (Extended Abstract)
Esuli A.
Information Search and Retrieval Approximate Similarity Search Access Methods
The Permutation Prefix Index (PP-Index) is a data structure that allows to perform efficient approximate similarity search. It is a permutation-based index, which is 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 biased toward efficiency. We show how the effectiveness can 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: 18th Italian Symposium on Advanced Database Systems, pp. 318–325, Rimini, Italy, 20-23 June 2010
Publisher: Esculapio, Bologna, ITA
Back to previous page
@inproceedings{oai:it.cnr:prodotti:91776,
title = {PP-Index: using permutation prefixes for efficient and scalable similarity search (Extended Abstract)},
author = {Esuli A.},
publisher = {Esculapio, Bologna, ITA},
booktitle = {18th Italian Symposium on Advanced Database Systems, pp. 318–325, Rimini, Italy, 20-23 June 2010},
year = {2010}
}
0000-0002-5725-4322