Skip to Main content Skip to Navigation
New interface
Conference papers

Cluster-and-Conquer: When Randomness Meets Graph Locality

George Giakkoupis 1 Anne-Marie Kermarrec 2 Olivier Ruas 3 François Taïani 1 
1 WIDE - the World Is Distributed Exploring the tension between scale and coordination
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
3 SPIRALS - Self-adaptation for distributed services and large software systems
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, which they incrementally improve by traversing neighbors-of-neighbors links. Unfortunately, the initial random graph exhibits a poor graph locality, leading to many unnecessary similarity computations. In this paper, we remove this drawback with Clusterand-Conquer (C 2 for short). Cluster-and-Conquer boosts the starting configuration of greedy algorithms thanks to a novel lightweight clustering mechanism, dubbed FastRandomHash. FastRandomHash leverages randomness and recursion to precluster similar nodes at a very low cost. Our extensive evaluation on real datasets shows that Cluster-and-Conquer significantly outperforms existing approaches, including LSH, yielding speedups of up to ×4.42 and even improving the KNN quality.
Complete list of metadata
Contributor : Olivier Ruas Connect in order to contact the contributor
Submitted on : Thursday, September 16, 2021 - 4:31:06 PM
Last modification on : Tuesday, November 22, 2022 - 2:26:16 PM
Long-term archiving on: : Friday, December 17, 2021 - 7:24:04 PM


Files produced by the author(s)



George Giakkoupis, Anne-Marie Kermarrec, Olivier Ruas, François Taïani. Cluster-and-Conquer: When Randomness Meets Graph Locality. ICDE 2021 - IEEE 37th International Conference on Data Engineering, Apr 2021, Chania, Greece. pp.2027-2032, ⟨10.1109/ICDE51399.2021.00195⟩. ⟨hal-03346860⟩



Record views


Files downloads