Fast Sublinear Sketches for ANN and KDE

In modern applications, massive volumes of input data often arrive as dynamic streams. Storing the entire input can be costly and challenging. Sublinear-space sketches are therefore essential for processing such massive data efficiently. We study Approximate Nearest Neighbor (*ANN*) search, a fundamental and extensively studied problem in algorithms and machine learning. However, *ANN* faces a fundamental space barrier in the streaming setting. We establish a simple information-theoretic lower bound ruling out $o(n)$-bit sketches in the worst case, even for insertion-only streams. On the positive side, under natural assumptions on the input data distribution, we design a sketch that retains an $n^{-\eta }$ fraction of the input and uses $\mathcal{O}(n^{(1-\eta )(1+\rho )})$ space for fixed locality-sensitive hashing (LSH) collision probabilities. Here, $\rho$ is the LSH exponent and $0<\eta <1$; the space bound is sublinear whenever $\eta >\rho /(1+\rho )$. Our sketch preserves classical *LSH* approximation guarantees for the full stream while matching its space and query bounds on the retained sample. It supports batch queries and turnstile updates under bounded local deletions. These space–approximation trade-offs complement long line of prior work on dynamic ANN that focused primarily on update time. Experiments on real-world and synthetic datasets demonstrate high approximate recall with compact sketches. On the evaluated real-world benchmarks, our method improves the recall–space trade-off over RACE-CMS (Coleman et al., ICML 2020) and achieves substantially higher query throughput. As a further application of *LSH*-based sketching, we consider Approximate Kernel Density Estimation (*A-KDE*), another fundamental problem in data analysis. By incorporating exponential histograms, we obtain the first sublinear-space sketch with provable approximation guarantees for *A-KDE* in the sliding-window model. While earlier sketches support insertions and deletions in the turnstile model, our construction handles data expiration explicitly while supporting efficient updates and queries. Experiments on real-world and synthetic datasets demonstrate accuracy comparable to RACE (Coleman and Shrivastava, WWW 2020) with a small memory footprint.