Partager cette page :

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.

Séminaire Informatique et télécommunications

Séminaire Informatique et télécommunications

Son exposé sera consacré à un sujet d'algorithmique distribuée avec des applications aux réseaux sociaux.

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