Streaming algorithms extend vector similarity metrics beyond equality counts
Frequency Moments Beyond Equality: Streaming Cosine Density Moments
Data Structures and Algorithms
Summary
When comparing many vectors, it's helpful to know how similar each one is to all the others. Previous methods focused only on counting exact matches, but this paper studies a way to measure similarity using cosine similarity, which captures angle-based closeness. The authors develop streaming algorithms that can calculate these similarity measures efficiently as new vectors arrive, using limited memory. They also prove theoretical limits on how well these calculations can be done, providing a new framework to handle challenging cases when vectors aren't just opposites.
What this means in practice
- •For machine learning engineers: Compute similarity-aware statistics over large embedding streams using low-memory passes to help monitor or summarize model outputs.
- •For database system developers: Implement streaming algorithms that efficiently maintain similarity-based metrics for high-dimensional data without storing all vectors.
Authors
Qin Zhang
Abstract
For a stream of nonzero vectors $x_1,\ldots,x_n\in\mathbb{R}^d$, let $u_i=x_i/\|x_i\|_2$. We define the cosine density of the $i$-th stream element by $D_i:=\sum_{j\in[n]}\langle u_i,u_j\rangle$ and study the density moments $M_p:=\sum_{i\in[n]}D_i^p$ in both the signed- and nonnegative-cosine regimes. These quantities are similarity-aware analogues of classical frequency moments: replacing cosine similarity by equality (that is, $D_i = \sum_{j\in[n]} \mathbf{1}\{u_j = u_i\}$) gives $M_p=F_{p+1}$ and, in particular, $M_{-1}=F_0$, the number of distinct elements. We give one-pass streaming algorithms and lower bounds that are tight or nearly tight in their dependence on the dimension $d$. Our results thus extend several fundamental statistics from the classical data stream literature to cosine similarity, a widely used measure for comparing vector embeddings in modern AI systems. The main challenge in proving a space lower bound for nonnegative cosine is to eliminate unwanted contributions without relying on pairs of opposite vectors. We address this through a construction that we call \emph{equal-sum moment isolation}: two insertion-only prefixes have the same cardinality and vector sum, and a finite-difference comparison cancels their common baseline while isolating the desired higher-order signal. This proof framework may be useful for other insertion-only streaming lower bounds, where direct cancellation is not possible.