Dynamic Similarity Graph Construction with Kernel Density Estimation

Steinar Laenen, Peter Macgregor, He Sun · 2025

Read Dynamic Similarity Graph Construction with Kernel Density Estimation by Steinar Laenen, Peter Macgregor, He Sun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01696.txt.

Description

Steinar Laenen, Peter Macgregor, and He Sun keep a living map of which data points resemble each other while the data keeps changing. The map rests on kernel density estimation, a way of scoring how crowded the space is around any query point. Their data structure updates those scores as new points arrive, instead of rebuilding from scratch each time.

From the live scores they maintain a sparse stand-in for the full similarity graph, which links every point to every other. On top of it they build a fast clustering method that groups points by the graph's spectral structure. Tests on made-up and real data check how well the whole system keeps up.

Catalog record

CREATORSteinar Laenen, Peter Macgregor, He Sun
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE135 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-01696

Browse the full library · About the Tower of Babel