Characterizing memory requirements for queries over continuous data streams
- 1 March 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 29 (1) , 162-194
- https://doi.org/10.1145/974750.974756
Abstract
This article deals with continuous conjunctive queries with arithmetic comparisons and optional aggregation over multiple data streams. An algorithm is presented for determining whether or not any given query can be evaluated using a bounded amount of memory for all possible instances of the data streams. For queries that can be evaluated using bounded memory, an execution strategy based on constant-sized synopses of the data streams is proposed. For queries that cannot be evaluated using bounded memory, data stream scenarios are identified in which evaluating the queries requires memory linear in the size of the unbounded streams.Keywords
This publication has 20 references indexed in Scilit:
- Issues in data stream managementACM SIGMOD Record, 2003
- Exploiting punctuation semantics in continuous data streamsIEEE Transactions on Knowledge and Data Engineering, 2003
- Models and issues in data stream systemsPublished by Association for Computing Machinery (ACM) ,2002
- Characterizing memory requirements for queries over continuous data streamsPublished by Association for Computing Machinery (ACM) ,2002
- Monitoring Streams — A New Class of Data Management ApplicationsPublished by Elsevier ,2002
- Streaming Queries over Streaming DataPublished by Elsevier ,2002
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-TotalsData Mining and Knowledge Discovery, 1997
- Efficient checking of temporal integrity constraints using bounded history encodingACM Transactions on Database Systems, 1995
- Random sampling with a reservoirACM Transactions on Mathematical Software, 1985