More Web Proxy on the site http://driver.im/

Article

Adaptive load shedding for windowed stream joins

Authors:

Ling LiuAuthors Info & Claims

CIKM '05: Proceedings of the 14th ACM international conference on Information and knowledge management

Pages 171 - 178

https://doi.org/10.1145/1099554.1099587

Published: 31 October 2005 Publication History

Abstract

We present an adaptive load shedding approach for windowed stream joins. In contrast to the conventional approach of dropping tuples from the input streams, we explore the concept of selective processing for load shedding. We allow stream tuples to be stored in the windows and shed excessive CPU load by performing the join operations, not on the entire set of tuples within the windows, but on a dynamically changing subset of tuples that are learned to be highly beneficial. We support such dynamic selective processing through three forms of runtime adaptations: adaptation to input stream rates, adaptation to time correlation between the streams and adaptation to join directions. Indexes are used to further speed up the execution of stream joins. Experiments are conducted to evaluate our adaptive load shedding in terms of output rate. The results show that our selective processing approach to load shedding is very effective and significantly outperforms the approach that drops tuples from the input streams.

References

[1]

A. Arasu, B. Babcock, S. Babu, M. Datar, K. Ito, R. Motwani, I. Nishizawa, U. Srivastava, D. Thomas, R. Varma, and J. Widom. STREAM: The stanford stream data manager. IEEE Data Engineering Bulletin, 26, March 2003.

[2]

B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In ACM PODS, 2002.

Digital Library

[3]

H. Balakrishnan, M. Balazinska, D. Carney, U. Cetintemel, M. Cherniack, C. Convey, E. Galvez, J. Salz, M. Stonebraker, N. Tatbul, R. Tibbetts, and S. Zdonik. Retrospective on Aurora. VLDB Journal Special Issue on Data Stream Processing, 2004.

Digital Library

[4]

D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, and S. Zdonik. Monitoring streams: A new class of data management applications. In VLDB, 2002.

Digital Library

[5]

S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. R. Madden, V. Raman, F. Reiss, and M. A. Shah. TelegraphCQ: Continuous dataflow processing for an uncertain world. In CIDR, 2003.

[6]

A. Das, J. Gehrke, and M. Riedewald. Approximate join processing over data streams. In ACM SIGMOD, 2003.

Digital Library

[7]

B. Gedik, K.-L.Wu, P. S. Yu, and L. Liu. Adaptive load shedding for windowed stream joins. Technical Report GIT-CERCS-05-05, Georgia Tech., May 2005.

Digital Library

[8]

L. Golab, S. Garg, and M. T. Ozsu. On indexing sliding windows over online data streams. In EDBT, 2004.

[9]

L. Golab and M. T. Ozsu. Processing sliding window multi-joins in continuous queries over data streams. In VLDB, 2003.

Digital Library

[10]

M. A. Hammad and W. G. Aref. Stream window join: Tracking moving objects in sensor-network databases. In SSDBM, 2003.

Digital Library

[11]

S. Helmer, T. Westmann, and G. Moerkotte. Diag-Join: An opportunistic join algorithm for 1:N relationships. In VLDB, 1998.

Digital Library

[12]

J. Kang, J. Naughton, and S. Viglas. Evaluating window joins over unbounded streams. In IEEE ICDE, 2003.

[13]

J. Kleinberg. Bursty and hierarchical structure in streams. In ACM SIGKDD, 2002.

Digital Library

[14]

S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. TAG: a Tiny AGgregation service for ad-hoc sensor networks. In USENIX OSDI, 2002.

Digital Library

[15]

N. Mamoulis. Efficient processing of joins on set-valued attributes. In ACM SIGMOD, 2003.

Digital Library

[16]

U. Srivastava and J. Widom. Flexible time management in data stream systems. In ACM PODS, 2004.

Digital Library

[17]

U. Srivastava and J. Widom. Memory-limited execution of windowed stream joins. In VLDB, 2004.

Digital Library

[18]

N. Tatbul, U. Cetintemel, S. Zdonik, M. Cherniack, and M. Stonebraker. Load shedding in a data stream manager. In VLDB, 2003.

Digital Library

[19]

P. A. Tucker, D. Maier, T. Sheard, and L. Fegaras. Exploiting punctuation semantics in continuous data streams. IEEE TKDE, 15, 2003.

Digital Library

[20]

K.-L. Wu, S.-K. Chen, and P. S. Yu. Interval query indexing for efficient stream processing. In ACM CIKM, 2004.

Digital Library

Cited By

Volnes EPlagemann TKoldehofe BGoebel VZhou YChrysanthis PGulisano V(2022)Travel lightProceedings of the 16th ACM International Conference on Distributed and Event-Based Systems10.1145/3524860.3539638(79-84)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1145/3524860.3539638
Zhao BViet Hung NWeidlich M(2020)Load Shedding for Complex Event Processing: Input-based and State-based Techniques2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00099(1093-1104)Online publication date: Apr-2020
https://doi.org/10.1109/ICDE48307.2020.00099
Russo G(2019)Self-Adaptive Data Stream Processing in Geo-Distributed Computing EnvironmentsProceedings of the 13th ACM International Conference on Distributed and Event-based Systems10.1145/3328905.3332304(276-279)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.1145/3328905.3332304
Show More Cited By

Index Terms

Adaptive load shedding for windowed stream joins
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Load-aware shedding in stream processing systems
DEBS '16: Proceedings of the 10th ACM International Conference on Distributed and Event-based Systems

Load shedding is a technique employed by stream processing systems to handle unpredictable spikes in the input load whenever available computing resources are not adequately provisioned. A load shedder drops tuples to keep the input load below a ...
CPU load shedding for binary stream joins

We present an adaptive load shedding approach for windowed stream joins. In contrast to the conventional approach of dropping tuples from the input streams, we explore the concept ofselective processing for load shedding. We allow stream tuples to be ...
A load shedding framework for XML stream joins
DEXA'10: Proceedings of the 21st international conference on Database and expert systems applications: Part I

Joining data streams using various types of windows is an established method of stream processing. The limitation of window size due to memory constraint takes a heavy toll on the accuracy of the query result. Through this paper, we propose a unique ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '05: Proceedings of the 14th ACM international conference on Information and knowledge management

October 2005

854 pages

ISBN:1595931406

DOI:10.1145/1099554

General Chair:
Otthein Herzog
University of Bremen, Germany
,
Program Chairs:
Hans-Jörg Schek
University for Health Sciences, Medical Informatics and Technology, Austria
,
Norbert Fuhr
University of Duisburg-Essen, Germany
,
Abdur Chowdhury
America Online, USA
,
Wilfried Teiken
IBM T.J. Watson Research Center, USA

Copyright © 2005 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 October 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM05

Sponsor:

CIKM05: Conference on Information and Knowledge Management

October 31 - November 5, 2005

Bremen, Germany

Acceptance Rates

CIKM '05 Paper Acceptance Rate 77 of 425 submissions, 18%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
541
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Volnes EPlagemann TKoldehofe BGoebel VZhou YChrysanthis PGulisano V(2022)Travel lightProceedings of the 16th ACM International Conference on Distributed and Event-Based Systems10.1145/3524860.3539638(79-84)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1145/3524860.3539638
Zhao BViet Hung NWeidlich M(2020)Load Shedding for Complex Event Processing: Input-based and State-based Techniques2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00099(1093-1104)Online publication date: Apr-2020
https://doi.org/10.1109/ICDE48307.2020.00099
Russo G(2019)Self-Adaptive Data Stream Processing in Geo-Distributed Computing EnvironmentsProceedings of the 13th ACM International Conference on Distributed and Event-based Systems10.1145/3328905.3332304(276-279)Online publication date: 24-Jun-2019
https://dl.acm.org/doi/10.1145/3328905.3332304
Jacques-Silva GLei RCheng LChen GChing KHu TMei YWilfong KShetty RYilmaz SBanerjee AHeintz BIyer SJaiswal A(2018)Providing streaming joins as a service at FacebookProceedings of the VLDB Endowment10.14778/3229863.322986911:12(1809-1821)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.14778/3229863.3229869
Katsipoulakis NLabrinidis AChrysanthis P(2018)Concept-Driven Load Shedding: Reducing Size and Error of Voluminous and Variable Data Streams2018 IEEE International Conference on Big Data (Big Data)10.1109/BigData.2018.8622265(418-427)Online publication date: Dec-2018
https://doi.org/10.1109/BigData.2018.8622265
Naeem MDobbie GLutteroth CWeber G(2017)Skewed distributions in semi-stream joinsInformation Systems10.1016/j.is.2016.09.00764:C(63-74)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1016/j.is.2016.09.007
Chandramouli BLevandoski JCortez E(2016)ICE: Managing cold state for big data applications2016 IEEE 32nd International Conference on Data Engineering (ICDE)10.1109/ICDE.2016.7498262(457-468)Online publication date: May-2016
https://doi.org/10.1109/ICDE.2016.7498262
(2015)Practical Identification of Dynamic Precedence Criteria to Produce Critical Results from Big Data StreamsBig Data Research10.5555/2991310.29913582:4(127-144)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.5555/2991310.2991358
Wei MRundensteiner EMani M(2015)INSURE: An integrated load reduction framework for XML stream processing2015 IEEE 31st International Conference on Data Engineering10.1109/ICDE.2015.7113333(783-794)Online publication date: Apr-2015
https://doi.org/10.1109/ICDE.2015.7113333
(2015)High frequency batch-oriented computations over large sliding time windowsFuture Generation Computer Systems10.1016/j.future.2014.09.00843:C(1-11)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.future.2014.09.008
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents