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

• 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)
• Synthesizing Efficiently Monitorable Formulas in Metric Temporal Logic [4.60607942851373]
  We consider the problem of automatically synthesizing formal specifications from system executions. Most of the classical approaches for synthesizing temporal logic formulas aim at minimizing the size of the formula. We formalize this notion and devise a learning algorithm that synthesizes concise formulas having bounded lookahead.
  arXiv  Detail & Related papers  (2023-10-26T14:13:15Z)
• 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)
• Uncertainty-Aware Signal Temporal logic [21.626420725274208]
  Existing temporal logic inference methods mostly neglect uncertainties in the data. We propose two uncertainty-aware signal temporal logic (STL) inference approaches to classify the undesired behaviors and desired behaviors of a system.
  arXiv  Detail & Related papers  (2021-05-24T21:26:57Z)
• 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.