Auxo: A Temporal Graph Management System
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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Tsinghua University Press
2019-03-01
|
| Series: | Big Data Mining and Analytics |
| Subjects: | |
| Online Access: | https://www.sciopen.com/article/10.26599/BDMA.2018.9020030 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832568936147714048 |
|---|---|
| author | Wentao Han Kaiwei Li Shimin Chen Wenguang Chen |
| author_facet | Wentao Han Kaiwei Li Shimin Chen Wenguang Chen |
| author_sort | Wentao Han |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-b315ecf1aa6e4cf887f4acb7de3de260 |
| institution | Kabale University |
| issn | 2096-0654 |
| language | English |
| publishDate | 2019-03-01 |
| publisher | Tsinghua University Press |
| record_format | Article |
| series | Big Data Mining and Analytics |
| spelling | doaj-art-b315ecf1aa6e4cf887f4acb7de3de2602025-02-02T23:47:57ZengTsinghua University PressBig Data Mining and Analytics2096-06542019-03-0121587110.26599/BDMA.2018.9020030Auxo: A Temporal Graph Management SystemWentao Han0Kaiwei Li1Shimin Chen2Wenguang Chen3<institution content-type="dept">Department of Computer Science and Technology</institution>, <institution>Tsinghua University</institution>, <city>Beijing</city> <postal-code>100084</postal-code>, <country>China</country>.<institution content-type="dept">Department of Computer Science and Technology</institution>, <institution>Tsinghua University</institution>, <city>Beijing</city> <postal-code>100084</postal-code>, <country>China</country>.<institution content-type="dept">Institute of Computing Technology</institution>, <institution>Chinese Academy of Sciences</institution>, <city>Beijing</city> <postal-code>100190</postal-code>, <country>China</country>.<institution content-type="dept">Department of Computer Science and Technology</institution>, <institution>Tsinghua University</institution>, <city>Beijing</city> <postal-code>100084</postal-code>, <country>China</country>.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.https://www.sciopen.com/article/10.26599/BDMA.2018.9020030graphs and networkstemporal databasescomposite structures |
| spellingShingle | Wentao Han Kaiwei Li Shimin Chen Wenguang Chen Auxo: A Temporal Graph Management System Big Data Mining and Analytics graphs and networks temporal databases composite structures |
| title | Auxo: A Temporal Graph Management System |
| title_full | Auxo: A Temporal Graph Management System |
| title_fullStr | Auxo: A Temporal Graph Management System |
| title_full_unstemmed | Auxo: A Temporal Graph Management System |
| title_short | Auxo: A Temporal Graph Management System |
| title_sort | auxo a temporal graph management system |
| topic | graphs and networks temporal databases composite structures |
| url | https://www.sciopen.com/article/10.26599/BDMA.2018.9020030 |
| work_keys_str_mv | AT wentaohan auxoatemporalgraphmanagementsystem AT kaiweili auxoatemporalgraphmanagementsystem AT shiminchen auxoatemporalgraphmanagementsystem AT wenguangchen auxoatemporalgraphmanagementsystem |