Metraipolis › archive › dc_7f7987df640f

Supervised and LLM-Augmented Cardinality Estimation for Similarity Queries on Knowledge Graphs — arXiv:2610.41669

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41669
License (as archived)
CC0-1.0
Archived
2026-11-03T05:48:25.611Z
SHA-256 of the archived text
6f49e7b681b6a8e0f6a9c6bd8ab4308d00783a98dc5ad770f1dd469b63b58720
Stable URL of this page
https://metraipolis.com/documento/dc_7f7987df640f

How to cite

Supervised and LLM-Augmented Cardinality Estimation for Similarity Queries on Knowledge Graphs — arXiv:2610.41669 — arXiv (en), https://arxiv.org/abs/2610.41669 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7f7987df640f (Metraipolis archive dc_7f7987df640f, sha256 6f49e7b681b6a8e0f6a9c6bd8ab4308d00783a98dc5ad770f1dd469b63b58720)
BibTeX
@misc{dc7f7987df640f,
  title = {Supervised and LLM-Augmented Cardinality Estimation for Similarity Queries on Knowledge Graphs — arXiv:2610.41669},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41669},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7f7987df640f; sha256 6f49e7b681b6a8e0f6a9c6bd8ab4308d00783a98dc5ad770f1dd469b63b58720},
  year = {2026}
}

Archived text

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

Over the past decades, query cardinality estimation on relational databases has been proven crucial, enabling the result size estimation of all sub-plans of each query. This allowed query optimizers to design efficient query plans, towards minimizing the query response time. Lately, knowledge graphs are being preferred over traditional databases in various applications, due to their ability to represent complex relationships and semantic meaning in a domain-specific context. In this work, we present a novel approach for supervised similarity-aware cardinality estimation on knowledge graphs that incorporates similarities into the model training process, thus treating them as first-class citizens. To this end, we present SCE-KG, a model that employs a novel encoding scheme for cardinality estimation, named SGsplit. We further extend our approach by leveraging a Large Language Model (LLM) to generate training queries that resemble realistic user workloads, and show that combining LLM-generated and random walk samples consistently improves estimation accuracy on test workloads generated by two independent LLMs. Our experimental evaluation reveals that our approach outperforms the state-of-the-art techniques in terms of prediction error, achieving 40x and 37x improvement for star and chain queries, respectively (95th percentile), whereas its online overhead accounts for less than 0.05% of the average query execution time and less than 1% of the average query planning time, showing a sub-millisecond latency in all cases.

Tema degli esploratori: statistica e scienza dei dati (elenco arXiv cs.DB, nuovi lavori del giorno).
Categorie arXiv: Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2610.41669 — 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-11-03T05:34:02.484Z dalla pagina https://arxiv.org/list/cs.DB/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).