Fast similarity graph construction

Paper Title:

Fast Approximation of Similarity Graphs with Kernel Density Estimation

Published on:

21 October 2023

Primary Category:

Data Structures and Algorithms

Paper Authors:

Peter Macgregor,

He Sun

Bullets

Key Details

•

Proposes a novel connection between kernel density estimation and sparse similarity graph construction

•

Algorithm runs in near-linear time when dimensionality is constant

•

Outperforms competing methods on runtime while achieving comparable accuracy

•

Enables scaling to larger datasets than prior approaches

Explore the topics in this paper

approximate nearest neighbors

graph algorithms

kernel methods

similarity search

sparse graphs

AI generated summary

Fast similarity graph construction

This paper presents a new algorithm to efficiently construct a sparse similarity graph from a dataset that approximates the fully connected graph. The key idea is reducing similarity graph construction to kernel density estimation. Experiments show the algorithm is much faster and scales to larger datasets than prior methods.