OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Dynamic Multi-probe LSH: An I/O Efficient Index Structure for Approximate Nearest Neighbor Search

Yin, Shaoyi and Badr, Mehdi and Vodislav, Dan Dynamic Multi-probe LSH: An I/O Efficient Index Structure for Approximate Nearest Neighbor Search. (2013) In: 24th International Conference on Database and Expert Systems Applications (DEXA 2013), 26 August 2013 - 29 August 2013 (Prague, Czech Republic).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1007/978-3-642-40285-2_7


Locality-Sensitive Hashing (LSH) is widely used to solve approximate nearest neighbor search problems in high-dimensional spaces. The basic idea is to map the “nearby” objects into a same hash bucket with high probability. A significant drawback is that LSH requires a large number of hash tables to achieve good search quality. Multi-probe LSH was proposed to reduce the number of hash tables by looking up multiple buckets in each table. While optimized for a main memory database, it is not optimal when multi-dimensional vectors are stored in a secondary storage, because the probed buckets may be randomly distributed in different physical pages. In order to optimize the I/O efficiency, we propose a new method called Dynamic Multi-probe LSH which groups small hash buckets into a single bucket by dynamically increasing the number of hash functions during the index construction. Experimental results show that our method is significantly more I/O efficient.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to Springer editor. This papers appears in volume 8055 of Lecture Notes in Computer Science ISSN : 0302-9743 ISBN 978-3-642-40284-5 The original PDF is available at: https://link.springer.com/chapter/10.1007%2F978-3-642-40285-2_7
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université de Cergy-Pontoise (FRANCE)
Other partners > Ecole Nationale Supérieure de l'Electronique et de ses Applications - ENSEA (France)
Laboratory name:
ANR : Agence nationale de la recherche (France)
Deposited On:24 Apr 2020 13:57

Repository Staff Only: item control page