Projects per year
Abstract / Description of output
Constructing a similarity graph from a set X of data points in R d is the first step of many modern clustering algorithms. However, typical constructions of a similarity graph have high time complexity, and a quadratic space dependency with respect to |X|. We address this limitation and present a new algorithmic framework that constructs a sparse approximation of the fully connected similarity graph while preserving its cluster structure. Our presented algorithm is based on the kernel density estimation problem, and is applicable for arbitrary kernel functions. We compare our designed algorithm with the well-known implementations from the scikit-learn library and the FAISS library, and find that our method significantly outperforms the implementation from both libraries on a variety of datasets.
Original language | English |
---|---|
Title of host publication | 37th Conference on Neural Information Processing Systems (NeurIPS 2023) |
Publisher | Curran Associates Inc |
Pages | 67603-67624 |
Number of pages | 22 |
Volume | 36 |
Publication status | Published - 15 Dec 2023 |
Event | Thirty-Seventh Conference on Neural Information Processing Systems - New Orleans Ernest N. Morial Convention Center, New Orleans, United States Duration: 10 Dec 2023 → 16 Dec 2023 Conference number: 37 https://neurips.cc/Conferences/2023 |
Conference
Conference | Thirty-Seventh Conference on Neural Information Processing Systems |
---|---|
Abbreviated title | NeurIPS 2023 |
Country/Territory | United States |
City | New Orleans |
Period | 10/12/23 → 16/12/23 |
Internet address |
Fingerprint
Dive into the research topics of 'Fast Approximation of Similarity Graphs with Kernel Density Estimation'. Together they form a unique fingerprint.Projects
- 1 Finished