Cluster-and-Conquer: When Randomness Meets Graph Locality
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 Cluster-and-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 x4.42 and even improving the KNN quality.
WOS:000687830800187
2021-01-01
978-1-7281-9184-3
Los Alamitos
IEEE International Conference on Data Engineering
2027
2032
REVIEWED
Event name | Event place | Event date |
ELECTR NETWORK | Apr 19-22, 2021 | |