Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
Ved Danait, Srijan Das, Sujoy Bhore · 2025
Read Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation by Ved Danait, Srijan Das, Sujoy Bhore (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-2510-23039.txt.
Introduction
Ved Danait, Srijan Das, and Sujoy Bhore design compact sketches for two core tasks on massive data streams: finding near neighbors and estimating kernel density. Data arrives fast and changes over time, so storing it all is not an option. A good sketch keeps the structure needed to answer queries while using far less than linear space.
The authors give new sketching algorithms with sublinear space and query time for both tasks in a dynamic stream. Their guarantees hold as items come and go. Such sketches could help search and monitoring systems stay fast without keeping full copies of huge live data.
Catalog record
| CREATOR | Ved Danait, Srijan Das, Sujoy Bhore |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-23039
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation Ved Danait, Srijan Das, Sujoy Bhore Abstract 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 𝒪 ( n 1 + ρ − η ) \mathcal{O}(n^{1+\rho-\eta}) memory by storing only a sublinear ( n − η n^{-\eta} ) fraction of the total inputs, where ρ \rho is a parameter of the LSH family, and 0 < η < 1 0<\eta<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 𝒪 ( R W ⋅ 1 1 + ϵ − 1 log 2 N ) \mathcal{O}\left(RW\cdot\frac{1}{\sqrt{1+\epsilon}-1}\log^{2}N\right) , where R R is the number of sketch rows, W W is the LSH range, N N is the window size, and ϵ \epsilon 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. 1 Introduction Modern machine learning and data analysis often require answering similarity and density queries over massive and evolving datasets. As data grows in scale and arrives in dynamic streams, it becomes infeasible to store or process everything explicitly, and the central challenge is to design compact sketches that preserve essential structure while supporting efficient queries. This challenge has been highlighted in seminal works on sublinear algorithms, streaming, and high-dimensional data processing [ AMS96 , IM98 , GIM+99 , Mut05 , CM05 ] . Two central problems in this setting are Approximate Nearest Neighbor ( ANN ) search and Approximate Kernel Density Estimation ( A-KDE ). Approximate Nearest Neighbor ( ANN ): The Approximate Nearest Neighbor ( ANN ) problem formalizes similarity search in high-dimensional spaces. In its standard (c,r) -formulation, given a point set {\mathbb{P}} in a metric space ({\mathcal{X}},{\mathcal{D}}) , the task is to preprocess {\mathbb{P}} so that, for any query {\bm{q}}\in{\mathcal{X}} , if the distance to its nearest neighbor in {\mathbb{P}} is at most r , then with probability at least 1-\delta the algorithm returns a point within distance cr of {\bm{q}} . This formulation corresponds to the modern version of the (r_{1},r_{2}) -PLEB problem introduced by [ IM98 ] , with a relaxed variant due to [ HPIM12 ] that permits null or arbitrary answers if no point lies within distance r_{1} . In [ HPIM12 ] , Har-Peled et al. presented fully dynamic solutions to ANN , though such methods require at least linear space and are not suited for the streaming model. In parallel, locality-sensitive hashing–based frameworks (e.g., [ Pan06 , AI08 , AINR14 , AR15a , ALRW17 , Ahl17 ] ) have driven much of the progress on optimizing space–time trade-offs in the primarily static and dynamic settings rather than streaming. Approximate Kernel Density Estimation ( A-KDE ): Kernel density estimation ( KDE ) is a classical non-parametric method for estimating probability distributions from data [ DLP11 , Par62 , Sil18 , Sco15 ] . Given a sequence of i.i.d. random variables x_{1},\dots,x_{n}\in\mathbb{R}^{d} , the density at a query x is estimated as \hat{p}(x;\sigma)=\frac{1}{n}\sum_{i=1}^{n}K_{\sigma}(x-x_{i}), where K_{\sigma}(\cdot) is a kernel function with bandwidth \sigma . While highly effective, exact KDE becomes computationally prohibitive for large-scale or streaming datasets, which motivated the approximate version (namely, A-KDE ), where the goal is to return, for any query q , a (1\pm\epsilon) multiplicative approximation to the true density with probability at least 1-\delta . A-KDE thus provides a principled framework for large-scale density estimation, balancing accuracy and efficiency. Notable advances include Repeated Array of Counts Estimator (in short, RACE ) [ CS20 ] , which compresses high-dimensional vectors into compact counters; TAKDE [ WDS23 ] , evaluated experimentally in the sliding-window setting; and KDE-Track [ QWZ16 ] , designed for spatiotemporal streams. Streaming Applications: Consider a personalized news agent or financial assistant powered by large language models: vast streams of articles or market updates arrive dynamically, yet the system must provide timely, personalized insights without storing or processing the entire corpus. Approximate nearest neighbor ( ANN ) search enables real-time matching of a user’s evolving interests to relevant news items or market updates, while approximate kernel density estimation ( A-KDE ) captures shifts in topical or market distributions to adapt recommendations. A similar challenge arises in large-scale image and video platforms, where streams of photos or frames arrive continuously. ANN supports fast similarity search for recommendation, moderation, or retrieval in these large-scale systems, while A-KDE tracks distributional changes such as emerging styles, anomalies, or trending categories. Such scenarios are not limited to text or vision: related needs appear in personalization, anomaly detection, and monitoring of high-volume data streams [ AMS96 , IM98 , Mut05 , CM05 , JDS11 , CS20 , QWZ16 , WDS23 ] . Across these domains, storing or processing all data explicitly is infeasible, making compact sketches essential for balancing efficiency and accuracy in large-scale retrieval problems. A central question is how to efficiently perform approximate nearest neighbor ( ANN ) search and approximate kernel density estimation ( A-KDE ) on massive, dynamically evolving data streams. In this work, we use three most commonly used models of streaming, namely, insertion-only, turnstile, and sliding window. Insertion-Only: In the insertion-only streaming model, data arrives sequentially and can only be appended to the dataset; deletions are not allowed. This model captures many practical scenarios, such as log analysis, clickstreams, and sensor readings, where storing all data explicitly is infeasible. The goal is to maintain a compact summary that supports approximate queries using sublinear memory. Classical sketches such as Count-Min [ CM05 ] , AMS [ AMS96 ] , and their extensions to similarity search and density estimation [ IM98 , CS20 ] have demonstrated the effectiveness of insertion-only algorithms for both high-dimensional similarity search and approximate kernel density estimation. Turnstile: The Turnstile model generalizes insertion-only streams by allowing both additions and deletions of data elements. This model is essential in settings where the dataset evolves dynamically or counts need to be adjusted, such as network traffic monitoring, dynamic graphs, and streaming recommendation updates. Maintaining sublinear sketches under Turnstile updates is more challenging, but prior work has shown that linear sketches, hash-based methods, and RACE -style counters can provide provable guarantees on query accuracy while supporting deletions efficiently