Metraipolis › archive › dc_eea197848145

Scalable Triangle Counting: The Threshold Algorithm — arXiv:2609.15848

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.15848
License (as archived): CC0-1.0
Archived: 2026-10-16T02:15:14.849Z
SHA-256 of the archived text: 119444986cfc9b150e967df1bdf6dd7631e857d712f7d6ad416d5bc71005fa00
Stable URL of this page: https://metraipolis.com/documento/dc_eea197848145

How to cite

Scalable Triangle Counting: The Threshold Algorithm — arXiv:2609.15848 — arXiv (en), https://arxiv.org/abs/2609.15848 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_eea197848145 (Metraipolis archive dc_eea197848145, sha256 119444986cfc9b150e967df1bdf6dd7631e857d712f7d6ad416d5bc71005fa00)

BibTeX

@misc{dceea197848145,
  title = {Scalable Triangle Counting: The Threshold Algorithm — arXiv:2609.15848},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.15848},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_eea197848145; sha256 119444986cfc9b150e967df1bdf6dd7631e857d712f7d6ad416d5bc71005fa00},
  year = {2026}
}

Archived text

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

We study one-pass triangle counting on random-order edge streams. We present a remarkably simple algorithm---read edges from the stream until $Q$ triangles are observed in the prefix, then output $Q\,(m/S)^3$ where $S$ is the stopping length---and prove that, when the maximum number of triangles incident to any edge satisfies $\eta \le T^{2/3}$, this is a $(1\pm\varepsilon)$-approximation of $T$ with probability $1-\delta$ using $O(\varepsilon^{-2}\log(1/\delta)\, m/T^{1/3})$ memory. Crucially, the algorithm does not need any a priori estimate of $T$, in sharp contrast with state-of-the-art sampling-rate based algorithms (McGregor and Vorotnikova, PODS 2020; Tsourakakis et al., KDD 2009). It also does not need a prescribed memory budget: the stopping rule self-selects the prefix length and can return an estimate before reading the entire stream. The proof rests on a Schudy--Sviridenko concentration argument for an independent-edge-sampling estimator, coupled to the without-replacement prefix produced by the algorithm. On six real temporal streams, the algorithm's stopping prefix follows the predicted cube-root scaling and achieves at most $6\%$ error at a $10\%$ prefix, without using $T$. At a fixed stored-edge budget, variance-reduced reservoir samplers are often more accurate, but only after reading the entire stream. On a separate, much larger, $1.8\times10^9$-edge graph, the threshold algorithm reads $0.46\%$ of the stream and returns $3.8\%$ error, while the strongest reservoir baselines do not finish a pass within the wall-clock cap.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-15 in cs.DB).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2609.15848 — 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-16T01:53:21.338Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).