Seminaive Materialisation in DatalogMTL

• URL: http://arxiv.org/abs/2208.07100v1
• Date: Mon, 15 Aug 2022 10:04:44 GMT
• Title: Seminaive Materialisation in DatalogMTL
• Authors: Dingmin Wang, Przemys{\l}aw Andrzej Wa{\l}\k{e}ga, and Bernardo Cuenca Grau
• Abstract summary: DatalogMTL is an extension of Datalog with metric temporal operators. We propose a materialisation-based procedure to minimise redundant computation. Our experiments show that our optimised seminaive strategy for DatalogMTL is able to significantly reduce materialisation times.
• Score: 10.850687097496373
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: DatalogMTL is an extension of Datalog with metric temporal operators that has found applications in temporal ontology-based data access and query answering, as well as in stream reasoning. Practical algorithms for DatalogMTL are reliant on materialisation-based reasoning, where temporal facts are derived in a forward chaining manner in successive rounds of rule applications. Current materialisation-based procedures are, however, based on a naive evaluation strategy, where the main source of inefficiency stems from redundant computations. In this paper, we propose a materialisation-based procedure which, analogously to the classical seminaive algorithm in Datalog, aims at minimising redundant computation by ensuring that each temporal rule instance is considered at most once during the execution of the algorithm. Our experiments show that our optimised seminaive strategy for DatalogMTL is able to significantly reduce materialisation times.

Related papers

• Score-matching-based Structure Learning for Temporal Data on Networks [17.166362605356074]
  Causal discovery is a crucial initial step in establishing causality from empirical data and background knowledge. Current score-matching-based algorithms are primarily designed to analyze independent and identically distributed (i.i.d.) data. We have developed a new parent-finding subroutine for leaf nodes in DAGs, significantly accelerating the most time-consuming part of the process: the pruning step.
  arXiv  Detail & Related papers  (2024-12-10T12:36:35Z)
• Goal-Driven Reasoning in DatalogMTL with Magic Sets [4.885086628404422]
  DatalogMTL is a powerful rule-based language for temporal reasoning. We introduce a new reasoning method for DatalogMTL which exploits the magic sets technique. We implement this approach and evaluate it on several publicly available benchmarks.
  arXiv  Detail & Related papers  (2024-12-10T07:40:37Z)
• Learning Temporal Logic Predicates from Data with Statistical Guarantees [0.0]
  We present a novel method to learn temporal logic predicates from data with finite-sample correctness guarantees. Our approach leverages expression optimization and conformal prediction to learn predicates that correctly describe future trajectories.
  arXiv  Detail & Related papers  (2024-06-15T00:07:36Z)
• Minimally Supervised Learning using Topological Projections in Self-Organizing Maps [55.31182147885694]
  We introduce a semi-supervised learning approach based on topological projections in self-organizing maps (SOMs) Our proposed method first trains SOMs on unlabeled data and then a minimal number of available labeled data points are assigned to key best matching units (BMU) Our results indicate that the proposed minimally supervised model significantly outperforms traditional regression techniques.
  arXiv  Detail & Related papers  (2024-01-12T22:51:48Z)
• Large-Scale OD Matrix Estimation with A Deep Learning Method [70.78575952309023]
  The proposed method integrates deep learning and numerical optimization algorithms to infer matrix structure and guide numerical optimization. We conducted tests to demonstrate the good generalization performance of our method on a large-scale synthetic dataset.
  arXiv  Detail & Related papers  (2023-10-09T14:30:06Z)
• Enhancing Datalog Reasoning with Hypertree Decompositions [17.868595375154506]
  We provide algorithms that exploit hypertree decompositions for the materialisation and incremental evaluation of Datalog programs. We combine this approach with standard Datalog reasoning algorithms in a modular fashion so that the overhead caused by the decompositions is reduced.
  arXiv  Detail & Related papers  (2023-05-11T14:51:16Z)
• Dynamic Scheduling for Federated Edge Learning with Streaming Data [56.91063444859008]
  We consider a Federated Edge Learning (FEEL) system where training data are randomly generated over time at a set of distributed edge devices with long-term energy constraints. Due to limited communication resources and latency requirements, only a subset of devices is scheduled for participating in the local training process in every iteration.
  arXiv  Detail & Related papers  (2023-05-02T07:41:16Z)
• Linear Temporal Logic Modulo Theories over Finite Traces (Extended Version) [72.38188258853155]
  This paper studies Linear Temporal Logic over Finite Traces (LTLf) proposition letters are replaced with first-order formulas interpreted over arbitrary theories. The resulting logic, called Satisfiability Modulo Theories (LTLfMT), is semi-decidable.
  arXiv  Detail & Related papers  (2022-04-28T17:57:33Z)
• MeTeoR: Practical Reasoning in Datalog with Metric Temporal Operators [12.145849273069627]
  We present a novel approach for practical reasoning in DatalogMTL which combines materialisation (a.k.a. forward chaining) with automata-based techniques. MeTeoR is a scalable system which enables reasoning over complex temporal rules and involving datasets of millions of temporal facts.
  arXiv  Detail & Related papers  (2022-01-12T17:46:18Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• Improving a State-of-the-Art Heuristic for the Minimum Latency Problem with Data Mining [69.00394670035747]
  Hybrid metaheuristics have become a trend in operations research. A successful example combines the Greedy Randomized Adaptive Search Procedures (GRASP) and data mining techniques.
  arXiv  Detail & Related papers  (2019-08-28T13:12:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.