Papers for

data stream engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Gaussian kernel enables efficient streaming similarity statistics in vectors

Streaming Algorithms for Gaussian Kernel Density Statistics

Abstract: Motivated by data produced by generative systems, \cite{LZ26b} formulates similarity-aware statistics via a weighted similarity graph, replacing equality with similarity in classical frequency-based statistics. Although this framework captures semantic relationships between nonidentical items, under general similarity functions even coarse one-pass approximation can require linear space. We therefore ask whether the geometric structure present in natural vector similarities can overcome this barrier. We answer this question affirmatively for the Gaussian kernel. For fixed-dimensional Euclidean vector streams, we study similarity-aware analogues of classical frequency statistics, including the number of distinct elements and frequency moments, through the diversity index and Gaussian density moments. We give one-pass sublinear-space approximation algorithms that exploit the geometric and analytic properties of the Gaussian kernel, and complement them with lower bounds. Our results show that geometric structure can fundamentally change the streaming complexity of similarity-aware statistical analysis.

Wed 9 SeptData Structures and Algorithms

The gist

Measuring how alike items are is useful but usually takes a lot of memory, especially when items are compared by similarity instead of exact matches. The authors show that when items are vectors in space, using a particular similarity measure called the Gaussian kernel lets you approximate these measures in a single pass using much less memory. This is helpful for streaming data where you see information only once. Their work proves it’s possible and gives practical algorithms with supporting limits on what’s achievable.

Open → 2609.09622v1