Metraipolis › archive › dc_a5b93f1d3dfd

Uplifting the Superpowers of Worst-Case-Optimal Join Algorithms — arXiv:2608.03840

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.03840
License (as archived)
CC0-1.0
Archived
2026-10-31T13:08:36.650Z
SHA-256 of the archived text
e8065b26653ef5bbb1f36430091471a5503f85ad6b452a3856d9456c67950d07
Stable URL of this page
https://metraipolis.com/documento/dc_a5b93f1d3dfd

How to cite

Uplifting the Superpowers of Worst-Case-Optimal Join Algorithms — arXiv:2608.03840 — arXiv (en), https://arxiv.org/abs/2608.03840 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a5b93f1d3dfd (Metraipolis archive dc_a5b93f1d3dfd, sha256 e8065b26653ef5bbb1f36430091471a5503f85ad6b452a3856d9456c67950d07)
BibTeX
@misc{dca5b93f1d3dfd,
  title = {Uplifting the Superpowers of Worst-Case-Optimal Join Algorithms — arXiv:2608.03840},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.03840},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a5b93f1d3dfd; sha256 e8065b26653ef5bbb1f36430091471a5503f85ad6b452a3856d9456c67950d07},
  year = {2026}
}

Archived text

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

Worst-case-optimal (wco) join algorithms have demonstrated their power -- in both theory and practice -- to efficiently solve complex Basic Graph Patterns (BGPs). Modern graph query languages, such as SPARQL and GQL, have BGPs at their core, but also have a wide range of other features, including filters (aka.\ selections). Such conditions are typically handled via pre- or post-filtering, before or after processing the BGPs. In this paper we show how to uplift wco join algorithms so as to incorporate such filtering natively, improving efficiency. We demonstrate the superiority of this approach by extending the \textit{Ring} -- a compact index that provides wco resolution of BGPs within almost no extra space on top of the graph -- so as to handle property graphs using our new techniques while retaining compactness. We implement this extension and experimentally show that it outperforms various baseline systems.

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