Impressively fast and efficient KNN construction

Antoine Boutet 1 Anne-Marie Kermarrec 2 Nupur Mittal 2 François Taïani 2
1 Laboratoire Hubert Curien / Eris
LHC - Laboratoire Hubert Curien [Saint Etienne]
2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : K-Nearest-Neighbor (KNN) graphs have emerged as a fundamental building block of many on-line services such as recommendation, similarity search and classification. Constructing a KNN graph rapidly and accurately is however, a computationally intensive task. As data volumes keep growing, speed and the ability to scale out are becoming critical factors when deploying a KNN construction algorithm. In this work, we present KIFF, a generic, fast and scalable KNN graph construction algorithm. KIFF directly exploits the bipartite nature of most datasets to which KNN algorithms are applied. This novel strategy drastically limits the computational cost required to rapidly converge to an accurate KNN solution, especially for sparse datasets. We use a variety of datasets to experimentally prove that KIFF quickly computes a close approximation of the ideal KNN while reducing the computational cost compared to state-of-the-art approaches. KIFF provides, on average, a speed-up factor of 28 while improving the quality of the KNN approximation by 18%.
Liste complète des métadonnées

https://hal.inria.fr/hal-01169782
Contributeur : Antoine Boutet <>
Soumis le : mardi 30 juin 2015 - 11:19:10
Dernière modification le : lundi 3 décembre 2018 - 22:20:04

Identifiants

  • HAL Id : hal-01169782, version 1

Citation

Antoine Boutet, Anne-Marie Kermarrec, Nupur Mittal, François Taïani. Impressively fast and efficient KNN construction. [Research Report] University Saint Etienne. 2015. 〈hal-01169782〉

Partager

Métriques

Consultations de la notice

531