Temporal Pattern Recognition in Large Scale Graphs
Pages 250 - 251
Abstract
Many application domains involve monitoring the temporal evolution of large-scale graph data structures. Unfortunately, this task is not well supported by modern programming paradigms and frameworks for large-scale data processing. This paper presents ongoing work on the implementation of FlowGraph, a framework to recognize temporal patterns over properties of large-scale graphs. FlowGraph combines the programming paradigm of traditional graph computation frameworks with the temporal pattern detection capabilities of Complex Event Recognition (CER) systems. In a nutshell, FlowGraph distributes the graph data structure across multiple nodes that also contribute to the computation and store partial results for pattern detection. It exploits temporal properties to defer as much as possible expensive computations, to sustain a high rate of changes.
References
[1]
Alexander Artikis, Alessandro Margara, Martin Ugarte, Stijn Vansummeren, and Matthias Weidlich. 2017. Complex Event Recognition Languages: Tutorial. In Proc. of the Int. Conf. on Dist. and Event-based Sys. (DEBS '17). ACM, 7--10.
[2]
Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache Flink: Stream and Batch Processing in a Single Engine. IEEE Data Engineering Bullettin 38, 4 (2015), 28--38.
[3]
Gianpaolo Cugola and Alessandro Margara. 2010. TESLA: A Formally Defined Event Specification Language. In Proc. of the Int. Conf. on Dist. Event-Based Sys. (DEBS '10). ACM, 50--61.
[4]
Gianpaolo Cugola and Alessandro Margara. 2012. Processing Flows of Information: From Data Stream to Complex Event Processing. Comput. Surveys 44, 3 (2012), 15:1--15:62.
[5]
Benjamin Erb, Dominik Meissner, Jakob Pietron, and Frank Kargl. 2017. Chronograph: A Distributed Processing Platform for Online and Batch Computations on Event-sourced Graphs. In Proceedings of the International Conference on Distributed and Event-based Systems (DEBS '17). ACM, 78--87.
[6]
Anand Padmanabha Iyer, Li Erran Li, Tathagata Das, and Ion Stoica. 2016. Time-evolving Graph Processing at Scale. In Proceedings of the International Workshop on Graph Data Management Experiences and Systems (GRADES '16). ACM, 5:1--5:6.
[7]
V. Kalavri, V. Vlassov, and S. Haridi. 2018. High-Level Programming Abstractions for Distributed Graph Processing. IEEE Transactions on Knowledge and Data Engineering 30, 2 (Feb 2018), 305--324.
[8]
Grzegorz Malewicz, Matthew H. Austern, Aart J.C Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: A System for Large-scale Graph Processing. In Proceedings of the International Conference on Management of Data (SIGMOD '10). ACM, 135--146.
[9]
Robert Ryan McCune, Tim Weninger, and Greg Madey. 2015. Thinking Like a Vertex: A Survey of Vertex-Centric Frameworks for Large-Scale Distributed Graph Processing. Comput. Surveys 48, 2 (2015), 25:1--25:39.
[10]
Youshan Miao, Wentao Han, Kaiwei Li, Ming Wu, Fan Yang, Lidong Zhou, Vijayan Prabhakaran, Enhong Chen, and Wenguang Chen. 2015. ImmortalGraph: A System for Storage and Analysis of Temporal Graphs. Transactions on Storage 11, 3(2015), 14:1--14:34.
[11]
Matei Zaharia, Tathagata Das, Haoyuan Li, Timothy Hunter, Scott Shenker, and Ion Stoica. 2013. Discretized Streams: Fault-tolerant Streaming Computation at Scale. In Proc. of the Symp. on Op. Sys. Princ. (SOSP '13). ACM, 423--438.
Index Terms
- Temporal Pattern Recognition in Large Scale Graphs
Recommendations
A fast deterministic detection of small pattern graphs in graphs without large cliques
AbstractWe show that for several pattern graphs on four vertices (e.g., C 4), their induced copies in host graphs with n vertices and no clique on k + 1 vertices can be deterministically detected in O ( n 2.5719 k 0.3176 + n 2 k 2 ) time for k ...
Large Induced Forests in Graphs
In this article, we prove three theorems. The first is that every connected graph of order n and size m has an induced forest of order at least 8n-2m-2/9 with equality if and only if such a graph is obtained from a tree by expanding every vertex to a ...
Connectivity of k-extendable graphs with large k
Discrete mathematics and theoretical computer science (DMTCS)Let G be a simple connected graph on 2n vertices with perfect matching. For a given positive integer k (0 ≤ k ≤ n - 1), G is k-extendable if any matching of size k in G is contained in a perfect matching of G. It is proved that if G is a k-extendable ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2019
291 pages
ISBN:9781450367943
DOI:10.1145/3328905
Copyright © 2019 Owner/Author.
Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 June 2019
Check for updates
Author Tags
Qualifiers
- Poster
- Research
- Refereed limited
Conference
DEBS '19: The 13th ACM International Conference on Distributed and Event-based Systems
June 24 - 28, 2019
Darmstadt, Germany
Acceptance Rates
DEBS '19 Paper Acceptance Rate 13 of 47 submissions, 28%;
Overall Acceptance Rate 145 of 583 submissions, 25%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 122Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)1
Reflects downloads up to 31 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in