PaperlayerView exact revision on arXiv

Source-linked AI summary

Frequency Moments Beyond Equality: Streaming Cosine Density Moments

Qin Zhang

arXiv:2609.06925v1cs.DS

TL;DR

Classical streaming statistics treat items as equal or different, while vector embeddings have real-valued similarities and general similarity graphs can make one-pass estimation hard. This paper gives one-pass algorithms and dimension-dependent bounds for cosine density moments, using equal-sum moment isolation in its nonnegative-cosine lower-bound construction.

  • Problem

    Classical streaming statistics model items through equality, whereas vector embeddings have real-valued similarity; general similarity functions can also make one-pass density-moment approximation require large space.

    Source: §1 · p. 1

  • Method

    The paper develops one-pass cosine density-moment algorithms and uses equal-sum prefixes whose common vector sum limits the effect of a gadget swap to its internal vector arrangement.

    Source: §2.3 · p. 7, §9 · p. 37

  • Results

    Cosine’s low-rank Gram structure permits dimension-dependent one-pass algorithms; for M−1, constant-relative-error algorithms require Ω(d^2) bits.

    Source: §1 · p. 3, §9 · p. 37

  • Takeaways & Limitations

    The results extend classical frequency moments to cosine similarity and show that its low-rank Gram structure supports dimension-dependent streaming algorithms.

    Source: §9 · p. 37

    For fixed integer p>2, the higher-moment upper and lower dimension exponents remain separated, and optimal dependence on ϵ is open.

    Source: §9 · p. 37

Abstract

from arXiv · show

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.

1 Introduction

The introduction motivates cosine density moments as similarity-aware extensions of frequency moments and presents one-pass algorithms and dimension-dependent space bounds for several moments. Cosine’s Gram structure supports these results, while nonnegative cosine creates a technical challenge for strong lower bounds.

1 Introduction

  • Cosine density moments extend classical frequency moments to real-valued similarity, avoiding explicit clustering or ground-truth assumptions.Under equality, they recover the corresponding frequency moments; cosine density instead aggregates each vector’s similarity to the entire stream.Source: §1 · pp. 1–2
  • One-pass algorithms and space bounds are tight or nearly tight in their polynomial dependence on dimension d for M−1, M1, and Mp with p≥2.The introduction connects these statistics under equality to F0, F2, and Fp+1, respectively.Source: §1 · p. 2
  • Every one-pass algorithm with constant relative error for M−1 requires Ω(d^2) bits, alongside a one-pass (1 + ϵ)-approximation algorithm.The supplied theorem passage does not preserve the upper-bound space expression.Source: §1 · p. 3
  • M1 has an exact O(d)-space algorithm with optimal dimension dependence, while M0 is simply the stream length.Source: §1 · p. 3
  • For even p≥2 under signed cosine, the paper gives a one-pass approximation and a corresponding lower bound, strengthened to Ω(d) bits when p=2.The theorem’s upper- and general lower-bound expressions are truncated in the supplied passages.Source: §1 · p. 3
  • For nonnegative cosine and fixed real p>2, the paper gives a one-pass approximation; for fixed integer p≥3, its lower-bound exponent is less than 1/2 below p/2.Positivity permits arbitrary real exponents, but makes strong lower bounds more difficult.Source: §1 · p. 3

2 Technical Overview

The overview combines streaming upper bounds with INDEX-based lower bounds for cosine-density moments. For nonnegative cosine, equal-sum gadgets and finite differences replace cancellation to isolate higher-moment signals.

2.1 A Map of Upper Bounds

  • For even p = 2k under signed cosine, a lifted AMS sketch estimates the tensorized moment using Op(dp/2ϵ−2) words.The even exponent allows the sketch to work even when individual densities are negative.Source: §2.1 · pp. 4–5
  • The diversity estimator stores each point with probability min{1, λ/Di(t)}, yielding a one-pass O(d2ϵ−2 + d log n)-word upper bound for M−1.Nonnegative cosine makes prefix densities nondecreasing, and the expected number of stored points is at most λM−1(Pt) ≤ λd.Source: §2.1 · p. 5
  • For every fixed real p > 2 under nonnegative cosine, a moment-ratio bound supports uniform sampling and a lifted linear Fp-sketch.The resulting algorithm uses eOp(dp/2ϵ−4+4/p) words; sampled densities are recovered after the final stream sum is known.Source: §2.1 · p. 5

2.2 Geometric Isolation for Lower Bounds

  • INDEX reductions turn a queried bit into a space lower bound, despite Bob’s suffix changing the densities of all earlier vectors.For M−1, a two-block suffix suppresses all but the queried row and tests its coordinate, producing an Ω(d2) lower bound.Source: §2.2 · pp. 5–6

2.3 Equal-Sum Moment Isolation: A Substitute for Cancellation

  • Equal-sum gadgets keep the global vector sum independent of Alice’s bit string, so swapping one gadget leaves densities outside it unchanged.The finite-difference comparison cancels every baseline-containing term and leaves p! hpZp; its zeroth- and first-order identities also give equal cardinality and vector sum.Source: §2.3 · pp. 7–8
  • Local anchors and balancing components realize the algebraic levels with unit vectors while preserving nonnegative pairwise inner products.The common anchor dominates the potentially negative contribution from opposite balancing signs.Source: §2.3 · p. 8
  • For the nonnegative-cosine higher-moment reduction, the queried gadget creates a constant multiplicative gap, yielding an Ωp(dρp)-bit lower bound.The construction has dimension Θ(m), encodes N = Θp(mρp) bits, and uses rational coordinates representable with Op(log d) bits each.Source: §2.3 · p. 10
  • Equal sums control the shared background and finite differences isolate the bit-dependent term, suggesting a modular template for other insertion-only lower bounds.For other objectives, the paired gadgets must make their objective contributions differ sufficiently while keeping the common background controllable.Source: §2.3 · pp. 10–11

3 Preliminaries

The preliminaries define the normalized-vector stream model and distinguish signed from nonnegative cosine. They also specify exponent scope, memory accounting, and conventions used for approximation and lower bounds.

3 Preliminaries

  • The stream algorithm makes one sequential pass over nonzero vectors in Rd and computes the target from its final memory configuration.Each vector is normalized upon arrival; the stream may be written as P = (u1, . . . , un).Source: §3 · p. 11
  • Under nonnegative cosine, every pairwise inner product is nonnegative, so prefix densities satisfy Di(t) ≥ 1 and are nondecreasing.With signed cosine, densities can be zero or negative; inverse moments may be undefined and odd higher moments may be negative or suffer cancellation, so the focus is even p.Source: §3 · p. 11
  • The paper focuses on integer exponents p ≥ −1, with M0 equal to stream length; some nonnegative-cosine results extend to fixed real p > 2.Unless stated otherwise, p is an integer.Source: §3 · p. 11
  • Upper bounds are measured in words, while lower bounds use bits and finite-precision rational coordinates to support information-theoretic arguments.Hard-instance coordinates use Op(log d) bits each; unrestricted real values could encode arbitrarily many bits in one coordinate or memory word.Source: §3 · p. 11
  • For lower bounds, Alice sends one message based on her input to Bob, who must recover the indexed bit; constant-error INDEXN protocols require Ω(N) bits.Algorithms are described with fully random hashes and signs, replaceable by bounded-independence constructions or pseudorandom generators with polylogarithmic overhead and negligible extra error.Source: §3 · pp. 11–12

4 Algebraic Identities and Exact Computation

This section develops algebraic and spectral facts for exact density-moment computation and the diversity–rank principle. It gives a linear-space exact algorithm and matching lower bound for M1, and an exact algorithm for higher integer moments.

4.1 Exact Computation of M1

  • M1(P) equals the squared norm of the normalized-vector sum and can be computed exactly in one pass using O(d) words.Any one-pass algorithm computing M1 exactly requires Ω(d) bits, even for O(d)-length streams of standard basis vectors in the nonnegative-cosine regime.Source: §4.1 · p. 12

4.2 Exact Density Moments

  • For every integer p ≥ 1, Mp(P) can be computed exactly in one pass using O_p(d^p) words.The algorithm maintains degree-p counters in a monomial basis.Source: §4.2 · p. 13

4.3 The Diversity–Rank Principle

  • For a nonnegative-cosine prefix, the diversity–rank argument uses a row-stochastic normalization whose PSD-similar matrix has eigenvalues in [0, 1], including 1.The nonnegative entries and row sums of the normalized matrix bound its eigenvalues; positive semidefiniteness makes them nonnegative.Source: §4.3 · p. 14

5 Diversity Index

For nonnegative cosine, the section gives a one-pass approximation algorithm for the diversity index M−1 and a matching quadratic-in-d lower bound. The lower bound contrasts with an exact two-pass algorithm using O(d) words.

5.1 The Algorithm

  • Algorithm 1 gives a one-pass (1 + ϵ)-approximation to M−1 in the nonnegative-cosine regime with probability at least 1 − δ.It adaptively samples points using inclusion probabilities that decrease as their prefix densities increase; stored contributions support an unbiased estimator.Source: §5.1 · p. 15

5.2 The Lower Bound

  • Any one-pass (1 + ϵ)-approximation for M−1 with constant error in dimension d requires Ω(d^2) bits, even for strictly positive pairwise cosines.The lower bound holds for polynomial-length streams with O(log d)-bit rational coordinates.Source: §5.2 · p. 18
  • The lower-bound construction reduces INDEX to M−1 by appending queried vectors to Alice’s prefix, allowing Bob to recover the queried bit from the estimate.The construction uses a positive shared coordinate so all pairwise cosine similarities are strictly positive.Source: §5.2 · pp. 17, 19
  • Under the nonnegative-cosine promise, M−1 can be computed exactly in two passes using O(d) words.The algorithm stores the vector sum and a scalar counter, in contrast to the Ω(d^2)-bit one-pass lower bound.Source: §5.2 · p. 19

6 Even Density Moments under Signed Cosine

For signed cosine, the section develops one-pass approximation for even density moments and lower bounds on the space needed to estimate them. The tensor–AMS estimator covers even exponents, while the lower bounds establish linear dependence on dimension for M2 and matching polynomial dependence for fixed even p ≥ 4.

6 Even Density Moments under Signed Cosine

  • Even exponents keep M_p nonnegative when densities may have either sign, enabling multiplicative approximation; odd exponents can suffer cancellation.The section therefore focuses on even moments in the signed-cosine regime.Source: §6 · p. 19

6.3 Lower Bounds for Higher Even Moments

  • For every fixed even p ≥ 4, the lower bound matches the upper bound’s polynomial dependence on d.The reduction uses antipodal pairs with zero vector sum and a suffix directed toward a queried codeword; the resulting moment distinguishes membership.Source: §6 · p. 19, §6.3 · pp. 22–23

6.1 A Tensor–AMS Estimator for Even Moments

  • For every even p = 2k, a one-pass tensor–AMS algorithm gives a (1 + ϵ)-approximation to M_p, with repeated sketches controlling variance and failure probability.The estimator represents each contribution as a squared inner product in a lifted tensor space, reducing the problem to estimating a second moment.Source: §6.1 · pp. 19–20

6.2 A Linear Lower Bound for M2

  • M2 requires Ω(d) bits even for nonnegative-cosine streams of length O(d) with O(log d)-bit rational inputs.A Hadamard-based suffix of orthonormal vectors keeps pairwise inner products nonnegative and makes the queried bit distinguishable through the moment estimate.Source: §6.2 · pp. 20–22

7 Higher Density Moments under Nonnegative Cosine: Upper Bound

For nonnegative cosine and fixed real p > 2, the section gives a one-pass approximation algorithm for higher density moments. It combines uniform sampling of density coordinates with a linear F_p sketch maintained without storing the sampled vectors.

7 Higher Density Moments under Nonnegative Cosine: Upper Bound

  • A moment-ratio bound makes uniform sampling of roughly d^(p/2) density coordinates sufficient for estimating M_p.Nonnegativity keeps densities positive and supports the moment-ratio bound used for sampling.Source: §7 · p. 24
  • A linear F_p sketch of the sampled density vector can be maintained without storing the sampled vectors themselves.Each scalar sketch counter is lifted to a d-dimensional vector, allowing the sketch to be recovered once the final stream sum is known.Source: §7 · p. 26
  • For every fixed real p > 2, a one-pass algorithm gives a (1 + ϵ)-approximation to M_p in the nonnegative-cosine regime.The algorithm supports confidence 1 − δ through independent repetitions and median aggregation.Source: §7 · p. 27

8 Higher Density Moments under Nonnegative Cosine: Lower Bound

This section proves a dimension-dependent, superlinear streaming space lower bound for approximating higher density moments under pairwise nonnegative cosine similarities. Its reduction uses sparse nonnegative codewords, equal-sum gadgets, and finite differences to isolate the queried signal, with finite-precision rationalization preserving positive similarities and the approximation gap.

8 Higher Density Moments under Nonnegative Cosine: Lower Bound

  • Ω_p(d^rho_p) bits are required for a one-pass 1/3-error (1 + epsilon_p)-approximation to M_p, where rho_p = p^2(p−1)/(2(p^2−2)).This holds for every fixed integer p > 2 and sufficiently large d, even for polynomial-length streams with coordinates representable in O_p(log d) bits.Source: §8 · p. 27

8.1 Notation and Parameters

  • The construction encodes N = c_N m^rho_p bits in a 4m-dimensional space before a one-dimensional precision perturbation, using mutually orthogonal code, anchor, and balancing blocks.The proof also defines p+1 coefficient levels and a suffix amplitude Q = L√m.Source: §8.1 · p. 28

8.2 A Sparse Nonnegative Code

  • The sparse-code lemma constructs N distinct nonnegative unit codewords with bounded first- and pth-power row sums, including normalized incidence vectors of s-subsets.The stated range is m < N = o(m^(p/2)); the row-sum bounds are used to control interference in the reduction.Source: §8.2 · pp. 28–29

8.3 The Finite-Difference Construction

  • Finite-difference coefficients cancel every power below p in (B + t_j Z)^r, while the pth-order response is p! h^p Z^p.The level spacing is h, and the identity holds for every B, Z and integer 0 ≤ r ≤ p.Source: §8.3 · p. 29, §8.4 · p. 30

8.4 Local Anchors and Nonnegative Geometry

  • The two unit-vector gadgets have nonnegative pairwise inner products and a common vector sum, so their difference cancels the local-anchor baseline and isolates κ_p Z_i^p.The isolated coefficient is κ_p = 2p! h^p.Source: §8.4 · pp. 30–31

8.5 The Hard Input

  • Alice’s INDEX prefix has a vector sum independent of her bits, and Bob’s suffix preserves nonnegative cosine while adding a queried code response and controlled nonqueried responses.The nonqueried responses are noise governed by the sparse-code properties.Source: §8.5 · pp. 31–32

8.6 Moment Upper Bounds

  • For any ν > 0, parameters can make total nonqueried code-response contribution at most νQ^p, while the all-zero baseline satisfies 0 ≤ V0(q) ≤ C_V Q^p.The sparse-code parameter ι is chosen first, followed by c_N in N = c_N m^rho_p.Source: §8.6 · p. 33
  • For p > 2, suffix vectors contribute O(Q^p) to the moment, and combining prefix and suffix contributions proves the moment upper-bound lemma.Source: §8.6 · p. 34

8.7 The Reduction

  • The constructed moment equals baseline V0(q) plus an independent contribution from each set bit; gadget replacements preserve the stream sum and other vectors’ densities.Replacing a zero-gadget with a one-gadget changes the moment by the gadget’s contribution.Source: §8.7 · p. 34
  • A (1 + epsilon_p)-approximation of M_p lets Bob recover z_q, implying an Ω_p(d^rho_p)-bit streaming lower bound for fixed p.The reduction has constant success probability.Source: §8.7 · p. 35

8.8 Finite Precision

  • Exact rational unit vectors with O_p(log m)-bit coordinates preserve strictly positive pairwise similarities and a constant approximation gap.Perturbation and rationalization leave the approximation intervals for the two cases disjoint.Source: §8.8 · pp. 36–37

9 Conclusion

Cosine density moments extend classical frequency moments to vector data, and the low-rank Gram structure permits dimension-dependent streaming algorithms. For fixed integers p>2 under nonnegative cosine, the optimal complexity remains unresolved.

9 Conclusion

  • The low-rank Gram structure of cosine similarity permits dimension-dependent streaming algorithms, extending classical frequency moments to vector data.These algorithms address a setting where general similarity graphs admit strong space lower bounds.Source: §9 · p. 37
  • For fixed integer p>2 under nonnegative cosine, the upper and lower bounds have different dimension exponents, leaving the optimal complexity open.The optimal dependence on epsilon also remains open.Source: §9 · p. 37

Use of AI assistance

The author developed the paper’s research and mathematical arguments, with AI assistance for language editing, proofreading, parameter optimization, and routine algebra.

Use of AI assistance

  • The author developed the research questions, algorithms, proof strategies, and substantive mathematical arguments.The author takes full responsibility for the paper’s contents.Source: Use of AI assistance · p. 37
  • ChatGPT (GPT-5.5 and GPT-5.6) assisted with language editing and proofreading.Source: Use of AI assistance · p. 37
  • ChatGPT also assisted with parameter optimization in gadget constructions and routine algebraic manipulation; the author verified the resulting text and calculations.Source: Use of AI assistance · p. 37

A Math Tools

The appendix states Bernstein’s inequality for independent, bounded, mean-zero random variables and notes a one-sided simplification.

A Math Tools

  • Bernstein’s inequality is stated for independent, mean-zero random variables bounded in absolute value by b.Source: A Math Tools · p. 39
  • The appendix introduces sigma squared as a quantity associated with the random variables, but the supplied passage does not give its full definition.Source: A Math Tools · p. 39
  • For every x>0, the appendix gives a specialization of the inequality, and a one-sided application can omit the leading factor 2.Source: A Math Tools · p. 39

B.1 A Sparse-Intersection Moment Bound

For independent uniform s-subsets A and B of [m], the intersection size X has a p-th moment bounded by C_p s^2/m when m ≥ 2p and s^2/m ≤ 1. The proof bounds its falling-factorial moments and converts them to ordinary moments.

B.1 A Sparse-Intersection Moment Bound

  • E[X^p] ≤ C_p s^2/m when m ≥ 2p and s^2/m ≤ 1, with C_p depending only on p.Here X = |A ∩ B| for independent uniform s-subsets A and B of [m].Source: §B.1 · p. 40
  • Independence of A and B is used to compute the factorial moments of their intersection size.The proof counts ordered distinct tuples and uses independence for the probability that a fixed tuple lies in both subsets.Source: §B.1 · p. 40
  • The proof bounds E[(X)_r] by 2^r s^2/m for each 1 ≤ r ≤ p, then substitutes these bounds into the falling-factorial expansion of X^p.(X)_r counts ordered r-tuples of distinct elements in A ∩ B.Source: §B.1 · p. 40

B.2 Proof of Lemma 8.3

The proof uses iterated forward differences to remove lower-degree polynomial terms and retain the degree-p contribution. Applied to (B + tZ)^r, this annihilates terms for r < p and extracts the leading coefficient when r = p.

B.2 Proof of Lemma 8.3

  • Applying the forward-difference operator p times lowers polynomial degree by p and maps t^p to p! h^p.For a degree-k polynomial, each application lowers the degree by one and multiplies its leading coefficient by k h.Source: §B.2 · p. 41
  • For f_r(t) = (B + tZ)^r with r < p, the p-fold forward difference vanishes because f_r has degree less than p..Source: §B.2 · p. 41
  • When r = p, the leading coefficient of (B + tZ)^p is Z^p, so the p-fold difference isolates that term from the lower-degree terms.The proof combines this case with the vanishing for r < p to establish the lemma.Source: §B.2 · p. 41
Loading 2609.06925v1…