Frequency Moments Beyond Equality: Streaming Cosine Density Moments

Abstract

For a stream of nonzero vectors $x_1,\dots ,x_n\in {\mathbb{R}}^d$, let $u_i=x_i/\Vert x_i{\Vert }_2$. We define the cosine density of the $i$-th stream element by $D_i:={\sum }_{j\in [n]}⟨u_i,u_j⟩$ 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]}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.

arXiv comment41 pages