No pane, no gain: efficient evaluation of sliding-window aggregates over data streams

ABSTRACT

Windows queries are proving essential to data-stream processing. In this paper, we present an approach for evaluating sliding-window aggregate queries that reduces both space and computation time for query execution. Our approach divides overlapping windows into disjoint panes, computes sub-aggregates over each pane, and "rolls up" the pane-aggregates to computer window-aggregates. Our experimental study shows that using panes has significant performance benefits.

REFERENCES

• 1: A. Arasu, S. Babu, and J. Widom. The CQL Continuous Query Language: Semantic Foundations and Query Execution. Stanford University Technical Report, October 2003.
• 2: A. Arasu, J. Widom. Resource Sharing in Continuous Sliding-Window Aggregates. In Proceedings of the 30th International Conference on Very Large Databases (VLDB 2004).
• 3: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 4: D. Carney et al. Monitoring Streams - A New Class of Data Management Applications. In Proceedings of the 28th International Conference on Very Large Databases (VLDB 2002).
• 5: Graham Cormode , Theodore Johnson , Flip Korn , S. Muthukrishnan , Oliver Spatscheck , Divesh Srivastava, Holistic UDAFs at streaming speeds, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007575]
• 6: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 7: S. Chandrasekaran et al. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. In Proceedings of the 2003 Conference on Innovative Data Systems Research.
• 8: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 9: J. Li et al. Evaluating window aggregate queries over streams. Technical Report, May 2004, OGI/OHSU. http://www.cse.ogi.edu/~jinli/papers/WinAggrQ.pdf
• 10: J. Naughton et al. The Niagara Internet Query System. IEEE Data Engineering Bulletin, 24(2), 27--33, (June 2001).
• 11: U. Srivastava, J. Widom. Flexible Time Management in Data Stream Systems. Technical Report 2003-40, Stanford University, Stanford, CA (July 2003).
• 12: The STREAM Group. STREAM: The Stanford STREAM Data Manager. IEEE Data Engineering Bulletin, 26(1), (March 2003).
• 13: XMark Benchmark. http://www.xml-benchmark.org.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Experimentation, Performance