Introducing uncertainty in complex event processing: model, implementation, and validation | Computing Skip to main content
Springer Nature Link
Log in

Introducing uncertainty in complex event processing: model, implementation, and validation

  • Published:
Computing Aims and scope Submit manuscript

Abstract

Several application domains involve detecting complex situations and reacting to them. This asks for a Complex Event Processing (CEP) engine specifically designed to timely process low level event notifications to identify higher level composite events according to a set of user-defined rules. Several CEP engines and accompanying rule languages have been proposed. Their primary focus on performance often led to an oversimplified modeling of the external world where events happens, which is not suited to satisfy the demand of real-life applications. In particular, they are unable to consider, model, and propagate the uncertainty that exists in most scenarios. Moving from this premise, we present CEP2U (Complex Event Processing under Uncertainty), a novel model for dealing with uncertainty in CEP. We apply CEP2U to an existing CEP language—TESLA—, showing how it seamlessly integrate with modern rule languages by supporting all the operators they commonly offer. Moreover, we implement CEP2U on top of the T-Rex CEP engine and perform a detailed study of its performance, measuring a limited overhead that demonstrates its practical applicability. The discussion presented in this paper, together with the experiments we conducted, show how CEP2U provides a valuable combination of expressiveness, efficiency, and ease of use.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. This mechanism allows the definition of “hierarchies of events”.

  2. In particular, we assume that we receive all events (no false negatives) and that all received events actually occurred (no false positives). CEP2U can models the presence of false positives and negatives as part of the uncertainty in rules, as discussed in Sect. 4.2.2.

  3. In principle, we could remove this assumption and consider a multivariate pdf that involves all the attributes of incoming events, but this would complicate the model and it would require information that is usually unavailable at sources.

  4. This is a reasonable assumption, since the two readings come from different, independent sources. Only the occurrence of a TVS malfunctioning, whose probability is exactly what we are computing, may lead to correlated readings.

  5. To better understand the overhead introduced by Monte Carlo simulations, we performed some experiments using curve fitting from randomly generated samples to approximate an unknown function. In presence of hundreds of samples, curve fitting required some hundreds of milliseconds to complete in our reference hardware. This is two order of magnitude higher than the typical processing time of a CEP engine (see Sect. 6 for more details). However, by reducing the granularity of the sampling intervals we could easily reduce the computation time to a few milliseconds. As future work, we plan to perform a detailed analysis of the tradeoffs between efficiency and precision.

  6. Notice that, in the general case, the cost for computing the value of an aggregate can grow exponentially with the number of event notifications received. To limit the impact of this problem, it is possible to trade precision for efficiency, e.g., by approximating to 0 the occurrence probability of an event when it is sufficiently low (below a certain threshold) and to 1 when it is sufficiently high (above a certain threshold). The thresholds can be chosen based on the requirements in terms of precision and processing time.

  7. A detailed analysis on the impact of the input queue on performance is outside the scope of this paper, and can be found in [15].

  8. Notice that to capture uncertainty in rules, after evaluating BNs at rule design time, we have to propagate the calculated value to the composite events; a step that happens at run-time but with no measurable impact on performance.

References

  1. Adi A, Etzion O (2004) Amit—the situation manager. VLDB J 13(2):177–203. doi:10.1007/s00778-003-0108-y

    Article  Google Scholar 

  2. Agrawal J, Diao Y, Gyllstrom D, Immerman N (2008) Efficient pattern matching over event streams. In: SIGMOD, pp 147–160. ACM, New York. doi:10.1145/1376616.1376634

  3. Aguilera MK, Strom RE, Sturman DC, Astley M, Chandra TD (1999) Matching events in a content-based subscription system. In: Proceedings of the eighteenth annual ACM symposium on principles of distributed computing, PODC ’99. ACM, New York, pp 53–61. doi:10.1145/301308.301326

  4. Anicic D, Fodor P, Rudolph S, Stuhmer R, Stojanovic N, Studer R (2010) A rule-based language for complex event processing and reasoning. In: Hitzler P, Lukasiewicz T (eds) Web reasoning and rule systems. Lecture notes in computer science, vol 6333. Springer, Berlin, pp 42–57

  5. Anicic D, Fodor P, Rudolph S, Stuhmer R, Stojanovic N, Studer R (2011) Etalis: rule-based reasoning in event processing. In: Helmer S, Poulovassilis A, Xhafa F (eds) Reasoning in event-based distributed systems. Studies in computational intelligence, vol 347. Springer, Berlin, pp 99–124

  6. Arasu A, Babu S, Widom J (2006) The CQL continuous query language: semantic foundations and query execution. VLDB J 15(2):121–142

    Article  Google Scholar 

  7. Artikis A, Etzion O, Feldman Z, Fournier F (2012) Event processing under uncertainty. In: Proceedings of the 6th ACM international conference on distributed event-based systems, DEBS ’12, Berlin, Germany. ACM, New York, pp 32–43. http://doi.acm.org/10.1145/2335484.2335488

  8. Babcock B, Babu S, Datar M, Motwani R, Widom J (2002) Models and issues in data stream systems. In: PODS. ACM, New York, pp 1–16

  9. Biswas R, Thrun S, Fujimura K (2007) Recognizing activities with multiple cues. In: Workshop on human motion, pp 255–270

  10. BOOST: BOOST C++ Libraries: Math Toolkit (2012). http://www.boost.org/doc/libs/1_49_0/libs/math/doc/sf_and_dist/html/

  11. Brenna L, Demers A, Gehrke J, Hong M, Ossher J, Panda B, Riedewald M, Thatte M, White W (2007) Cayuga: a high-performance event processing engine. In: SIGMOD. ACM, New York, pp 1100–1102

  12. Broda K, Clark K, Miller R, Russo A (2009) SAGE: a logical agent-based environment monitoring and control system. In: Tscheligi M, Ruyter B, Markopoulus P, Wichert R, Mirlacher T, Meschterjakov A, Reitberger W (eds) Ambient intelligence, Lecture Notes in Computer Science, vol 5859. Springer, Berlin, Heidelberg, pp 112–117. http://dx.doi.org/10.1007/978-3-642-05408-2_14

  13. Chakravarthy S, Krishnaprasad V, Anwar E, Kim SK (1994) Composite events for active databases: semantics, contexts and detection. In: Proceedings of the 20th international conference on very large data bases, VLDB ’94. Morgan Kaufmann Publishers Inc., San Francisco, pp 606–617

  14. Cugola G, Margara A (2010) Tesla: a formally defined event specification language. In: DEBS, pp 50–61

  15. Cugola G, Margara A (2012) Complex event processing with T-Rex. J Syst Softw 85(8):1709–1728. doi:10.1016/j.jss.2012.03.056

    Article  Google Scholar 

  16. Cugola G, Margara A (2012) Low latency complex event processing on parallel hardware. J Parallel Distrib Comput 72(2):205–218. doi:10.1016/j.jpdc.2011.11.002

    Article  Google Scholar 

  17. Cugola G, Margara A (2012) Processing flows of information: from data stream to complex event processing. ACM Comput Surv 44(3):15:1–15:62. doi:10.1145/2187671.2187677

  18. Demers AJ, Gehrke J, Hong M, Riedewald M, White WM (2006) Towards expressive publish/subscribe systems. In: EDBT, pp 627–644

  19. Diao Y, Li B, Liu A, Peng L, Sutton C, Tran TTL, Zink M (2009 Capturing data uncertainty in high-volume stream processing. In: CIDR 2009, fourth biennial conference on innovative data systems research, Asilomar, CA, USA, 4–7 January 2009. Online proceedings

  20. Esper (2012). http://esper.codehaus.org/

  21. Etzion O, Niblett P (2010) Event processing in action. Manning Publications Co., Greenwich

    Google Scholar 

  22. Event zero (2012). http://www.eventzero.com/solutions/environment.aspx

  23. Gyllstrom D, Agrawal J, Diao Y, Immerman N (2008) On supporting Kleene closure over event streams. In: ICDE, pp 1391–1393

  24. Helaoui R, Niepert M, Stuckenschmidt H (2011) Recognizing interleaved and concurrent activities: a statistical-relational approach. In: PerCom, pp 1–9

  25. Jensen F (1996) An introduction to Bayesian networks, vol 36. UCL Press, London

  26. Kembhavi A, Yeh T, Davis LS (2010) Why did the person cross the road (there)? Scene understanding using probabilistic logic models and common sense reasoning. ECCV 2:693–706

    Google Scholar 

  27. Li G, Jacobsen HA (2005) Composite subscriptions in content-based publish/subscribe systems. In: Middleware. Springer-Verlag New York Inc, New York, pp 249–269

  28. Luckham DC (2001) The power of events: an introduction to complex event processing in distributed enterprise systems. Addison-Wesley Longman Publishing Co., Inc., Boston

    Google Scholar 

  29. Margara A (2012) Combining expressiveness and efficiency in a complex event processing middleware. PhD thesis, Politecnico di Milano

  30. Margara A, Cugola G, Tamburrelli G (2013) Towards automated rule learning for complex event processing. Technical Report

  31. Morariu VI, Davis LS (2011) Multi-agent event recognition in structured scenarios. In: CVPR, pp 3289–3296

  32. Mühl G, Fiege L, Pietzuch P (2006) Distributed event-based systems. Springer-Verlag New York, Inc., Secaucus

    MATH  Google Scholar 

  33. Netica: Netica API (2012). http://www.norsys.com/netica_api.html

  34. Oracle CEP (2011). http://www.oracle.com/technologies/soa/complex-event-processing.html

  35. Pietzuch PR, Shand B, Bacon J (2003) A framework for event composition in distributed systems. In: Proceedings of the ACM/IFIP/USENIX 2003 international conference on middleware. Middleware ’03. Springer-Verlag New York, Inc., New York, pp 62–82

  36. Progress-Apama (2011) http://web.progress.com/it-need/complex-event-processing.html. Visited Nov 2011

  37. Ré C, Letchner J, Balazinksa M, Suciu D (2008) Event queries on correlated probabilistic streams. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data, SIGMOD ’08. ACM, New York, pp 715–728. doi:10.1145/1376616.1376688

  38. Richardson M, Domingos P (2006) Markov logic networks. Mach Learn 62(1–2):107–136

    Article  Google Scholar 

  39. Sanghai S, Domingos P, Weld D (2005) Learning models of relational stochastic processes. In: Machine learning: ECML 2005. Springer, Berlin, pp 715–723

  40. Schultz-Møller NP, Migliavacca M, Pietzuch PR (2009) Distributed complex event processing with query rewriting. In: DEBS, pp 4:1–4:12

  41. Srivastava U, Widom J (2004) Flexible time management in data stream systems. In: PODS ’04. ACM, New York, pp 263–274. doi:10.1145/1055558.1055596

  42. Streambase (2011). http://www.streambase.com/

  43. Tibco: Tibco BusinessEvents. http://www.tibco.com/software/complex-event-processing/businessevents/defaul

  44. Tran SD, Davis LS (2008) Event modeling and recognition using Markov logic networks. ECCV 2:610–623

    Google Scholar 

  45. Wang F, Liu P (2005) Temporal management of RFID data. In: VLDB. VLDB endowment, pp 1128–1139

  46. Wasserkrug S, Gal A, Etzion O (2005) A model for reasoning with uncertain rules in event composition systems. In: Proceedings of the 21st annual conference on uncertainty in artificial intelligence, pp 599–606

  47. Wasserkrug S, Gal A, Etzion O, Turchin Y Complex event processing over uncertain data. In: Proceedings of the second international conference on distributed event-based systems, DEBS ’08. ACM, New York, pp 253–264 (2008). doi:10.1145/1385989.1386022

  48. Wasserkrug S, Gal A, Etzion O, Turchin Y (2012) Efficient processing of uncertain events in rule-based systems. IEEE Trans Knowl Data Eng 24(1):45–58. doi:10.1109/TKDE.2010.204

    Article  Google Scholar 

Download references

Acknowledgments

This research has been funded by the European Commission, Programme IDEAS-ERC, Project 227977-SMScom and Programme FP7-PEOPLE-2011-IEF, Project 302648-RunMore and by the Dutch national program COMMIT.

Author information

Authors and Affiliations

  1. Dipartimento di Elettronica, Informazione e Bioingegneria (DEIB), Politecnico di Milano, Piazza L. da Vinci 32, Milan, Italy

    Gianpaolo Cugola & Matteo Matteucci

  2. Department of Computer Science, Vrije Universiteit, De Boelelaan 1081A, 1081 HV , Amsterdam, The Netherlands

    Alessandro Margara

  3. Faculty of Informatics, Università della Svizzera Italiana, Via Buffi 13, Lugano, Switzerland

    Giordano Tamburrelli

Authors
  1. Gianpaolo Cugola
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alessandro Margara
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Matteo Matteucci
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Giordano Tamburrelli
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Giordano Tamburrelli.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cugola, G., Margara, A., Matteucci, M. et al. Introducing uncertainty in complex event processing: model, implementation, and validation. Computing 97, 103–144 (2015). https://doi.org/10.1007/s00607-014-0404-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00607-014-0404-y

Keywords

Mathematics Subject Classification

Search

Navigation