Metraipolis › archive › dc_193fdceed525

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-03T08:23:44.596Z
SHA-256 of the archived text
568eb827ffe88ecb07931637c1f78a75f53be72af2ee9b310df85520b8ee1e1e
Stable URL of this page
https://metraipolis.com/documento/dc_193fdceed525

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_193fdceed525 (Metraipolis archive dc_193fdceed525, sha256 568eb827ffe88ecb07931637c1f78a75f53be72af2ee9b310df85520b8ee1e1e)
BibTeX
@misc{dc193fdceed525,
  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_193fdceed525; sha256 568eb827ffe88ecb07931637c1f78a75f53be72af2ee9b310df85520b8ee1e1e},
  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-03T08:07:08.783Z dalla pagina https://arxiv.org/list/cs.DB/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).