Distributed KNN-graph approximation via hashing

Riadh Trad 1 Alexis Joly 1 Boujemaa Nozha 2
1 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Efficiently constructing the K-Nearest Neighbor Graph (K-NNG) of large and high dimensional datasets is crucial for many applications with feature-rich objects, such as images or other multimedia content. In this paper we investigate the use of high dimensional hashing methods for efficiently approximating the K-NNG, notably in distributed environments. We first discuss the importance of balancing issues on the performance of such approaches and show why the baseline approach using Locality Sensitive Hashing does not perform well. Our new KNN-join method is based on RMMH, a recently introduced hash function family based on randomly trained classifiers. We show that the resulting hash tables are much more balanced and that the number of resulting collisions can be greatly reduced without degrading quality. We further improve the load balancing of our distributed approach by designing a parallelized local join algorithm, implemented within the MapReduce framework.
Type de document :
Communication dans un congrès
ICMR - International Conference on Multimedia Retrieval - 2012, Jun 2012, Hong-Kong, Hong Kong SAR China. ACM, pp.43:1--43:8, 2012, Proceedings of the 2nd ACM International Conference on Multimedia Retrieval. 〈http://www.icmr2012.org/〉. 〈10.1145/2324796.2324847〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00739713
Contributeur : Alexis Joly <>
Soumis le : lundi 8 octobre 2012 - 16:58:33
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Identifiants

Collections

Citation

Riadh Trad, Alexis Joly, Boujemaa Nozha. Distributed KNN-graph approximation via hashing. ICMR - International Conference on Multimedia Retrieval - 2012, Jun 2012, Hong-Kong, Hong Kong SAR China. ACM, pp.43:1--43:8, 2012, Proceedings of the 2nd ACM International Conference on Multimedia Retrieval. 〈http://www.icmr2012.org/〉. 〈10.1145/2324796.2324847〉. 〈hal-00739713〉

Partager

Métriques

Consultations de la notice

613