Metraipolis › archive › dc_18f2baf7bbdc

TreeRedux: Separating Concerns in Spark's Distributed Tree Aggregation — arXiv:2609.06982

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.06982
License (as archived)
CC0-1.0
Archived
2026-10-16T13:07:14.328Z
SHA-256 of the archived text
6778a41715a0c7d1e59f179ff3d7aa56bd3c3014cf8bb5ab1a635037d08e7cc1
Stable URL of this page
https://metraipolis.com/documento/dc_18f2baf7bbdc

How to cite

TreeRedux: Separating Concerns in Spark's Distributed Tree Aggregation — arXiv:2609.06982 — arXiv (en), https://arxiv.org/abs/2609.06982 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_18f2baf7bbdc (Metraipolis archive dc_18f2baf7bbdc, sha256 6778a41715a0c7d1e59f179ff3d7aa56bd3c3014cf8bb5ab1a635037d08e7cc1)
BibTeX
@misc{dc18f2baf7bbdc,
  title = {TreeRedux: Separating Concerns in Spark's Distributed Tree Aggregation — arXiv:2609.06982},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.06982},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_18f2baf7bbdc; sha256 6778a41715a0c7d1e59f179ff3d7aa56bd3c3014cf8bb5ab1a635037d08e7cc1},
  year = {2026}
}

Archived text

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

By default, Apache Spark's tree aggregation primitives place the tree root on the driver, requiring the driver to participate in the same aggregation computation over intermediate aggregation state as executor nodes. For large aggregates, this can expose the single coordinator to substantial computation and memory requirements. Recent Spark versions optionally move the root to an executor, but the completed aggregate must still be returned to and materialized on the driver. We demonstrate this limitation using exact quantile computation and heavy-hitter identification, where the intermediate aggregation state can be substantially larger than the desired final result. We propose TreeRedux, a minimal extension that adds a terminal finalize operation, executed on an executor, that maps the aggregation state U to a compact result V, so that V rather than the potentially large U is materialized on the driver. For exact quantile computation, applying TreeRedux to GK Select removes the driver's epsilon-n memory term, reducing driver memory requirements to the same asymptotic order as Spark's GK Sketch. In our experiments, the default GK Select implementation encountered a driver out-of-memory error at 2.5 billion elements. Spark's executor-side final aggregation option extended this limit to approximately 16-18 billion elements but still required the final aggregation state to be materialized on the driver. Redux Select completed through 28 billion elements without a driver out-of-memory error. TreeRedux allowed Space-Saving sketches with up to 32x the capacity of the largest configuration that materializes a full sketch on the driver.

Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-09 in cs.DC).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2609.06982 — 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-16T13:02:21.572Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).