Supervised and LLM-Augmented Cardinality Estimation for Similarity Queries on Knowledge Graphs

原文：Supervised and LLM-Augmented Cardinality Estimation for Similarity Queries on Knowledge Graphs

作者：Georgios Chatzigeorgakidis, Dimitrios Skoutas, Alkis Simitsis

来源：arXiv cs.DB（数据库）

正文

Computer Science > Databases

arXiv:2610.41669v1 (cs)

[Submitted on 30 Oct 2026]

Title:Supervised and LLM-Augmented Cardinality Estimation for Similarity Queries on Knowledge Graphs

Authors:Georgios Chatzigeorgakidis, Dimitrios Skoutas, Alkis Simitsis

View a PDF of the paper titled Supervised and LLM-Augmented Cardinality Estimation for Similarity Queries on Knowledge Graphs, by Georgios Chatzigeorgakidis and 2 other authors

View PDF

HTML (experimental)

Abstract: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.

Subjects:

Databases (cs.DB)

Cite as:

arXiv:2610.41669 [cs.DB]

(or

arXiv:2610.41669v1 [cs.DB] for this version)

https://doi.org/10.48550/arXiv.2610.41669

Focus to learn more

arXiv-issued DOI via DataCite (pending registration)

主题

数据库

由「前沿雷达」于 2026-10-30 采集。正文取自原文页面，已保留出处链接。标题与正文版权归原作者所有。