research-article

Approximate continuous querying over distributed streams

Authors:

Graham Cormode,

Minos GarofalakisAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 33, Issue 2

Article No.: 9, Pages 1 - 39

https://doi.org/10.1145/1366102.1366106

Published: 24 June 2008 Publication History

Abstract

While traditional database systems optimize for performance on one-shot query processing, emerging large-scale monitoring applications require continuous tracking of complex data-analysis queries over collections of physically distributed streams. Thus, effective solutions have to be simultaneously space/time efficient (at each remote monitor site), communication efficient (across the underlying communication network), and provide continuous, guaranteed-quality approximate query answers. In this paper, we propose novel algorithmic solutions for the problem of continuously tracking a broad class of complex aggregate queries in such a distributed-streams setting. Our tracking schemes maintain approximate query answers with provable error guarantees, while simultaneously optimizing the storage space and processing time at each remote site, and the communication cost across the network. In a nutshell, our algorithms rely on tracking general-purpose randomized sketch summaries of local streams at remote sites along with concise prediction models of local site behavior in order to produce highly communication- and space/time-efficient solutions. The end result is a powerful approximate query tracking framework that readily incorporates several complex analysis queries (including distributed join and multi-join aggregates, and approximate wavelet representations), thus giving the first known low-overhead tracking solution for such queries in the distributed-streams model. Experiments with real data validate our approach, revealing significant savings over naive solutions as well as our analytical worst-case guarantees.

References

[1]

Alon, N., Gibbons, P. B., Matias, Y., and Szegedy, M. 1999. Tracking join and self-join sizes in limited storage. In Proceedings of the 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. Philadeplphia, PA.

Digital Library

[2]

Alon, N., Matias, Y., and Szegedy, M. 1996. The space complexity of approximating the frequency moments. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing. Philadelphia, PA, 20--29.

Digital Library

[3]

Babcock, B. and Olston, C. 2003. Distributed top-K monitoring. In Proceedings of the ACM SIGMOD International Conference on Management of Data. San Diego, CA.

Digital Library

[4]

Box, G. and Jenkins, G. 1970. Time Series Analaysis: Forecasting and Control. Holden-Day.

Digital Library

[5]

Charikar, M., Chen, K., and Farach-Colton, M. 2002. Finding frequent items in data streams. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Malaga, Spain.

Digital Library

[6]

Chu, D., Deshpande, A., Hellerstein, J. M., and Hong, W. 2006. Approximate data collection in sensor networks using probabilistic models. In Proceedings of the 22nd International Conference on Data Engineering. Atlanta, GA.

Digital Library

[7]

Cormode, G. and Garofalakis, M. 2005. Sketching streams through the net: Distributed approximate query tracking. In Proceedings of the 31st International Conference on Very Large Data Bases. Trondheim, Norway.

Digital Library

[8]

Cormode, G., Garofalakis, M., Muthukrishnan, S., and Rastogi, R. 2005. Holistic aggregates in a networked world: Distributed tracking of approximate quantiles. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Baltimore, MD.

Digital Library

[9]

Cormode, G. and Muthukrishnan, S. 2003. What's hot and what's not: Tracking most frequent items dynamically. In Proceedings of the 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. San Diego, CA, 296--306.

Digital Library

[10]

Cormode, G. and Muthukrishnan, S. 2004. An improved data stream summary: The count-min sketch and its applications. Latin American Informatics. 29--38.

[11]

Cranor, C., Johnson, T., Spatscheck, O., and Shkapenyuk, V. 2003. Gigascope: A stream database for network applications. In Proceedings of the ACM SIGMOD International Conference on Management of Data. San Diego, CA.

Digital Library

[12]

Das, A., Ganguly, S., Garofalakis, M., and Rastogi, R. 2004. Distributed set-expression cardinality estimation. In Proceedings of the 30th International Conference on Very Large Data Bases. Toronto, Canada.

Digital Library

[13]

Datar, M., Gionis, A., Indyk, P., and Motwani, R. 2002. Maintaining stream statistics over sliding windows. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. San Francisco, CA, 635--644.

Digital Library

[14]

Deshpande, A., Guestrin, C., Madden, S. R., Hellerstein, J. M., and Hong, W. 2004. Model-driven data acquisition in sensor networks. In Proceedings of the 30th International Conference on Very Large Data Bases. Toronto, Canada.

Digital Library

[15]

Dobra, A., Garofalakis, M., Gehrke, J., and Rastogi, R. 2002. Processing complex aggregate queries over data streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Madison, WI, 61--72.

Digital Library

[16]

Ganguly, S., Garofalakis, M., and Rastogi, R. 2003. Processing set expressions over continuous update streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data. San Diego, CA.

Digital Library

[17]

Ganguly, S., Garofalakis, M., and Rastogi, R. 2004. Processing data-stream join aggregates using skimmed sketches. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT'04). Heraklion-Crete, Greece.

[18]

Gibbons, P. B. 2001. Distinct sampling for highly accurate answers to distinct values queries and event reports. In Proceedings of the 27th International Conference on Very Large Data Bases. Roma, Italy.

Digital Library

[19]

Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., and Strauss, M. J. 2001. Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. In Proceedings of the 27th International Conference on Very Large Data Bases. Roma, Italy.

Digital Library

[20]

Greenwald, M. B. and Khanna, S. 2001. Space-efficient online computation of quantile summaries. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Santa Barbara, CA.

Digital Library

[21]

Greenwald, M. B. and Khanna, S. 2004. Power-conserving computation of order-statistics over sensor networks. In Proceedings of the 23rd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. Paris, France.

Digital Library

[22]

Hardy, G., Littlewood, J., and Pólya, G. 1988. Inequalities, 2nd Ed. Cambridge University Press.

[23]

Huang, L., Garofalakis, M., Joseph, A. D., and Taft, N. 2007a. Communication-efficient tracking of distributed cumulative triggers. In Proceedings of the 27th IEEE International Conference on Distributed Computing Systems (ICDCS'07). Toronto, Canada.

Digital Library

[24]

Huang, L., Nguyen, X., Garofalakis, M., Hellerstein, J. M., Jordan, M. I., Joseph, A. D., and Taft, N. 2007b. Communication-efficient online detection of network-wide anomalies. In Proceedings of IEEE INFOCOM. Anchorage, AK.

[25]

Jain, A., Chang, E. Y., and Wang, Y.-F. 2004. Adaptive stream resource management using Kalman filters. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Paris, France.

Digital Library

[26]

Keralapura, R., Cormode, G., and Ramamirtham, J. 2006. Communication-efficient distributed monitoring of thresholded counts. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Chicago, IL, 289--300.

Digital Library

[27]

Madden, S. R., Franklin, M. J., Hellerstein, J. M., and Hong, W. 2003. The design of an acquisitional query processor for sensor networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data. San Diego, CA.

Digital Library

[28]

Manjhi, A., Shkapenyuk, V., Dhamdhere, K., and Olston, C. 2005. Finding (recently) frequent items in distributed data streams. In Proceedings of the 21st International Conference on Data Engineering. Tokyo, Japan.

Digital Library

[29]

Manku, G. S. and Motwani, R. 2002. Approximate frequency counts over data streams. In Proceedings of the 28th International Conference on Very Large Data Bases. Hong Kong, China, 346--357.

Digital Library

[30]

Motwani, R. and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press.

Digital Library

[31]

Olston, C., Jiang, J., and Widom, J. 2003. Adaptive filters for continuous queries over distributed data streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data. San Diego, CA.

Digital Library

[32]

Sharfman, I., Schuster, A., and Keren, D. 2006. A geometric approach to monitoring threshold functions over distributed data streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Chicago, IL, 301--312.

Digital Library

[33]

Thaper, N., Guha, S., Indyk, P., and Koudas, N. 2002. Dynamic multidimensional histograms. In Proceedings of the ACM SIGMOD International Conference on Management of Data. Madison, WI, 428--439.

Digital Library

[34]

Tulone, D. and Madden, S. 2006. Paq: Time series forecasting for approximate query answering in sensor networks. In the European Conference on Wireless Sensor Networks (EWSN).

Digital Library

Cited By

Kontaxakis AGiatrakos NSacharidis DDeligiannakis A(2023)And synopses for all: A synopses data engine for extreme scale analytics-as-a-serviceInformation Systems10.1016/j.is.2023.102221116(102221)Online publication date: Jun-2023
https://doi.org/10.1016/j.is.2023.102221
Sun JZhang RZhang JZhang Y(2021)PriStream: Privacy-preserving distributed stream monitoring of thresholded PERCENTILE statisticsIEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications10.1109/INFOCOM.2016.7524461(1-9)Online publication date: 10-Mar-2021
https://dl.acm.org/doi/10.1109/INFOCOM.2016.7524461
Vandenberg JTsan JBoulden DZakaria ZLynch CBoyer KWiebe E(2020)Elementary Students’ Understanding of CS TermsACM Transactions on Computing Education10.1145/338636420:3(1-19)Online publication date: 16-Jun-2020
https://dl.acm.org/doi/10.1145/3386364
Show More Cited By

Index Terms

Approximate continuous querying over distributed streams
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
  2. World Wide Web
    1. Web applications
      1. Internet communications tools
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Tracking set-expression cardinalities over continuous update streams

There is growing interest in algorithms for processing and querying continuous data streams (i.e., data seen only once in a fixed order) with limited memory resources. In its most general form, a data stream is actually an <i>update</i> stream, i.e., ...
TuG synopses for approximate query answering

This article introduces the Tuple Graph (TuG) synopses, a new class of data summaries that enable accurate approximate answers for complex relational queries. The proposed summarization framework adopts a “semi-structured” view of the relational ...
Approximate query processing using wavelets

Approximate query processing has emerged as a cost-effective approach for dealing with the huge data volumes and stringent response-time requirements of today's decision support systems (DSS). Most work in this area, however, has so far been limited in ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 33, Issue 2

June 2008

309 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/1366102

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 June 2008

Accepted: 01 January 2008

Revised: 01 August 2007

Received: 01 January 2007

Published in TODS Volume 33, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
903
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kontaxakis AGiatrakos NSacharidis DDeligiannakis A(2023)And synopses for all: A synopses data engine for extreme scale analytics-as-a-serviceInformation Systems10.1016/j.is.2023.102221116(102221)Online publication date: Jun-2023
https://doi.org/10.1016/j.is.2023.102221
Sun JZhang RZhang JZhang Y(2021)PriStream: Privacy-preserving distributed stream monitoring of thresholded PERCENTILE statisticsIEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications10.1109/INFOCOM.2016.7524461(1-9)Online publication date: 10-Mar-2021
https://dl.acm.org/doi/10.1109/INFOCOM.2016.7524461
Vandenberg JTsan JBoulden DZakaria ZLynch CBoyer KWiebe E(2020)Elementary Students’ Understanding of CS TermsACM Transactions on Computing Education10.1145/338636420:3(1-19)Online publication date: 16-Jun-2020
https://dl.acm.org/doi/10.1145/3386364
Ravve E(2020)Logic-Based Approach to Incremental Monitoring and Optimization on Strongly Distributed Data StreamsFoundations of Information and Knowledge Systems10.1007/978-3-030-39951-1_15(242-262)Online publication date: 17-Feb-2020
https://dl.acm.org/doi/10.1007/978-3-030-39951-1_15
Chen YLan HDu ZLiu STao JHan DLuo TGuo QLi LXie YChen T(2019)An Instruction Set Architecture for Machine LearningACM Transactions on Computer Systems10.1145/333146936:3(1-35)Online publication date: 13-Aug-2019
https://dl.acm.org/doi/10.1145/3331469
Gupta AShute J(2019)High-Availability at Massive Scale: Building Google’s Data Infrastructure for AdsReal-Time Business Intelligence and Analytics10.1007/978-3-030-24124-7_5(63-81)Online publication date: 11-Oct-2019
https://doi.org/10.1007/978-3-030-24124-7_5
Lazerson AKeren DSchuster A(2018)Lightweight Monitoring of Distributed StreamsACM Transactions on Database Systems10.1145/322611343:2(1-37)Online publication date: 31-Jul-2018
https://dl.acm.org/doi/10.1145/3226113
Dai HLi MLiu A(2018)Finding Persistent Items in Distributed DatasetsIEEE INFOCOM 2018 - IEEE Conference on Computer Communications10.1109/INFOCOM.2018.8486425(1403-1411)Online publication date: Apr-2018
https://doi.org/10.1109/INFOCOM.2018.8486425
Giatrakos NDeligiannakis AGarofalakis MKeren DSamoladas V(2018)Scalable approximate query tracking over highly distributed data streams with tunable accuracy guaranteesInformation Systems10.1016/j.is.2018.05.00176(59-87)Online publication date: Jul-2018
https://doi.org/10.1016/j.is.2018.05.001
Papapetrou OGarofalakis M(2018)Monitoring distributed fragmented skylinesDistributed and Parallel Databases10.1007/s10619-018-7223-736:4(675-715)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10619-018-7223-7
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents