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

research-article

Moving range queries in distributed complex event processing

Authors:

Boris Koldehofe,

Beate Ottenwälder,

Kurt Rothermel,

Umakishore RamachandranAuthors Info & Claims

DEBS '12: Proceedings of the 6th ACM International Conference on Distributed Event-Based Systems

Pages 201 - 212

https://doi.org/10.1145/2335484.2335507

Published: 16 July 2012 Publication History

Abstract

Up to now, correlations in complex event processing (CEP) systems are detected by a well defined set of operators, whose configuration is determined ahead of deployment time. Although CEP operators involve location specific attributes, state of the art systems are heavily constrained in detecting situations where the interest in a situation changes depending on the consumer's location, e. g., with the movement of mobile devices.

This paper adopts the concept of range queries to CEP systems. We propose a mobility-aware event delivery semantics and present a corresponding execution model, which accounts for mobility driven selection of primary event streams to the CEP system. By utilizing the properties of this execution model, we derive an algorithm that establishes low cost and coordinated reconfiguration of CEP operators in a distributed system. The algorithm minimizes the amount of information that needs to be streamed between operators and avoids additional delays as a result of a reconfiguration of CEP operators. We present an analysis of the algorithm's properties and evaluate the efficiency of the proposed reconfiguration algorithm.

References

[1]

http://www.b30-oberschwaben.de/html/vergleiche.html, February 2012.

[2]

M. Akdere, U. Çetintemel, and N. Tatbul. Plan-based complex event detection across distributed sources. Proc. VLDB Endow., 1:66--77, August 2008.

Digital Library

[3]

A. Arasu, S. Babu, and J. Widom. The cql continuous query language: semantic foundations and query execution. The VLDB Journal, 15:121--142, June 2006.

Digital Library

[4]

M. Behrisch, L. Bieker, J. Erdmann, and D. Krajzewicz. Sumo - simulation of urban mobility: An overview. In SIMUL 2011, The Third International Conference on Advances in System Simulation, pages 63--68, Barcelona, Spain, October 2011.

[5]

A. Benzing, B. Koldehofe, and K. Rothermel. Efficient support for multi-resolution queries in global sensor networks. In Proceedings of the 5th International Conference on Communication System Software and Middleware, COMSWARE '11, pages 11:1--11:12, New York, NY, USA, 2011. ACM.

Digital Library

[6]

S. Chakravarthy and D. Mishra. Snoop: An expressive event specification language for active databases. Data & Knowledge Engineering, 14(1):1--26, 1994.

Digital Library

[7]

M. Cheema, L. Brankovic, X. Lin, W. Zhang, and W. Wang. Multi-guarded safe zone: An effective technique to monitor moving circular range queries. In Data Engineering (ICDE), 2010 IEEE 26th International Conference on, pages 189--200, march 2010.

[8]

T. Do, K. Hua, and C.-S. Lin. Extrange: Continuous moving range queries in mobile peer-to-peer networks. In Mobile Data Management: Systems, Services and Middleware, 2009. MDM '09. Tenth International Conference on, pages 317--322, may 2009.

Digital Library

[9]

P. T. Eugster, P. A. Felber, R. Guerraoui, and A.-M. Kermarrec. The many faces of publish/subscribe. ACM Comput. Surv., 35(2):114--131, 2003.

Digital Library

[10]

T. Farrell, R. Cheng, and K. Rothermel. Energy-efficient monitoring of mobile objects with uncertainty-aware tolerances. In Proceedings of the 11th International Database Engineering and Applications Symposium, pages 129--140, Washington, DC, USA, 2007. IEEE Computer Society.

Digital Library

[11]

S. Gatziu and K. Dittrich. Detecting composite events in active database systems using petri nets. In Research Issues in Data Engineering, 1994. Active Database Systems. Proceedings Fourth International Workshop on, pages 2--9, 14--15 1994.

[12]

B. Gedik and L. Liu. Mobieyes: A distributed location monitoring service using moving location queries. IEEE Transactions on Mobile Computing, 5:1384--1402, 2006.

Digital Library

[13]

M. Haklay and P. Weber. Openstreetmap: User-generated street maps. Pervasive Computing, IEEE, 7(4):12--18, oct.--dec. 2008.

Digital Library

[14]

K. Jayaram, C. Jayalath, and P. Eugster. Parametric subscriptions for content-based publish/subscribe networks. In I. Gupta and C. Mascolo, editors, Middleware 2010, volume 6452 of Lecture Notes in Computer Science, pages 128--147. Springer Berlin/Heidelberg, 2010.

Digital Library

[15]

G. G. Koch, B. Koldehofe, and K. Rothermel. Cordies: expressive event correlation in distributed systems. In DEBS '10: Proceedings of the Fourth ACM International Conference on Distributed Event-Based Systems, pages 26--37, New York, NY, USA, 2010. ACM.

Digital Library

[16]

A. Leonhardi and K. Rothermel. A comparison of protocols for updating location information. Cluster Computing, 4:355--367, October 2001.

Digital Library

[17]

D. C. Luckham. The Power of Events: An Introduction to Complex Event Processing in Distributed Enterprise Systems. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2001.

Digital Library

[18]

K. Patroumpas and T. Sellis. Maintaining consistent results of continuous queries under diverse window specifications. Inf. Syst., 36:42--61, March 2011.

Digital Library

[19]

D. Pfoser, C. S. Jensen, and Y. Theodoridis. Novel approaches in query processing for moving object trajectories. In Proceedings of the 26th International Conference on Very Large Data Bases, VLDB '00, pages 395--406, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc.

Digital Library

[20]

P. Pietzuch, J. Ledlie, J. Shneidman, M. Roussopoulos, M. Welsh, and M. Seltzer. Network-aware operator placement for stream-processing systems. In Proceedings of the 22nd International Conference on Data Engineering, ICDE '06, pages 49--, Washington, DC, USA, 2006. IEEE Computer Society.

Digital Library

[21]

P. R. Pietzuch, B. Shand, and J. Bacon. Composite event detection as a generic middleware extension. Network, IEEE, 18(1):44--55, jan/feb 2004.

Digital Library

[22]

S. Rizou, F. Dürr, and K. Rothermel. Solving the Multi-operator Placement Problem in Large-Scale Operator Networks. In Proceedings of the 19th International Conference on Computer Communication Networks, Zurich, August 2010. IEEE Communications Society.

[23]

B. Schilling, B. Koldehofe, U. Pletat, and K. Rothermel. Distributed heterogeneous event processing: enhancing scalability and interoperability of cep in an industrial context. In DEBS '10: Proceedings of the Fourth ACM International Conference on Distributed Event-Based Systems, pages 150--159, New York, NY, USA, 2010. ACM.

Digital Library

[24]

B. Schilling, B. Koldehofe, and K. Rothermel. Efficient and distributed rule placement in heavy constraint-driven event systems. In High Performance Computing and Communications (HPCC), 2011 IEEE 13th International Conference on, pages 355--364, sept. 2011.

Digital Library

[25]

K. Sheykh-Esmaili, T. Sanamrad, P. M. Fischer, and N. Tatbul. Changing Flights in Mid-air: A Model for Safely Modifying Continuous Queries. In ACM SIGMOD International Conference on Management of Data (SIGMOD'11), Athens, Greece, June 2011.

Digital Library

[26]

M. A. Tariq, G. G. Koch, B. Koldehofe, I. Khan, and K. Rothermel. Dynamic publish/subscribe to meet subscriber-defined delay and bandwidth constraints. In Proceedings of the 16th international Euro-Par conference on Parallel processing: Part I, EuroPar'10, pages 458--470, Berlin, Heidelberg, 2010. Springer-Verlag.

Digital Library

[27]

G. Trajcevski, H. Ding, P. Scheuermann, and I. Cruz. Bora: Routing and aggregation for distributed processing of spatio-temporal range queries. In Mobile Data Management, 2007 International Conference on, pages 36--43, may. 2007.

Digital Library

[28]

A. Varga. The omnet++ discrete event simulation system. In Proceedings of the European Simulation Multiconference (ESM'2001), June 2001.

[29]

M. Völz, B. Koldehofe, and K. Rothermel. Supporting strong reliability for distributed complex event processing systems. In High Performance Computing and Communications (HPCC), 2011 IEEE 13th International Conference on, pages 477--486, sept. 2011.

Digital Library

[30]

O. Wolfson, A. P. Sistla, S. Chamberlain, and Y. Yesha. Updating and querying databases that track mobile units. Distrib. Parallel Databases, 7:257--387, July 1999.

Digital Library

[31]

E. Wu, Y. Diao, and S. Rizvi. High-performance complex event processing over streams. In Proceedings of the 2006 ACM SIGMOD international conference on Management of data, SIGMOD '06, pages 407--418, New York, NY, USA, 2006. ACM.

Digital Library

[32]

X. Xiong, H. Elmongui, X. Chai, and W. Aref. Place: A distributed spatio-temporal data stream management system for moving objects. In Mobile Data Management, 2007 International Conference on, pages 44--51, May 2007.

Digital Library

Cited By

Richerzhagen BRicherzhagen B(2018)State of the ArtMechanism Transitions in Publish/Subscribe Systems10.1007/978-3-319-92570-7_3(27-46)Online publication date: 28-Jul-2018
https://doi.org/10.1007/978-3-319-92570-7_3
Bhowmik STariq MKoldehofe BDurr FKohler TRothermel K(2017)High Performance Publish/Subscribe Middleware in Software-Defined NetworksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2016.263297025:3(1501-1516)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1109/TNET.2016.2632970
Gong YKuang HCai XHu HSong WLu J(2017)Parallelized Mobility-Aware Complex Event Processing2017 IEEE International Conference on Web Services (ICWS)10.1109/ICWS.2017.116(898-901)Online publication date: Jun-2017
https://doi.org/10.1109/ICWS.2017.116
Show More Cited By

Index Terms

Moving range queries in distributed complex event processing

Recommendations

Complex event processing with T-REX

Several application domains involve detecting complex situations and reacting to them. This asks for a Complex Event Processing (CEP) middleware specifically designed to timely process large amounts of event notifications as they flow from the ...
Towards complex actions for complex event processing
DEBS '13: Proceedings of the 7th ACM international conference on Distributed event-based systems

Complex actions are a natural extension for complex event processing languages needed by many applications like emergency management. In particular interactions with external actuators that are common in those applications pose challenges that need to ...
Reasoning on the Efficiency of Distributed Complex Event Processing
Concurrency, Specification, and Programming: Special Issue of Selected Papers of CS&P 2018

Complex event processing (CEP) evaluates queries over streams of event data to detect situations of interest. If the event data are produced by geographically distributed sources, CEP may exploit in-network processing that distributes the evaluation of a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DEBS '12: Proceedings of the 6th ACM International Conference on Distributed Event-Based Systems

July 2012

410 pages

ISBN:9781450313155

DOI:10.1145/2335484

Co-chair:
Francois Bry
Ludwig Maximilian University of Munich, Germany
,
General Chair:
Adrian Paschke
Freie Universitaet Berlin, Germany
,
Program Chairs:
Patrick Eugster
Purdue University, USA
,
Christof Fetzer
Dresden University of Technology, Germany
,
Publications Chair:
Andreas Behrend
University of Bonn, Germany

Copyright © 2012 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: 16 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DEBS '12

Sponsor:

DEBS '12: The 6th ACM International Conference on Distributed Event-based system

July 16 - 20, 2012

Berlin, Germany

Acceptance Rates

Overall Acceptance Rate 145 of 583 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
531
Total Downloads

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

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Richerzhagen BRicherzhagen B(2018)State of the ArtMechanism Transitions in Publish/Subscribe Systems10.1007/978-3-319-92570-7_3(27-46)Online publication date: 28-Jul-2018
https://doi.org/10.1007/978-3-319-92570-7_3
Bhowmik STariq MKoldehofe BDurr FKohler TRothermel K(2017)High Performance Publish/Subscribe Middleware in Software-Defined NetworksIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2016.263297025:3(1501-1516)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1109/TNET.2016.2632970
Gong YKuang HCai XHu HSong WLu J(2017)Parallelized Mobility-Aware Complex Event Processing2017 IEEE International Conference on Web Services (ICWS)10.1109/ICWS.2017.116(898-901)Online publication date: Jun-2017
https://doi.org/10.1109/ICWS.2017.116
Lim JBok KYoo J(2017)An efficient continuous range query processing scheme in mobile P2P networksThe Journal of Supercomputing10.1007/s11227-017-1986-xOnline publication date: 23-Feb-2017
https://doi.org/10.1007/s11227-017-1986-x
Starks FGoebel VKristiansen SPlagemann T(2017)Mobile Distributed Complex Event Processing—Ubi Sumus? Quo Vadimus?Mobile Big Data10.1007/978-3-319-67925-9_7(147-180)Online publication date: 1-Nov-2017
https://doi.org/10.1007/978-3-319-67925-9_7
Mayer RMayer CTariq MRothermel KGal AWeidlich MKalogeraki VVenkasubramanian N(2016)GraphCEPProceedings of the 10th ACM International Conference on Distributed and Event-based Systems10.1145/2933267.2933509(309-316)Online publication date: 13-Jun-2016
https://dl.acm.org/doi/10.1145/2933267.2933509
Chakraborty SBhowmick STalaga PAgrawal D(2016)Fog Networks in Healthcare Application2016 IEEE 13th International Conference on Mobile Ad Hoc and Sensor Systems (MASS)10.1109/MASS.2016.065(386-387)Online publication date: Oct-2016
https://doi.org/10.1109/MASS.2016.065
Mayer RKoldehofe BRothermel K(2015)Predictable Low-Latency Event Detection With Parallel Complex Event ProcessingIEEE Internet of Things Journal10.1109/JIOT.2015.23973162:4(274-286)Online publication date: Aug-2015
https://doi.org/10.1109/JIOT.2015.2397316
Tariq MKoldehofe BBhowmik SRothermel KRéveillère LCherkasova LTaïani F(2014)PLEROMAProceedings of the 15th International Middleware Conference10.1145/2663165.2663338(217-228)Online publication date: 8-Dec-2014
https://dl.acm.org/doi/10.1145/2663165.2663338
Ottenwälder BKoldehofe BRothermel KHong KLillethun DRamachandran U(2014)MCEPACM Transactions on Internet Technology10.1145/263368814:1(1-24)Online publication date: 7-Aug-2014
https://dl.acm.org/doi/10.1145/2633688
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