Journal Home > Volume 2 , Issue 1

As real-world graphs are often evolving over time, interest in analyzing the temporal behavior of graphs has grown. Herein, we propose Auxo, a novel temporal graph management system to support temporal graph analysis. It supports both efficient global and local queries with low space overhead. Auxo organizes temporal graph data in spatio-temporal chunks. A chunk spans a particular time interval and covers a set of vertices in a graph. We propose chunk layout and chunk splitting designs to achieve the desired efficiency and the abovementioned goals. First, by carefully choosing the time split policy, Auxo achieves linear complexity in both space usage and query time. Second, graph splitting further improves the worst-case query time, and reduces the performance variance introduced by splitting operations. Third, Auxo optimizes the data layout inside chunks, thereby significantly improving the performance of traverse-based graph queries. Experimental evaluation showed that Auxo achieved 2.9× to 12.1× improvement for global queries, and 1.7× to 2.7× improvement for local queries, as compared with state-of-the-art open-source solutions.


menu
Abstract
Full text
Outline
About this article

Auxo: A Temporal Graph Management System

Show Author's information Wentao Han( )Kaiwei LiShimin ChenWenguang Chen
Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China.
Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China.

Abstract

As real-world graphs are often evolving over time, interest in analyzing the temporal behavior of graphs has grown. Herein, we propose Auxo, a novel temporal graph management system to support temporal graph analysis. It supports both efficient global and local queries with low space overhead. Auxo organizes temporal graph data in spatio-temporal chunks. A chunk spans a particular time interval and covers a set of vertices in a graph. We propose chunk layout and chunk splitting designs to achieve the desired efficiency and the abovementioned goals. First, by carefully choosing the time split policy, Auxo achieves linear complexity in both space usage and query time. Second, graph splitting further improves the worst-case query time, and reduces the performance variance introduced by splitting operations. Third, Auxo optimizes the data layout inside chunks, thereby significantly improving the performance of traverse-based graph queries. Experimental evaluation showed that Auxo achieved 2.9× to 12.1× improvement for global queries, and 1.7× to 2.7× improvement for local queries, as compared with state-of-the-art open-source solutions.

Keywords: graphs and networks, temporal databases, composite structures

References(33)

[1]
L. Yang, L. Qi, Y. Zhao, B. Gao, and T. Liu, Link analysis using time series of web graphs, in Proceedings of the Sixteenth ACM Conference on Information and Knowledge Management, CIKM 2007, Lisbon, Portugal, 2007, pp. 1011-1014.
DOI
[2]
C. Wilson, B. Boe, A. Sala, K. P. N. Puttaswamy, and B. Y. Zhao, User interactions in social networks and their implications, in Proceedings of the 2009 EuroSys Conference, Nuremberg, Germany, 2009, pp. 205-218.
DOI
[3]
J. Leskovec, J. M. Kleinberg, and C. Faloutsos, Graphs over time: Densification laws, shrinking diameters and possible explanations, in Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, IL, USA, 2005, pp. 177-187.
DOI
[4]
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, in Proceedings of the Ninth European Conference on Computer Systems EuroSys’14, New York, NY, USA, 2014, pp. 1:1-1:14.
DOI
[5]
U. Khurana and A. Deshpande, Efficient snapshot retrieval over historical graph data, in Data Engineering (ICDE), 2013 IEEE 29th International Conference on, 2013, pp. 997-1008.
DOI
[6]
B. Salzberg and V. J. Tsotras, Comparison of access methods for time-evolving data, ACM Comput. Surv., vol. 31, pp. 158-221, 1999.
[7]
R. Cheng, J. Hong, A. Kyrola, Y. Miao, X. Weng, M. Wu, F. Yang, L. Zhou, F. Zhao, and E. Chen, Kineograph: Taking the pulse of a fast-changing and connected world, in Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys’12, New York, NY, USA, 2012, pp. 85-98.
DOI
[8]
F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber, Bigtable: A distributed storage system for structured data, ACM Transactions on Computer Systems, vol. 26, no. 2, p. 4, 2008.
[9]
P. E. O’Neil, E. Cheng, D. Gawlick, and E. J. O’Neil, The log-structured merge-tree (lsm-tree), Acta Inf., vol. 33, no. 4, pp. 351-385, 1996.
[10]
D. Lomet and B. Salzberg, Access methods for multiversion data, in Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data SIGMOD’89, New York, NY, USA, 1989, pp. 315-324
DOI
[11]
G. Karypis and V. Kumar, METIS—Unstructured graph partitioning and sparse matrix ordering system, version 2.0, Tech. Rep., 1995.
[12]
M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some simplified np-complete problems, in Proceedings of the Sixth annual ACM Symposium on Theory of Computing, 1974, pp. 47-63.
DOI
[13]
Neo4j, http://neo4j.com/, 2015.
[14]
PostgreSQL, http://www.postgresql.org/, 2015.
[15]
HBase, http://hbase.apache.org/, 2015.
[16]
J. Kunegis, Konect: The koblenz network collection, in Proceedings of the 22nd International Conference on World Wide Web Companion, 2013, pp. 1343-1350
DOI
[17]
D. A. Spielmat and S.-H. Teng, Spectral partitioning works: Planar graphs and finite element meshes, in Proceedings of 37th Annual Symposium on Foundations of Computer Science, 1996, pp. 96-105.
DOI
[18]
P. Boldi, M. Santini, and S. Vigna, A large time-aware web graph, SIGIR Forum, vol. 42, no. 2, pp. 33-38, 2008.
[19]
J. Leskovec, J. Kleinberg, and C. Faloutsos, Graphs over time: Densification laws, shrinking diameters and possible explanations, in Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, KDD’05, New York, NY, USA, 2005, pp. 177-187.
DOI
[20]
C. Wilson, B. Boe, R. Sala, K. P. N. Puttaswamy, and B. Y. Zhao, User interactions in social networks and their implications, in Proceedings of the 4th ACM European Conference on Computer Systems, 2009.
DOI
[21]
K. Lerman, R. Ghosh, and J. H. Kang, Centrality metric    for dynamic networks, in Proceedings of the Eighth Workshop on Mining and Learning with Graphs, 2010, pp. 70-77.
DOI
[22]
J. Tang, I. Leontiadis, S. Scellato, V. Nicosia, C. Mascolo, M. Musolesi, and V. Latora, Applications of temporal graph metrics to real-world networks, in Temporal Networks, 2013, pp. 135-159.
DOI
[23]
S. Huang, J. Cheng, and H. Wu, Temporal graph traversals: Definitions, algorithms, and applications, arXiv preprint arXiv:1401.1919, 2014.
[24]
B. Gedik and R. Bordawekar, Disk-based management of interaction graphs, IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 11, pp. 2689-2702, 2014.
[25]
R. Zhang and M. Stradling, The hv-tree: A memory hierarchy aware version index, Proc. VLDB Endow., vol. 3, pp. 397-408, 2010.
[26]
D. Lomet, R. Barga, M. F. Mokbel, G. Shegalov, R. Wang, and Y. Zhu, Immortal db: Transaction time support for sql server, in Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data SIGMOD’05, New York, NY, USA, 2005, pp. 939-941
DOI
[27]
D. Lomet, M. Hong, R. Nehme, and R. Zhang, Transaction time indexing with version compression, Proceedings of the VLDB Endowment, vol. 1, no. 1, pp. 870-881, 2008.
[28]
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 Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD’10, New York, NY, USA, 2010, pp. 135-146.
DOI
[29]
Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein, Graphlab: A new framework for parallel machine learning, arXiv Preprint arXiv:1006.4990, 2010.
[30]
J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin, Powergraph: Distributed graph-parallel computation on natural graphs, in Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI’12, Berkeley, CA, USA, 2012, pp. 17-30.
[31]
V. Prabhakaran, M. Wu, X. Weng, F. McSherry, L. Zhou, and M. Haridasan, Managing large graphs on multicores with graph awareness, in Proceedings of the 2012 USENIX Annual Technical Conference (USENIX ATC’12), Boston, MA, USA, 2012, pp. 41-52
[32]
A. Kyrola, G. Blelloch, and C. Guestrin, Graphchi: Large-scale graph computation on just a PC, in Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI’12, Berkeley, CA, USA, 2012, pp. 31-46.
[33]
A. Roy, I. Mihailovic, and W. Zwaenepoel, X-stream: Edge-centric graph processing using streaming partitions, in Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP’13, New York, NY, USA, 2013, pp. 472-488.
DOI
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 08 May 2018
Accepted: 27 May 2018
Published: 19 November 2018
Issue date: March 2019

Copyright

© The author(s) 2019

Acknowledgements

This work was supported by the National High-Tech Development Plan of China (No. 2015AA015306) and the National Natural Science Foundation of China (No. 61772302).

Rights and permissions

Return