Manuel Then
Timo Kersten
Abstract
Analytical graph algorithms commonly compute metrics for a graph at one point in time. In practice it is often also of interest how metrics change over time, e.g., to find trends. For this purpose, algorithms must be executed for multiple graph snapshots.
We present Single Algorithm Multiple Snapshots (SAMS), a novel approach to execute algorithms concurrently for multiple graph snapshots. SAMS automatically transforms graph algorithms to leverage similarities between the analyzed graph snapshots. The automatic transformation interleaves algorithm executions on multiple snapshots, synergistically shares their graph accesses and traversals, and optimizes the algorithm's data layout. Thus, SAMS can amortize the cost of random data accesses and improve memory bandwidth utilization---two main cost factors in graph analytics. We extensively evaluate SAMS using six well-known algorithms and multiple synthetic as well as real-world graph datasets. Our measurements show that in multi-snapshot analyses, SAMS offers runtime improvements of up to two orders of magnitude over traditional snapshot-at-a-time execution.
- J. R. Allen, K. Kennedy, C. Porterfield, and J. Warren. Conversion of control dependence to data dependence. In SIGACT-SIGPLAN, pages 177--189, 1983. Google Scholar
Digital Library
- S. Beamer, K. Asanović, and D. Patterson. Direction-Optimizing Breadth-First Search. In SC, pages 12:1--12:10, 2012. Google ScholarDigital Library
- M. Clavel, F. Durán, S. Eker, P. Lincoln, N. Marti-Oliet, J. Meseguer, and J. F. Quesada. Maude: specification and programming in rewriting logic. Theoretical Computer Science, 285(2):187--243, 2002. Google ScholarDigital Library
- W. R. Cook and B. Wiedermann. Remote batch invocation for SQL databases. In DBPL, 2011.Google Scholar
- J. E. Gonzalez, R. S. Xin, A. Dave, D. Crankshaw, M. J. Franklin, and I. Stoica. Graphx: Graph processing in a distributed dataflow framework. In OSDI, pages 599--613, 2014. Google ScholarDigital Library
- R. Guravannavar and S. Sudarshan. Rewriting procedures for batched bindings. VLDB, 1(1):1107--1123, 2008. Google ScholarDigital Library
- W. Han, Y. Miao, K. Li, M. Wu, F. Yang, L. Zhou, V. Prabhakaran, W. Chen, and E. Chen. Chronos: A graph engine for temporal graph analysis. EuroSys, pages 1:1--1:14, 2014. Google ScholarDigital Library
- S. Hong, H. Chafi, E. Sedlar, and K. Olukotun. Green-Marl: A DSL for easy and efficient graph analysis. In ASPLOS, pages 349--362, 2012. Google ScholarDigital Library
- A. Iosup, T. Hegeman, W. Ngai, S. Heldens, A. Prat, T. Manhardt, H. Chafi, M. Capota, N. Sundaram, M. Anderson, et al. LDBC graphalytics: A benchmark for large-scale graph analysis on parallel and distributed platforms. PVLDB, 9(12):1317--1328, 2016. Google ScholarDigital Library
- U. Khurana and A. Deshpande. Efficient snapshot retrieval over historical graph data. In IEEE ICDE, pages 997--1008, 2013. Google ScholarDigital Library
- J. Kunegis. KONECT: the Koblenz network collection. In WWW, pages 1343--1350, 2013. Google ScholarDigital Library
- J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins. Microscopic evolution of social networks. In SIGKDD, pages 462--470, 2008. Google ScholarDigital Library
- J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In SIGKDD, pages 177--187, 2005. Google ScholarDigital Library
- P. Macko, V. J. Marathe, D. W. Margo, and M. I. Seltzer. LLAMA: Efficient graph analytics using large multiversioned arrays. In ICDE, pages 363--374. IEEE, April 2015.Google ScholarCross Ref
- G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD, pages 135--146, 2010. Google ScholarDigital Library
- R. R. McCune, T. Weninger, and G. Madey. Thinking like a vertex: A survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Comput. Surv., 48(2):25:1--25:39, Oct. 2015. Google ScholarDigital Library
- R. K. Pan and J. Saramäki. Path lengths, correlations, and centrality in temporal networks. Physical Review E, 84(1):016105, 2011.Google ScholarCross Ref
- J. Shun and G. E. Blelloch. Ligra: A lightweight graph processing framework for shared memory. In SIGPLAN, pages 135--146, 2013. Google ScholarDigital Library
- M. Then, M. Kaufmann, F. Chirigati, T.-A. Hoang-Vu, K. Pham, A. Kemper, T. Neumann, and H. T. Vo. The more the merrier: efficient multi-source graph traversal. PVLDB, 8(4):449--460, 2014. Google ScholarDigital Library
- S. Wasserman and K. Faust. Social network analysis: Methods and applications, volume 8. Cambridge university press, 1994.Google Scholar
- G. Winskel. The formal semantics of programming languages. MIT press, 2001. Google ScholarDigital Library
- H. Wu, J. Cheng, S. Huang, Y. Ke, Y. Lu, and Y. Xu. Path problems in temporal graphs. PVLDB, 7(9):721--732, 2014. Google ScholarDigital Library
- W. Xie, Y. Tian, Y. Sismanis, A. Balmin, and P. J. Haas. Dynamic interaction graphs with probabilistic edge decay. In IEEE ICDE, pages 1143--1154, April 2015.Google ScholarCross Ref
Index Terms
- Automatic algorithm transformation for efficient multi-snapshot analytics on temporal graphs
Recommendations
An optimal multi-writer snapshot algorithm
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computingAn m-component, n-process snapshot object is an abstraction of shared memory that consists of m words and allows up to n processes to concurrently execute the following two types of operations: write(i,v), which writes v into the ith word, and scan(), ...
Matching transformation graphs of cubic bipartite plane graphs
In this paper, we explore some properties of the matching transformation graph of a connected cubic bipartite plane graph G. We prove that if M is any perfect matching of G, then G has at least two disjoint M-alternating faces. This result is sharp in ...
Efficient minus and signed domination in graphs
An efficient minus (respectively, signed) dominating function of a graph G=(V,E) is a function f:V { 1,0,1} (respectively, { 1,1}) such that u Nv]f(u)=1 for all v V, where Nv]={v} {u|(u,v) E}. The efficient minus (respectively, signed) domination ...
Comments