PaperlayerView exact revision on arXiv

Source-linked AI summary

Streaming Algorithms for Gaussian Kernel Density Statistics

Qin Zhang

arXiv:2609.09622v1cs.DS

TL;DR

For similarity-aware statistics, general similarity functions can require linear space for even coarse one-pass approximation. This paper develops one-pass algorithms and lower bounds for Gaussian-kernel statistics on fixed-dimensional Euclidean streams, showing that sublinear-space approximation is possible in this setting.

  • Problem

    Under general similarity functions, one-pass constant-factor approximation of similarity-aware statistics can require linear space, motivating the question of whether structure in a natural similarity can overcome that barrier.

    Source: §1 · p. 2

  • Method

    The paper uses Gaussian-kernel analytic and geometric structure to approximate the diversity index and density moments in fixed-dimensional streams.

    Source: §1 · pp. 2–3

  • Results

    For fixed-dimensional streams, the paper gives one-pass sublinear-space approximation algorithms for Gaussian-kernel statistics and complements them with lower bounds.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The results show that Gaussian-kernel structure can change the one-pass space complexity of similarity-aware statistical analysis.

    Source: §1 · p. 2

    The upper- and lower-bound exponents remain separated for the diversity index, and a small polynomial gap remains for higher density moments.

    Source: §5 · p. 32

Abstract

from arXiv · show

Motivated by data produced by generative systems, \cite{LZ26b} formulates similarity-aware statistics via a weighted similarity graph, replacing equality with similarity in classical frequency-based statistics. Although this framework captures semantic relationships between nonidentical items, under general similarity functions even coarse one-pass approximation can require linear space. We therefore ask whether the geometric structure present in natural vector similarities can overcome this barrier. We answer this question affirmatively for the Gaussian kernel. For fixed-dimensional Euclidean vector streams, we study similarity-aware analogues of classical frequency statistics, including the number of distinct elements and frequency moments, through the diversity index and Gaussian density moments. We give one-pass sublinear-space approximation algorithms that exploit the geometric and analytic properties of the Gaussian kernel, and complement them with lower bounds. Our results show that geometric structure can fundamentally change the streaming complexity of similarity-aware statistical analysis.

1 Introduction

The introduction motivates replacing exact equality with graded similarity for generative-system data, then studies Gaussian-kernel analogues of distinct-element and frequency-moment statistics. It presents one-pass algorithms and lower bounds for fixed-dimensional streams, and situates this approach among work on classical streaming statistics, similarity graphs, and kernel-density estimation.

1 Introduction

  • The diversity index and density moments generalize classical distinct-element and frequency statistics by replacing exact equality with similarity contributions.Under the equality kernel, the diversity index, first density moment, and p-th density moment reduce to F0, F2, and Fp+1, respectively.Source: §1 · pp. 1–2, §1.1 · p. 3
  • The stream reveals only points, not the complete weighted similarity graph, so algorithms must estimate its global statistics with compact sketches.The graph's vertices are input items and its edge weights are pairwise similarities; constructing or storing it explicitly is ruled out by the streaming setting.Source: §1 · pp. 1–2
  • General similarity functions can require linear space for one-pass constant-factor approximations, whereas Gaussian-kernel structure permits sublinear-space algorithms.The paper attributes its alternative route to the Gaussian kernel's spatial decay and Euclidean geometry, rather than the low-rank Gram structure used for cosine similarity [Zha26].Source: §1 · p. 2
  • For fixed-dimensional streams, the paper gives one-pass approximation algorithms for the diversity index and Gaussian density moments, alongside lower bounds for these statistics.The diversity-index algorithm has polylogarithmic dependence on stream length for fixed d, ϵ, and δ; the first- and higher-moment results also include lower bounds.Source: §1 · p. 3

1.1 Related Work

  • Earlier near-duplicate work studied well-shaped data with threshold graphs close to disjoint unions of cliques, while cosine-similarity work exploited low-rank Gram structure [CZ18] [LZ26a] [Zha26].The Gaussian-kernel results investigate how its analytic and geometric structure changes streaming complexity.Source: §1.1 · p. 4
  • Prior kernel-density work approximates queries, while this paper estimates global aggregates of densities evaluated at the streamed points [PT20, Tai22, CKNS20, CS20].The paper also relates its diversity index to order-zero similarity-sensitive diversity.Source: §1.1 · p. 4

2 Diversity Index

For fixed-dimensional Euclidean streams, this section develops and analyzes a one-pass approximation to the diversity index using Gaussian-kernel geometry, truncated exponential envelopes, and active-cell sampling. It establishes the estimator’s accuracy and space bound, analyzes its sampling variance and streaming implementation, and proves a dimension-dependent space lower bound.

2 Diversity Index

  • A one-pass algorithm approximates DI(P) within (1 + ϵ, δ) for streams of n points in fixed-dimensional Euclidean space.Theorem 2.1 gives the approximation guarantee; the supplied passage does not include the full space bound.Source: §2 · p. 5

2.1 Grid and Cell Densities

  • A sufficiently fine grid makes each occupied cell’s center density a multiplicative approximation to the density of every point in that cell.The resulting cell-based diversity estimate approximates DI(P); occupied cells also satisfy Dg ≥ ng/2 and Di ≤ 2Dg for points in the cell.Source: §2.1 · pp. 6–7

2.2 A Packing Bound for Active Cells

  • The active-cell packing bound gives |A| ≤ β · DI(P), linking the number of relevant grid cells to the diversity index.For β = Cβϵ^-dΓ^2d, this geometric bound is the structural fact underlying the algorithm and its analysis.Source: §2.2 · p. 7

2.3 Exponential Lower Envelopes and Local Updates

  • Exponential lower envelopes estimate reciprocal cell densities, and truncating them at T makes updates local while keeping the estimator’s expected value within (1 ± ϵ/4)DI(P).A point can affect a cell only when its exponential-rank candidate falls below T; with high probability all relevant updates lie within the fixed active radius R∗.Source: §2.3 · pp. 8–10

2.4 Sampling Active Cells

  • Geometric sampling levels select a manageable subset of active cells, and conditional on no dictionary overflow, the scaled sampled estimator is unbiased for Wr.The algorithm estimates the active-set size to choose a sampling level and caps stored sampled cells; the overflow probability is bounded across repetitions.Source: §2.4 · pp. 10–11
  • For each selected level ℓ∗, the sampling estimator satisfies E[(c Wr − µ)^2 | ℓ∗] ≤ 16β · DI(P)^2.Conditioning on the selected level, the bound controls the variance from cell sampling and the randomness of the exponential lower envelope.Source: §2.4 · pp. 11–12

2.5 Pseudocode of the Streaming Algorithm

  • The one-pass grid sketch samples cells at multiple levels, maintains capped dictionaries, and queries an F0 estimate to select a level before applying median-of-means.The query selects the first level with sampling probability at most K0/eU, yielding Θ(K0) expected sampled cells.Source: §2.5 · pp. 12–14

2.6 Proof of Theorem 2.1

  • The estimator achieves a (1 + ϵ)-approximation with failure probability at most δ using ϵ^(-2d-4) log^{O(d)} n words for fixed d.The median-of-means guarantee holds when selected dictionaries do not overflow; the analysis combines this with the other failure probabilities.Source: §2.6 · pp. 14–15

2.7 A Dimension-Dependent Space Lower Bound

  • For every fixed dimension d ≥ 1, any one-pass algorithm on insertion-only streams of at most n points in R^d that outputs a 1.01-approximation to DI(P) with probability at least 2/3 requires at least Ω_d(q) bits.The resulting stream contains q(Nc + 1) points, with Nc = ⌊√n⌋; for fixed d and sufficiently large n, this is at most n.Source: §2.7 · pp. 15, 17, 18

3 First Density Moment

The section develops a one-pass approximation algorithm for the first Gaussian density moment using local features and an ℓ2-norm sketch, then proves a lower bound through a reduction from frequency-moment estimation.

3 First Density Moment

  • A one-pass streaming algorithm outputs a (1 + ϵ, δ)-approximation to the first density moment M1(P).The theorem assumes fixed dimension d.Source: §3 · p. 18
  • Knowing the stream length in advance is not essential; a polynomial upper bound on n suffices without changing the asymptotic space bound.The length enters the feature-map parameters only through logarithmic factors.Source: §3 · p. 18
  • A deterministic local feature map approximates Gaussian similarities while updating only a bounded neighborhood of grid cells, enabling streaming updates.The algorithm uses this map to reduce M1(P) estimation to estimating the squared ℓ2 norm of an implicit aggregate vector with an AMS sketch.Source: §3 · pp. 18, 20
  • The feature approximation and AMS sketch combine to give the stated (1 + ϵ) approximation with probability at least 1 − δ.The AMS estimator uses O(ϵ^-2 log(1/δ)) counters.Source: §3 · p. 20

3.1 Lower Bound

  • For real-line streams in the theorem’s stated accuracy range, a one-pass approximation to M1(P) inherits a lower bound via a reduction from insertion-only F2 estimation.The reduction maps item frequencies to separated Gaussian locations, making same-location pair contributions equal to F2.Source: §3.1 · pp. 21–22

4 Higher Density Moments

This section develops a one-pass, sublinear-space sample-and-probe estimator for higher Gaussian density moments in fixed-dimensional geometry, with variance analysis based on geometric regularity and block sampling that avoids needing the stream length in advance. It also bounds failure in the unknown-length implementation via reservoir-overflow control and proves a one-pass space lower bound through a reduction from frequency moments.

4 Higher Density Moments

  • For fixed integer p > 1 and fixed dimension d, a one-pass streaming algorithm on a stream of n points in R^d produces a (1 + ϵ, δ)-approximation to Mp(P).Source: §4 · p. 22

4.1 Geometric Regularity of Gaussian Densities

  • Gaussian regularity bounds show low-density points contribute limited mass near any query, high-density points have many comparable-density neighbors, and Gaussian overlaps control correlations.These bounds underpin the higher-moment power-sum and correlation analysis.Source: §4.1 · pp. 23–24

4.2 Algorithm and Analysis

  • The estimator samples candidate points and uses p independent probe sets to form unbiased density estimates whose product estimates D_i^p; shared probes create correlations that the geometric bounds control.A variance bound of at most ϵ^2(Mp(P))^2 supports the approximation guarantee.Source: §4.2 · pp. 25, 27

4.3 Removing the Assumption of Known Stream Length

  • When stream length is unknown, dyadic-block reservoir samplers are combined after the stream so that, absent overflow, they produce the independent uniform candidate and probe samples required by the estimator.This modification leaves the estimator and its asymptotic space complexity unchanged.Source: §4.3 · pp. 29–30
  • The unknown-length implementation has overall failure probability at most δ: overflow occurs with probability at most δ/2, and conditional failure without overflow is at most δ/2.When no sample pool overflows, the implementation agrees exactly with the conceptual estimator.Source: §4.3 · p. 31

4.4 Lower Bound

  • Theorem 4.8 gives a one-pass space lower bound for (1 + ε)-approximating M_p on at most n real-line points, for fixed p > 1 and C_p n^-1/(p+1) ≤ ε ≤ 1/20.The algorithm must succeed with probability at least 2/3; the supplied theorem statement does not show the bound's full space expression.Source: §4.4 · pp. 31–32
  • The lower-bound proof maps each frequency item a to coincident Gaussian points at aL, with distinct item locations separated by at least L.The reduction starts from the insertion-only frequency-moment problem and fixes the Gaussian bandwidth to σ = 1.Source: §4.4 · p. 31
  • A (1 + ε)-approximation to M_p would yield a (1 + 2ε)-approximation to F_{p+1}, allowing the classical frequency-moment lower bound to apply.The proof uses constant parallel repetitions to raise success probability to the constant required by that lower bound.Source: §4.4 · p. 32

5 Conclusion

The conclusion summarizes the paper’s algorithms and identifies remaining gaps in the bounds for higher density moments and the diversity index, as well as the broader question of which kernels admit sublinear-space algorithms.

5 Conclusion

  • The paper develops one-pass streaming algorithms for the diversity index and density moments under Gaussian kernel similarity.For higher density moments, a small polynomial gap remains between upper and lower bounds; for the diversity index, the exponents in its upper and lower bounds still differ.Source: §5 · p. 32
  • Characterizing which kernels or geometric similarity functions admit sublinear-space streaming algorithms remains an open direction.Source: §5 · p. 32

Use of AI assistance

The author developed the research and mathematical arguments; ChatGPT was used for language editing, proofreading, and routine algebraic assistance, with the author verifying the resulting text and calculations.

Use of AI assistance

  • The author developed the paper’s research questions, algorithms, proof strategies, and substantive mathematical arguments.ChatGPT assisted with language editing, proofreading, and routine algebraic manipulations; the author verified the text and calculations and takes responsibility for the contents.Source: Use of AI assistance · p. 32

6 Omitted Proofs

The omitted proofs establish a communication lower bound, simplify a Gaussian integral, and bound shifted-lattice sums uniformly over their shift.

6.1 Proof of Lemma 2.10

  • A decoder's error probability at most 1/3 yields an entropy bound, and the message length is at least I(X; M | R).The proof takes X uniform over vectors of Hamming weight m/2 and I uniform in [m], then applies binary Fano's inequality and conditional-entropy bounds.Source: §6.1 · p. 34

6.2 Proof of Lemma 3.2

  • Completing the square leaves an integral independent of x and y, after which the normalizing constants cancel.The remaining integral is evaluated using a change of variables and the standard Gaussian integral.Source: §6.2 · p. 35

6.3 Proof of Claim 3.4

  • Integral comparisons bound shifted-lattice Gaussian sums and their tails beyond L, uniformly over the shift.The comparison uses the even, nonincreasing Gaussian and the spacing h of lattice points.Source: §6.3 · p. 36
Loading 2609.09622v1…