Open Access
Issue
Published:
*19 November 2018*

Cite this article:

Han W, Li K, Chen S, et al.
Auxo: A Temporal Graph Management System.
Big Data Mining and Analytics,
2019, 2(1): 58-71.
https://doi.org/10.26599/BDMA.2018.9020030
Download citation

538

Views

13

Downloads

Citations

7

Crossref

2

WoS

7

Scopus

0

CSCD

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

menu

Abstract

Full text

Outline

About this article

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

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

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

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

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

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

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

[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

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

[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

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

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

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

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

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

[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

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

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

Publication history

Copyright

Acknowledgements

Rights and permissions

Received: 08 May 2018

Accepted: 27 May 2018

Published:
19 November 2018

Issue date: March 2019

© The author(s) 2019

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).