LMKG: Learned Models for Cardinality Estimation in Knowledge Graphs
arXiv:2102.10588
Abstract
Accurate cardinality estimates are a key ingredient to achieve optimal query plans. For RDF engines, specifically under common knowledge graph processing workloads, the lack of schema, correlated predicates, and various types of queries involving multiple joins, render cardinality estimation a particularly challenging task. In this paper, we develop a framework, termed LMKG, that adopts deep learning approaches for effectively estimating the cardinality of queries over RDF graphs. We employ both supervised (i.e., deep neural networks) and unsupervised (i.e., autoregressive models) approaches that adapt to the subgraph patterns and produce more accurate cardinality estimates. To feed the underlying data to the models, we put forward a novel encoding that represents the queries as subgraph patterns. Through extensive experiments on both real-world and synthetic datasets, we evaluate our models and show that they overall outperform the state-of-the-art approaches in terms of accuracy and execution time.
12 pages, 11 figures, 2 tables
References in corpus (13)
- Inductive Representation Learning on Large Graphs
- A Survey on Knowledge Graphs: Representation, Acquisition and Applications
- Neo: A Learned Query Optimizer
- Deep Unsupervised Cardinality Estimation
- Learned Cardinalities: Estimating Correlated Joins with Deep Learning
- Learning to Optimize Join Queries With Deep Reinforcement Learning
- MolecularRNN: Generating realistic molecular graphs with optimized properties
- Towards a Hands-Free Query Optimizer through Deep Learning
- Estimating the Cardinality of Conjunctive Queries over RDF Data Using Graph Summarisation
- NeuroCard: One Cardinality Estimator for All Tables
- An Empirical Analysis of Deep Learning for Cardinality Estimation
- Improved Cardinality Estimation by Learning Queries Containment Rates
- PRESTO: Probabilistic Cardinality Estimation for RDF Queries Based on Subgraph Overlapping