# Sub-linear RACE Sketches for Approximate Kernel Density Estimation on Streaming Data

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Dec 2019.

## Built on by (most cited first, 14 of 14)

- [How to Train Data-Efficient LLMs](https://mlsanity.com/paper/2402.09668/) (2024)
- [FisherSFT: Data-Efficient Supervised Fine-Tuning of Language Models Using Information Gain](https://mlsanity.com/paper/2505.14826/) (2025)
- [Fast Private Kernel Density Estimation via Locality Sensitive Quantization](https://mlsanity.com/paper/2307.01877/) (2023)
- [Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theory](https://mlsanity.com/paper/2208.03915/) (2022)
- [RACE Attention: A Strictly Linear-Time Attention Layer for Training on Outrageously Large Contexts](https://mlsanity.com/paper/2510.04008/) (2025)
- [SOCKET: SOft Collision Kernel EsTimator for Sparse Attention](https://mlsanity.com/paper/2602.06283/) (2026)
- [Efficient Inference via Universal LSH Kernel](https://mlsanity.com/paper/2106.11426/) (2021)
- [Adaptive Sampling for Deep Learning via Efficient Nonparametric Proxies](https://mlsanity.com/paper/2311.13583/) (2023)
- [Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases](https://mlsanity.com/paper/2605.09472/) (2026)
- [Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation](https://mlsanity.com/paper/2610.05174/) (2026)
- [Density Sketches for Sampling and Estimation](https://mlsanity.com/paper/2102.12301/) (2021)
- [M2M: A general method to perform various data analysis tasks from a differentially private sketch](https://mlsanity.com/paper/2211.14062/) (2022)
- [Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation](https://mlsanity.com/paper/2510.23039/) (2025)
- [SCoNE: Spherical Consistent Neighborhoods Ensemble for Effective and Efficient Multi-View Anomaly Detection](https://mlsanity.com/paper/2512.05540/) (2025)

## Abstract (arXiv)

Kernel density estimation is a simple and effective method that lies at the heart of many important machine learning applications. Unfortunately, kernel methods scale poorly for large, high dimensional datasets. Approximate kernel density estimation has a prohibitively high memory and computation cost, especially in the streaming setting. Recent sampling algorithms for high dimensional densities can reduce the computation cost but cannot operate online, while streaming algorithms cannot handle high dimensional datasets due to the curse of dimensionality. We propose RACE, an efficient sketching algorithm for kernel density estimation on high-dimensional streaming data. RACE compresses a set of N high dimensional vectors into a small array of integer counters. This array is sufficient to estimate the kernel density for a large class of kernels. Our sketch is practical to implement and comes with strong theoretical guarantees. We evaluate our method on real-world high-dimensional datasets and show that our sketch achieves 10x better compression compared to competing methods.