Reasoning on the Efficiency of Distributed Complex Event Processing

• Autorzy: Akili Samira , Weidlich Matthias

Identyfikatory

DOI

10.3233/FI-2021-2017

• Języki publikacji: EN

Abstrakty

EN

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 query among the nodes of a network. To this end, a query is modularized and individual query operators are assigned to nodes, especially those that act as data sources. Existing solutions for such operator placement, however, are limited in that they assume all query results to be gathered at one designated node, commonly referred to as a sink. Hence, existing techniques postulate a hierarchical structure of the network that generates and processes the event data. This largely neglects the optimisation potential that stems from truly decentralised query evaluation with potentially many sinks. To address this gap, in this paper, we propose Multi-Sink Evaluation (MuSE) graphs as a formal computational model to evaluate common CEP queries in a decentralised manner. We further prove the completeness of query evaluation under this model. Striving for distributed CEP that can scale to large volumes of high-frequency event streams, we show how to reason on the network costs induced by distributed query evaluation and prune inefficient query execution plans. As such, our work lays the foundation for distributed CEP that is both, sound and efficient.

Słowa kluczowe

EN

distributed systems; complex event processing; operator placement

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 179, nr 2
• Strony: 113--134
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Akili Samira

• Humboldt-Universität zu Berlin, Berlin, Germany

autor

Weidlich Matthias

• Humboldt-Universität zu Berlin, Berlin, Germany

Bibliografia

• [1] Teymourian K, Rohde M, Paschke A. Knowledge-based processing of complex stock market events. In: Rundensteiner EA, Markl V, Manolescu I, Amer-Yahia S, Naumann F, Ari I (eds.), 15th International Conference on Extending Database Technology, EDBT ’12, Berlin, Germany, March 27-30, 2012, Proceedings. ACM. ISBN 978-1-4503-0790-1, 2012 pp. 594-597. doi:10.1145/2247596.2247674.
• [2] Artikis A, et al. Heterogeneous Stream Processing and Crowdsourcing for Urban Traffic Management. In: Amer-Yahia S, Christophides V, Kementsietsidis A, Garofalakis MN, Idreos S, Leroy V (eds.), Proceedings of the 17th International Conference on Extending Database Technology, EDBT 2014, Athens, Greece, March 24-28, 2014. OpenProceedings.org, 2014 pp. 712-723. doi:10.5441/002/edbt.2014.77.
• [3] Fernandez RC, Weidlich M, Pietzuch PR, Gal A. Scalable stateful stream processing for smart grids. In: Bellur U, Kothari R (eds.), The 8th ACM International Conference on Distributed Event-Based Systems, DEBS ’14, Mumbai, India, May 26-29, 2014. ACM. ISBN 978-1-4503-2737-4, 2014 pp. 276-281. doi:10.1145/2611286.2611326.
• [4] Starks F, Goebel V, Kristiansen S, Plagemann T. Mobile Distributed Complex Event Processing. Ubi Sumus? Quo Vadimus? In: Mobile Big Data, pp. 147-180. Springer, 2018. doi:10.1007/978-3-319-67925-9_7.
• [5] Nardelli M, Cardellini V, Grassi V, PRESTI FL. Efficient Operator Placement for Distributed Data Stream Processing Applications. IEEE Transactions on Parallel and Distributed Systems, 2019. doi:10.1109/TPDS.2019.2896115.
• [6] Chen J, Ramaswamy L, Lowenthal DK, Kalyanaraman S. Comet: Decentralized complex event detection in mobile delay tolerant networks. In: 2012 IEEE 13th International Conference on Mobile Data Management. IEEE, 2012 pp. 131-136. doi:10.1109/MDM.2012.18.
• [7] Pietzuch P, Ledlie J, Shneidman J, Roussopoulos M, Welsh M, Seltzer M. Network-aware operator placement for stream-processing systems. In: ICDE’06. IEEE, 2006 pp. 49-49. doi:10.1109/ICDE.2006.105.
• [8] Rizou S, Durr F, Rothermel K. Solving the multi-operator placement problem in large-scale operator networks. In: 2010 Proceedings of 19th International Conference on Computer Communications and Networks. IEEE, 2010 pp. 1-6. doi:10.1109/ICCCN.2010.5560127.
• [9] Cardellini V, Grassi V, Lo Presti F, Nardelli M. Optimal operator placement for distributed stream processing applications. In: Proceedings of the 10th ACM International Conference on Distributed and Event-based Systems. ACM, 2016 pp. 69-80. doi:10.1145/2933267.2933312.
• [10] Lakshmanan GT, Li Y, Strom R. Placement strategies for internet-scale data stream systems. IEEE Internet Computing, 2008. 12(6):50-60. doi:10.1109/MIC.2008.129.
• [11] Srivastava U, Munagala K, Widom J. Operator placement for in-network stream query processing. In: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM, 2005 pp. 250-258. doi:10.1145/1065167.1065199.
• [12] Chatzimilioudis G, Cuzzocrea A, Gunopulos D, Mamoulis N. A novel distributed framework for optimizing query routing trees in wireless sensor networks via optimal operator placement. Journal of Computer and System Sciences, 2013. 79(3):349-368. doi:10.1016/j.jcss.2012.09.013.
• [13] Artikis A, Margara A, Ugarte M, Vansummeren S, Weidlich M. Complex Event Recognition Languages: Tutorial. In: Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems, DEBS 2017, Barcelona, Spain, June 19-23, 2017. ACM. ISBN 978-1-4503-5065-5, 2017 pp. 7-10. doi:10.1145/3093742.3095106.
• [14] Flouris I, Giatrakos N, Deligiannakis A, Garofalakis M, Kamp M, Mock M. Issues in complex event processing: Status and prospects in the big data era. Journal of Systems and Software, 2017. pp. 217-236. doi:10.1016/j.jss.2016.06.011.
• [15] Cugola G, Margara A. Deployment strategies for distributed complex event processing. Computing, 2013. 95(2):129-156. doi:10.1007/s00607-012-0217-9.
• [16] Starks F, Plagemann TP. Operator placement for efficient distributed complex event processing in manets. In: 2015 IEEE 11th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob). IEEE, 2015 pp. 83-90. doi:10.1109/WiMOB.2015.7347944.
• [17] Brenna L, Demers AJ, Gehrke J, Hong M, Ossher J, Panda B, Riedewald M, Thatte M, White WM. Cayuga: a high-performance event processing engine. In: Chan CY, Ooi BC, Zhou A (eds.), Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China, June 12-14, 2007. ACM. ISBN 978-1-59593-686-8, 2007 pp. 1100-1102. doi:10.1145/1247480.1247620.
• [18] Agrawal J, Diao Y, Gyllstrom D, Immerman N. Efficient pattern matching over event streams. In: Wang JT (ed.), Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008. ACM. ISBN 978-1-60558-102-6, 2008 pp. 147-160. doi:10.1145/1376616.1376634.
• [19] Anicic D, Rudolph S, Fodor P, Stojanovic N. Stream reasoning and complex event processing in ETALIS. Semantic Web, 2012. 3(4):397-407. doi:10.3233/SW-2011-0053.
• [20] Dousson C, Maigat PL. Chronicle Recognition Improvement Using Temporal Focusing and Hierarchization. In: Veloso MM (ed.), IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007. 2007 pp. 324-329. URL http://ijcai.org/Proceedings/07/Papers/050.pdf.
• [21] Artikis A, Sergot MJ, Paliouras G. An Event Calculus for Event Recognition. IEEE Trans. Knowl. Data Eng., 2015. 27(4):895-908. doi:10.1109/TKDE.2014.2356476.
• [22] Weidlich M, Mendling J, Gal A. Net-Based Analysis of Event Processing Networks-The Fast Flower Delivery Case. In: Colom JM, Desel J (eds.), Application and Theory of Petri Nets and Concurrency - 34th International Conference, PETRI NETS 2013, Milan, Italy, June 24-28, 2013. Proceedings, volume 7927 of Lecture Notes in Computer Science. Springer. ISBN 978-3-642-38696-1, 2013 pp. 270-290. doi:10.1007/978-3-642-38697-8\_15.
• [23] Macià H, Valero V, Díaz G, Boubeta-Puig J, Ortiz G. Complex Event Processing Modeling by Prioritized Colored Petri Nets. IEEE Access, 2016. 4:7425-7439. doi:10.1109/ACCESS.2016.2621718.
• [24] Boubeta-Puig J, Díaz G, Macià H, Valero V, Ortiz G. MEdit4CEP-CPN: An approach for complex event processing modeling by prioritized colored petri nets. Inf. Syst., 2019. 81:267-289. doi:10.1016/j.is.2017.11.005.
• [25] proANT. Transport Robots. 2016. http://www.insystems.de/en/produkte/proant-transport-roboter/.
• [26] Akdere M, Çetintemel U, Tatbul N. Plan-based complex event detection across distributed sources. Proceedings of the VLDB Endowment, 2008. 1(1):66-77. doi:10.14778/1453856.1453869.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).