Metraipolis › archive › dc_9537cb4eb652

Frequency Moments Beyond Equality: Streaming Cosine Density Moments — arXiv:2609.06925

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.06925
License (as archived): CC0-1.0
Archived: 2026-10-16T15:31:49.599Z
SHA-256 of the archived text: a1d11c9a869776edc74c95367f05ebbe8226814fa76a0dd025b5da6e2d9fa943
Stable URL of this page: https://metraipolis.com/documento/dc_9537cb4eb652

How to cite

Frequency Moments Beyond Equality: Streaming Cosine Density Moments — arXiv:2609.06925 — arXiv (en), https://arxiv.org/abs/2609.06925 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9537cb4eb652 (Metraipolis archive dc_9537cb4eb652, sha256 a1d11c9a869776edc74c95367f05ebbe8226814fa76a0dd025b5da6e2d9fa943)

BibTeX

@misc{dc9537cb4eb652,
  title = {Frequency Moments Beyond Equality: Streaming Cosine Density Moments — arXiv:2609.06925},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.06925},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9537cb4eb652; sha256 a1d11c9a869776edc74c95367f05ebbe8226814fa76a0dd025b5da6e2d9fa943},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06925. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.06925 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T15:15:08.340Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).