Metraipolis › archive › dc_da1601f8f82b

Streaming Algorithms for Gaussian Kernel Density Statistics — arXiv:2609.09622

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.09622
License (as archived)
CC0-1.0
Archived
2026-10-16T11:17:55.712Z
SHA-256 of the archived text
3a1bcd965694edb9b6e95c248348ad1bf0ccbb8f1178895b534115a55b542346
Stable URL of this page
https://metraipolis.com/documento/dc_da1601f8f82b

How to cite

Streaming Algorithms for Gaussian Kernel Density Statistics — arXiv:2609.09622 — arXiv (en), https://arxiv.org/abs/2609.09622 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_da1601f8f82b (Metraipolis archive dc_da1601f8f82b, sha256 3a1bcd965694edb9b6e95c248348ad1bf0ccbb8f1178895b534115a55b542346)
BibTeX
@misc{dcda1601f8f82b,
  title = {Streaming Algorithms for Gaussian Kernel Density Statistics — arXiv:2609.09622},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.09622},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_da1601f8f82b; sha256 3a1bcd965694edb9b6e95c248348ad1bf0ccbb8f1178895b534115a55b542346},
  year = {2026}
}

Archived text

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

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-10 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.09622 — 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-16T10:56:12.717Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).