abstract

FlowGraph: Distributed temporal pattern detection over dynamically evolving graphs

Author:

Hassan Nazeer ChaudhryAuthors Info & Claims

DEBS '19: Proceedings of the 13th ACM International Conference on Distributed and Event-based Systems

Pages 272 - 275

https://doi.org/10.1145/3328905.3332303

Published: 24 June 2019 Publication History

Abstract

Temporally evolving graphs are an indispensable requisite of modern-day big data processing pipelines. Existing graph processing systems mostly focus on static graphs and lack the essential support for pattern detection and event processing in graph-shaped data. On the other hand, stream processing systems support event and pattern detection, but they are inadequate for graph processing. This work lies at the intersection of the graph and stream processing domains with the following objectives: (i) It introduces the syntax of a language for the detection of temporal patterns in large-scale graphs. (ii) It presents a novel data structure called distributed label store (DLS) to efficiently store graph computation results and discover temporal patterns within them. The proposed system, called FlowGraph, unifies graph-shaped data with stream processing by observing graph changes as a stream flowing into the system. It provides an API to handle temporal patterns that predicate on the results of graph computations with traditional graph computations.

References

[1]

Renzo Angles and Claudio Gutierrez. 2008. Survey of Graph Database Models. ACM Comput. Surv. 40, 1, Article 1 (Feb. 2008), 39 pages.

Digital Library

[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]

Raymond Cheng, Ji Hong, Aapo Kyrola, Youshan Miao, Xuetian Weng, Ming Wu, Fan Yang, Lidong Zhou, Feng Zhao, and Enhong Chen. 2012. Kineograph: Taking the Pulse of a Fast-changing and Connected World. In Proceedings of the 7th ACM European Conference on Computer Systems (EuroSys '12). ACM, New York, NY, USA, 85--98.

Digital Library

[4]

Gianpaolo Cugola and Alessandro Margara. 2012. Processing Flows of Information: From Data Stream to Complex Event Processing. ACM Comput. Surv. 44, 3, Article 15 (June 2012), 62 pages.

Digital Library

[5]

Benjamin Erb, Dominik Meissner, Frank Kargl, Benjamin A. Steer, Felix Cuadrado, Domagoj Margan, and Peter Pietzuch. 2018. Graphtides: A Framework for Evaluating Stream-based Graph Processing Platforms. In Proceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) (GRADES-NDA '18). ACM, New York, NY, USA, Article 3, 10 pages.

Digital Library

[6]

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 11th ACM International Conference on Distributed and Event-based Systems (DEBS '17). ACM, New York, NY, USA, 78--87.

Digital Library

[7]

Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed Graph-parallel Computation on Natural Graphs. In Proceedings of the Conference on Operating Systems Design and Implementation (OSDI'12). USENIX Association, 17--30.

[8]

Joseph E. Gonzalez, Reynold S. Xin, Ankur Dave, Daniel Crankshaw, Michael J. Franklin, and Ion Stoica. 2014. GraphX: Graph Processing in a Distributed Dataflow Framework. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI'14). USENIX Association, Berkeley, CA, USA, 599--613. http://dl.acm.org/citation.cfm?id=2685048.2685096

Digital Library

[9]

Wentao Han, Youshan Miao, Kaiwei Li, Ming Wu, Fan Yang, Lidong Zhou, Vijayan Prabhakaran, Wenguang Chen, and Enhong Chen. 2014. Chronos: A Graph Engine for Temporal Graph Analysis. In Proceedings of the Ninth European Conference on Computer Systems (EuroSys '14). ACM, New York, NY, USA, Article 1, 14 pages.

Digital Library

[10]

Anand Padmanabha Iyer, Li Erran Li, Tathagata Das, and Ion Stoica. 2016. Time-evolving Graph Processing at Scale. In Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems (GRADES '16). ACM, New York, NY, USA, Article 5, 6 pages.

Digital Library

[11]

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.

[12]

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.

Digital Library

[13]

Alessandro Margara, Jacopo Urbani, Frank van Harmelen, and Henri Bal. 2014. Streaming the Web. Web Semantics 25, C (March 2014), 24--44.

Digital Library

[14]

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.

Digital Library

[15]

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. Trans. Storage 11, 3, Article 14 (July 2015), Article 14, 34 pages.

Digital Library

[16]

Marko A. Rodriguez and Peter Neubauer. 2010. The Graph Traversal Pattern. CoRR abs/1004.1001 (2010). arXiv:1004.1001 http://arxiv.org/abs/1004.1001

[17]

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.

Digital Library

Cited By

Chaudhry HRossi M(2024)Optimising Queries for Pattern Detection Over Large Scale Temporally Evolving GraphsIEEE Access10.1109/ACCESS.2024.341735212(86790-86808)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3417352
Coimbra MEsteves SFrancisco AVeiga L(2022)VeilGraph: incremental graph stream processingJournal of Big Data10.1186/s40537-022-00565-89:1Online publication date: 23-Feb-2022
https://doi.org/10.1186/s40537-022-00565-8
Chaudhry HJaved YKulsoom FMehmood ZKhan ZShoaib UJanjua S(2021)Sentiment Analysis of before and after Elections: Twitter Data of U.S. Election 2020Electronics10.3390/electronics1017208210:17(2082)Online publication date: 27-Aug-2021
https://doi.org/10.3390/electronics10172082
Show More Cited By

Index Terms

FlowGraph: Distributed temporal pattern detection over dynamically evolving graphs
1. Information systems
  1. Data management systems
2. Theory of computation
  1. Models of computation
    1. Streaming models

Recommendations

A new temporal interpretation of cluster editing
Abstract
The NP-complete graph problem Cluster Editing seeks to transform a static graph into a disjoint union of cliques by making the fewest possible edits to the edges. We introduce a natural interpretation of this problem in temporal graphs, whose ...
A survey on dynamic graph processing on GPUs: concepts, terminologies and systems
Abstract
Graphs that are used to model real-world entities with vertices and relationships among entities with edges, have proven to be a powerful tool for describing real-world problems in applications. In most real-world scenarios, entities and their ...
Mengerian Temporal Graphs Revisited
Fundamentals of Computation Theory
Abstract
A temporal graph $G$ is a graph that changes with time. More specifically, it is a pair $(G, λ)$ where G is a graph and $λ$ is a function on the edges of G that describes when each edge $e \in E (G)$ is active. Given vertices $s, t \in V (G)$ , a temporal $s, t$ -path is a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DEBS '19: Proceedings of the 13th ACM International Conference on Distributed and Event-based Systems

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

Abstract
Research
Refereed limited

Conference

DEBS '19

Sponsor:

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

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
163
Total Downloads

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

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chaudhry HRossi M(2024)Optimising Queries for Pattern Detection Over Large Scale Temporally Evolving GraphsIEEE Access10.1109/ACCESS.2024.341735212(86790-86808)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3417352
Coimbra MEsteves SFrancisco AVeiga L(2022)VeilGraph: incremental graph stream processingJournal of Big Data10.1186/s40537-022-00565-89:1Online publication date: 23-Feb-2022
https://doi.org/10.1186/s40537-022-00565-8
Chaudhry HJaved YKulsoom FMehmood ZKhan ZShoaib UJanjua S(2021)Sentiment Analysis of before and after Elections: Twitter Data of U.S. Election 2020Electronics10.3390/electronics1017208210:17(2082)Online publication date: 27-Aug-2021
https://doi.org/10.3390/electronics10172082
Huang XWang HLi LZhu YHu C(2021)Microbloggers’ interest inference using a subgraph streamIntelligent Data Analysis10.3233/IDA-19504225:2(397-417)Online publication date: 4-Mar-2021
https://dl.acm.org/doi/10.3233/IDA-195042
Coimbra MFrancisco AVeiga L(2021)An analysis of the graph processing landscapeJournal of Big Data10.1186/s40537-021-00443-98:1Online publication date: 9-Apr-2021
https://doi.org/10.1186/s40537-021-00443-9
Benczúr ABéres FKelen DPálovics RMargara AValle E(2021)Tutorial on graph stream analyticsProceedings of the 15th ACM International Conference on Distributed and Event-based Systems10.1145/3465480.3468293(168-171)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1145/3465480.3468293

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