# Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation

arXiv: https://arxiv.org/abs/2510.23039 · HTML: https://mlsanity.com/paper/2510.23039/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 27 Oct 2025.

## Builds on (most cited first, 9 of 9)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Beyond Locality-Sensitive Hashing](https://mlsanity.com/paper/1306.1547/) (2013)
- [Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors](https://mlsanity.com/paper/1608.03580/) (2016)
- [Sub-linear RACE Sketches for Approximate Kernel Density Estimation on Streaming Data](https://mlsanity.com/paper/1912.02283/) (2019)
- [TAKDE: Temporal Adaptive Kernel Density Estimator for Real-Time Dynamic Density Estimation](https://mlsanity.com/paper/2203.08317/) (2022)
- [A Refined Analysis of LSH for Well-dispersed Data Points](https://mlsanity.com/paper/1612.04571/) (2016)
- [Optimal Las Vegas Locality Sensitive Data Structures](https://mlsanity.com/paper/1704.02054/) (2017)

## Abstract (arXiv)

Approximate Nearest Neighbor (ANN) search and Approximate Kernel Density Estimation (A-KDE) are fundamental problems at the core of modern machine learning, with broad applications in data analysis, information systems, and large-scale decision making. In massive and dynamic data streams, a central challenge is to design compact sketches that preserve essential structural properties of the data while enabling efficient queries. In this work, we develop new sketching algorithms that achieve sublinear space and query time guarantees for both ANN and A-KDE for a dynamic stream of data. For ANN in the streaming model, under natural assumptions, we design a sublinear sketch that requires only O(n(1-η)(1+ρ)) memory by storing only a sublinear (n-η) fraction of the total inputs, where ρ is a parameter of the LSH family, and 0<η<1. Our method supports sublinear query time, batch queries, and extends to the more general Turnstile model. While earlier works have focused on Exact NN, this is the first result on ANN that achieves near-optimal trade-offs between memory size and approximation error. Next, for A-KDE in the Sliding-Window model, we propose a sketch of size Oleft(LW · frac1√1+ε - 1 log2 Nright), where L is the number of sketch rows, W is the LSH range, N is the window size, and ε is the approximation error. This, to the best of our knowledge, is the first theoretical sublinear sketch guarantee for A-KDE in the Sliding-Window model. We complement our theoretical results with experiments on various real-world datasets, which show that the proposed sketches are lightweight and achieve consistently low error in practice.