Efficient Query Processing for Dynamically Changing Datasets.

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Muhammad Idris - , Université libre de Bruxelles (ULB) (Author)
  • Martín Ugarte - , Pontificia Universidad Católica de Chile (Author)
  • Stijn Vansummeren - , Université libre de Bruxelles (ULB) (Author)
  • Hannes Voigt - , Neo4j, Inc. (Author)
  • Wolfgang Lehner - , TUD Dresden University of Technology (Author)

Abstract

The ability to efficiently analyze changing data is a key requirement of many real-time analytics applications. Traditional approaches to this problem were developed around the notion of Incremental View Maintenance (IVM), and are based either on the materialization of subresults (to avoid their recomputation) or on the recomputation of subresults (to avoid the space overhead of materialization). Both techniques are suboptimal: Instead of materializing results and subresults, one may also maintain a data structure that supports efficient maintenance under updates and from which the full query result can quickly be enumerated. In two previous articles, we have presented algorithms for dynamically evaluating queries that are easy to implement, efficient, and can be naturally extended to evaluate queries from a wide range of application domains. In this paper, we discuss our algorithm and its complexity, explaining the main components behind its efficiency. Finally, we show experiments that compare our algorithm to a state-of-the-art (Higher-order) IVM engine, as well as to a prominent complex event recognition engine. Our approach outperforms the competitor systems by up to two orders of magnitude in processing time, and one order in memory consumption.

Details

Original languageEnglish
Article number1
Pages (from-to)33-40
Number of pages8
JournalSIGMOD record
Volume48
Issue number1
Publication statusPublished - Mar 2019
Peer-reviewedYes
Externally publishedYes

External IDs

Scopus 85074859062
ORCID /0000-0001-8107-2775/work/142253462

Keywords

ASJC Scopus subject areas