Being prepared in a sparse world: the case of KNN graph construction
le 13 septembre 2016
15h30 - 17h00
ENS Rennes, Salle du conseil
Plan d'accès
Intervention de François Taïani, responsable de l'équipe ASAP à l'IRISA/Inria
Séminaire du département Informatique et télécommunications.
Son exposé sera consacré à un sujet d'algorithmique distribuée avec des applications aux réseaux sociaux.
K-Nearest-Neighbor (KNN) graphs have emerged as a fundamental building block of many on-line services providing 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 algorithm.
In this talk, I will present KIFF [1], 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 simple but powerful strategy drastically limits the computational cost required to rapidly converge to an accurate KNN solution, especially for sparse datasets. Our evaluation on a representative range of datasets show that KIFF provides, on average, a speed-up factor of 14 against recent state-of-the-art solutions while improving the quality of the KNN approximation by 18%.
[1] A. Boutet, A.-M. Kermarrec, N. Mittal, F. Taïani. Being prepared in a sparse world: the case of KNN graph construction. In ICDE, 2016
Being prepared in a sparse world: the case of KNN graph construction
K-Nearest-Neighbor (KNN) graphs have emerged as a fundamental building block of many on-line services providing 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 algorithm.
In this talk, I will present KIFF [1], 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 simple but powerful strategy drastically limits the computational cost required to rapidly converge to an accurate KNN solution, especially for sparse datasets. Our evaluation on a representative range of datasets show that KIFF provides, on average, a speed-up factor of 14 against recent state-of-the-art solutions while improving the quality of the KNN approximation by 18%.
[1] A. Boutet, A.-M. Kermarrec, N. Mittal, F. Taïani. Being prepared in a sparse world: the case of KNN graph construction. In ICDE, 2016
- Thématique(s)
- Formation, Recherche - Valorisation
- Contact
- David Cachera & François Schwarzentruber
Mise à jour le 25 janvier 2017