Article

Towards expressive publish/subscribe systems

Authors:

Johannes Gehrke,

Mingsheng Hong,

Mirek Riedewald,

Walker WhiteAuthors Info & Claims

EDBT'06: Proceedings of the 10th international conference on Advances in Database Technology

Pages 627 - 644

https://doi.org/10.1007/11687238_38

Published: 26 March 2006 Publication History

Abstract

Traditional content based publish/subscribe (pub/sub) systems allow users to express stateless subscriptions evaluated on individual events. However, many applications such as monitoring RSS streams, stock tickers, or management of RFID data streams require the ability to handle stateful subscriptions. In this paper, we introduce Cayuga, a stateful pub/sub system based on nondeterministic finite state automata (NFA). Cayuga allows users to express subscriptions that span multiple events, and it supports powerful language features such as parameterization and aggregation, which significantly extend the expressive power of standard pub/sub systems. Based on a set of formally defined language operators, the subscription language of Cayuga provides non-ambiguous subscription semantics as well as unique opportunities for optimizations. We experimentally demonstrate that common optimization techniques used in NFA-based systems such as state merging have only limited effectiveness, and we propose novel efficient indexing methods to speed up subscription processing. In a thorough experimental evaluation we show the efficacy of our approach.

References

[1]

Traderbot financial search engine. http://www.traderbot.com/.

[2]

D. J. Abadi, Y. Ahmad, M. Balazinska, U. Çetintemel, M. Cherniack, J.-H. Hwang, W. Lindner, A. Maskey, A. Rasin, E. Ryvkina, N. Tatbul, Y. Xing, and S. B. Zdonik. The design of the borealis stream processing engine. In Proc. CIDR, pages 277-289, 2005.

[3]

R. Adaikkalavan and S. Chakravarthy. Snoopib: Interval-based event specification and detection for active databases. In Proc. ADBIS, pages 190-204, 2003.

[4]

M. K. Aguilera, R. E. Strom, D. C. Sturman, M. Astley, and T. D. Chandra. Matching events in a content-based subscription system. In Proc. PODC, pages 53-61, 1999.

Digital Library

[5]

A. Arasu, B. Babcock, S. Babu, J.McAlister, and J.Widom. Characterizing memory requirements for queries over continuous data streams. In Proc. PODS, pages 221-232, 2002.

Digital Library

[6]

A. Arasu, S. Babu, and J. Widom. The CQL continuous query language: Semantic foundations and query execution. Technical report, Stanford University, 2003.

[7]

B. Babcock, S. Babu, M. Datar, R.Motwani, and J.Widom. Models and issues in data stream systems. In Proc. PODS, pages 1-16, 2002.

Digital Library

[8]

D. Carney, U. Çetintemel, 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 Proc. VLDB, 2002.

Digital Library

[9]

S. Chakravarthy, V. Krishnaprasad, E. Anwar, and S.-K. Kim. Composite events for active databases: Semantics, contexts and detection. In Proc. VLDB, pages 606-617, 1994.

Digital Library

[10]

C. Y. Chan, P. Felber, M. N. Garofalakis, and R. Rastogi. Efficient filtering of XML documents with XPath expressions. In Proc. ICDE, pages 235-244, 2002.

Digital Library

[11]

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 Proc. CIDR, 2003.

[12]

A. Demers, J. Gehrke, M. Hong, M. Riedewald, and W. White. A general algebra and implementation for monitoring event streams. Technical report, Cornell University, 2005. http://techreports.library.cornell.edu.

[13]

Y. Diao, M. Altinel, M. J. Franklin, H. Zhang, and P. M. Fischer. Path sharing and predicate evaluation for high-performance XML filtering. ACM TODS, 28(4):467-516, 2003.

Digital Library

[14]

F. Fabret, H.-A. Jacobsen, F. Llirbat, J. Pereira, K. A. Ross, and D. Shasha. Filtering algorithms and implementation for very fast publish/subscribe. In Proc. SIGMOD, pages 115- 126, 2001.

Digital Library

[15]

A. Galton and J. C. Augusto. Two approaches to event definition. In Proc. DEXA, pages 547-556, 2002.

Digital Library

[16]

N. H. Gehani, H. V. Jagadish, and O. Shmueli. Composite event specification in active databases: Model and implementation. In Proc. VLDB, pages 327-338, 1992.

Digital Library

[17]

T. J. Green, G. Miklau, M. Onizuka, and D. Suciu. Processing XML streams with deterministic automata. In Proc. ICDT, pages 173-189, 2003.

Digital Library

[18]

A. K. Gupta and D. Suciu. Stream processing of XPath queries with predicates. In Proc. SIGMOD, pages 419-430, 2003.

Digital Library

[19]

J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2nd edition, 2000.

Digital Library

[20]

S. Krishnamurthy, M. J. Franklin, J. M. Hellerstein, and G. Jacobson. The case for precision sharing. In Proc. VLDB, pages 972-986, 2004.

Digital Library

[21]

H. Leung and H. Jacobsen. Efficient matching for state-persistent publish/subscribe systems. In CASCON '03: Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research, pages 182-196. IBM Press, 2003.

Digital Library

[22]

G. Li and H. Jacobsen. Composite subscriptions in content-based publish/subscribe systems. In Proc. ACM/IFIP/USENIX International Middleware Conference, 2005.

Digital Library

[23]

I. Motakis and C. Zaniolo. Formal semantics for composite temporal events in active database rules. Journal of Systems Integration, 7(3-4):291-325, 1997.

[24]

I. Motakis and C. Zaniolo. Temporal aggregation in active database rules. In Proc. SIGMOD, pages 440-451, 1997.

Digital Library

[25]

R. Motwani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. S. Manku, C. Olston, J. Rosenstein, and R. Varma. Query processing, approximation, and resource management in a data stream management system. In Proc. CIDR, 2003.

[26]

T. K. Sellis. Multiple-query optimization. ACM TODS, 13(1):23-52, 1988.

Digital Library

[27]

A. P. Sistla and O. Wolfson. Temporal conditions and integrity constraints in active database systems. In Proc. SIGMOD, pages 269-280, 1995.

Digital Library

[28]

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

Digital Library

[29]

J. Widom and S. Ceri, editors. Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann Publishers, 1996.

Digital Library

[30]

A. Yalamanchi, J. Srinivasan, and D. Gawlick. Managing expressions as data in relational database systems. In Proc. CIDR, 2003.

[31]

D. Zimmer and R. Unland. On the semantics of complex events in active database management systems. In Proc. ICDE, pages 392-399, 1999.

Digital Library

Cited By

Bucchi MGrez AQuintana ARiveros CVansummeren S(2022)COREProceedings of the VLDB Endowment10.14778/3538598.353861515:9(1951-1964)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.14778/3538598.3538615
Chapnik KKolchinsky ISchuster A(2022)DARLINGProceedings of the VLDB Endowment10.14778/3494124.349413715:3(541-554)Online publication date: 4-Feb-2022
https://dl.acm.org/doi/10.14778/3494124.3494137
Amir AKolchinsky ISchuster AIves ZBonifati AEl Abbadi A(2022)DLACEP: A Deep-Learning Based Framework for Approximate Complex Event ProcessingProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3526136(340-354)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3526136
Show More Cited By

Recommendations

Modeling Uncertainties in Publish/Subscribe Systems
ICDE '04: Proceedings of the 20th International Conference on Data Engineering

In the publish/subscribe paradigm, informationproviders disseminate publications to all consumers whohave expressed interest by registering subscriptions. Thisparadigm has found wide-spread applications, rangingfrom selective information dissemination ...
Efficient matching for state-persistent publish/subscribe systems
CASCON '03: Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research

Content-based publish/subscribe systems allow information dissemination and fine-grained information filtering in loosely coupled distributed systems. Stateless publish/subscribe systems send notifications to all subscribers whose subscriptions match an ...
Parameterized subscriptions in publish/subscribe systems

Traditional publish/subscribe systems commonly deal with static subscriptions, whose event filtering criteria stay fixed once defined. Although systems with static subscriptions are simpler to implement, there are cases where the subscription criterion ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EDBT'06: Proceedings of the 10th international conference on Advances in Database Technology

March 2006

1204 pages

ISBN:3540329609

Editors:
Yannis Ioannidis
University of Athens, Greece
,
Marc H. Scholl
University of Konstanz, Konstanz, Germany
,
Joachim W. Schmidt
Sustainable Content Logistics Centre, Hamburg, Germany
,
Florian Matthes
Chair of Software Engineering for Business Information Systems, Technische Universität München, Boltzmannstraße 3, Garching b. München
,
Mike Hatzopoulos
Department of Informatics, University of Athens Panepistimiopolis, Boltzmannstraße 3, Athens, Greece

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 26 March 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

80
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bucchi MGrez AQuintana ARiveros CVansummeren S(2022)COREProceedings of the VLDB Endowment10.14778/3538598.353861515:9(1951-1964)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.14778/3538598.3538615
Chapnik KKolchinsky ISchuster A(2022)DARLINGProceedings of the VLDB Endowment10.14778/3494124.349413715:3(541-554)Online publication date: 4-Feb-2022
https://dl.acm.org/doi/10.14778/3494124.3494137
Amir AKolchinsky ISchuster AIves ZBonifati AEl Abbadi A(2022)DLACEP: A Deep-Learning Based Framework for Approximate Complex Event ProcessingProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3526136(340-354)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3526136
Yankovitch MKolchinsky ISchuster AIves ZBonifati AEl Abbadi A(2022)HYPERSONIC: A Hybrid Parallelization Approach for Scalable Complex Event ProcessingProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517829(1093-1107)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517829
Kolchinsky ISchuster ABoncz PManegold SAilamaki ADeshpande AKraska T(2019)Real-Time Multi-Pattern Detection over Event StreamsProceedings of the 2019 International Conference on Management of Data10.1145/3299869.3319869(589-606)Online publication date: 25-Jun-2019
https://dl.acm.org/doi/10.1145/3299869.3319869
Kolchinsky ISchuster A(2018)Efficient adaptive detection of complex event patternsProceedings of the VLDB Endowment10.14778/3236187.323619011:11(1346-1359)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.14778/3236187.3236190
Kolchinsky ISchuster A(2018)Join query optimization techniques for complex event processing applicationsProceedings of the VLDB Endowment10.14778/3236187.323618911:11(1332-1345)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.14778/3236187.3236189
Elyusufi ZElyusufi YAitkbir M(2018)Customer profiling using CEP architecture in a Big Data contextProceedings of the 3rd International Conference on Smart City Applications10.1145/3286606.3286841(1-6)Online publication date: 10-Oct-2018
https://dl.acm.org/doi/10.1145/3286606.3286841
Giambona RRedondi ACesana MMüller PMostefaoui A(2018)MQTT+Proceedings of the 14th ACM International Symposium on QoS and Security for Wireless and Mobile Networks10.1145/3267129.3267135(77-84)Online publication date: 25-Oct-2018
https://dl.acm.org/doi/10.1145/3267129.3267135
Bračevac OAmin NSalvaneschi GErdweg SEugster PMezini M(2018)Versatile event correlation with algebraic effectsProceedings of the ACM on Programming Languages10.1145/32367622:ICFP(1-31)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3236762
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents