StreamQRE: modular specification and efficient evaluation of quantitative queries over streaming data
Open Access
- 14 June 2017
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 52 (6) , 693-708
Abstract
Real-time decision making in emerging IoT applications typically relies on computing quantitative summaries of large data streams in an efficient and incremental manner. To simplify the task of programming the desired logic, we propose StreamQRE, which provides natural and high-level constructs for processing streaming data. Our language has a novel integration of linguistic constructs from two distinct programming paradigms: streaming extensions of relational query languages and quantitative extensions of regular expressions. The former allows the programmer to employ relational constructs to partition the input data by keys and to integrate data streams from different sources, while the latter can be used to exploit the logical hierarchy in the input stream for modular specifications. We first present the core language with a small set of combinators, formal semantics, and a decidable type system. We then show how to express a number of common patterns with illustrative examples. Our compilation algorithm translates the high-level query into a streaming algorithm with precise complexity bounds on per-item processing time and total memory footprint. We also show how to integrate approximation algorithms into our framework. We report on an implementation in Java, and evaluate it with respect to existing high-performance engines for processing streaming data. Our experimental evaluation shows that (1) StreamQRE allows more natural and succinct specification of queries compared to existing frameworks, (2) the throughput of our implementation is higher than comparable systems (for example, two-to-four times greater than RxJava), and (3) the approximation algorithms supported by our implementation can lead to substantial memory savings.Keywords
Funding Information
- National Science Foundation (CCF 1138996, CCF-1617851, IIS-1447470, ACI-1547360, ACI-1640813)
- National Institutes of Health (U01 EB020954)
This publication has 31 references indexed in Scilit:
- Processing flows of informationACM Computing Surveys, 2012
- Satisfiability modulo theoriesCommunications of the ACM, 2011
- MapReduceCommunications of the ACM, 2008
- The CQL continuous query language: semantic foundations and query executionThe VLDB Journal, 2005
- Data Streams: Algorithms and ApplicationsFoundations and Trends® in Theoretical Computer Science, 2005
- Aurora: a new model and architecture for data stream managementThe VLDB Journal, 2003
- Exploiting punctuation semantics in continuous data streamsIEEE Transactions on Knowledge and Data Engineering, 2003
- Continuous queries over data streamsACM SIGMOD Record, 2001
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite AutomataSIAM Journal on Computing, 1985