arXiv preprint ·
Frequency Moments Beyond Equality: Streaming Cosine Density Moments
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler
Sparse Polynomial GCD Algorithms Asymptotically Linear in All Fundamental Parameters
Smoothed Picard Hamiltonian Monte Carlo
Beyond Cut Balance: Spectral Sparsification of the Nonlinear Directed Laplacian
Generalized Graph Search Trees
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.