Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2024, Vol. 18 Issue (4) : 184106    https://doi.org/10.1007/s11704-023-2656-1
Architecture
A survey on dynamic graph processing on GPUs: concepts, terminologies and systems
Hongru GAO1,2, Xiaofei LIAO1, Zhiyuan SHAO1,2(), Kexin LI1,2, Jiajie CHEN1, Hai JIN1
1. National Engineering Research Center for Big Data Technology and System/Services Computing Technology and System Lab/Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
2. Zhejiang Lab, Hangzhou 311121, China
 Download: PDF(6283 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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 relationships are subject to constant changes. Graphs that record such changes are called dynamic graphs. In recent years, the widespread application scenarios of dynamic graphs have stimulated extensive research on dynamic graph processing systems that continuously ingest graph updates and produce up-to-date graph analytics results. As the scale of dynamic graphs becomes larger, higher performance requirements are demanded to dynamic graph processing systems. With the massive parallel processing power and high memory bandwidth, GPUs become mainstream vehicles to accelerate dynamic graph processing tasks. GPU-based dynamic graph processing systems mainly address two challenges: maintaining the graph data when updates occur (i.e., graph updating) and producing analytics results in time (i.e., graph computing). In this paper, we survey GPU-based dynamic graph processing systems and review their methods on addressing both graph updating and graph computing. To comprehensively discuss existing dynamic graph processing systems on GPUs, we first introduce the terminologies of dynamic graph processing and then develop a taxonomy to describe the methods employed for graph updating and graph computing. In addition, we discuss the challenges and future research directions of dynamic graph processing on GPUs.

Keywords dynamic graphs      graph processing      graph algorithms      GPUs     
Corresponding Author(s): Zhiyuan SHAO   
Just Accepted Date: 09 March 2023   Issue Date: 24 May 2023
 Cite this article:   
Hongru GAO,Xiaofei LIAO,Zhiyuan SHAO, et al. A survey on dynamic graph processing on GPUs: concepts, terminologies and systems[J]. Front. Comput. Sci., 2024, 18(4): 184106.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-023-2656-1
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I4/184106
Symbol Description
G=(V,E) A graph G (directed or undirected), where V is the vertex set and E is the edge set.
|V| The number of vertices in graph G.
|E| The number of edges in graph G.
Nin(u),Nout(u) In-neighbor set and out-neighbor set of vertex u in a directed graph.
din(u),dout(u) In-degree and out-degree of vertex u, denoting the number of in-neighbors and out-neighbors of u, respectively.
N(u) Neighbor set of vertex u in an undirected graph.
d(u) Degree of vertex u, denoting the number of neighbors of u.
Tab.1  Notations for graphs
Fig.1  Examples of undirected, directed, undirected weighted and directed weighted graphs (the number attached to an edge is the edge weight). (a) An example undirected graph; (b) an example directed graph; (c) an example undirected weighted graph; (d) an example directed weighted graph
Fig.2  Graph representations used to represent the example graph in Fig.1(d). (a) Adjacency matrix A = (aij); (b) coordinate list; (c) compressed sparse row (dotted arrows indicate the starting offsets of the out-neighbors of vertices); (d) adjacency list (solid arrows denote pointers to objects, and the notation “/” denotes pointers that do not refer to any object)
  
Fig.3  Updating the example graph in Fig.1(d) with a series of graph updates listed in chronological order
Stream graph Snapshot sequence Temporal graph
Analytics workloads online online & offline offline
Historical graph data not supported coarse-grained (with snapshots) fine-grained (with timestamps)
Ingesting updates single & batch (with fixed batch size) batch (with fixed time interval) not mentioned
Preferred scenarios high time-sensitivity low time-sensitivity & long-term relation short-term relation
Tab.2  Comparisons between the stream graph model, the snapshot sequence model, and the temporal graph model
Fig.4  Schematic figures of the stream graph, snapshot sequence, temporal graph models under edge insertions (edges will not be removed once they are inserted), where t0, t1, t2, t3 denote time points
Fig.5  General workflow of dynamic graph processing on GPUs
Fig.6  Schematic figures of graph updating methods (blue parts show the process of merging graph updates). (a) Array-based space management; (b) chain-based space management; (c) CSR-based space management
Fig.7  An example of incremental computing processes
Fig.8  A taxonomy of GPU-based dynamic graph processing systems
Methods Typical systems
array-based space management cuSTINGER [69], Hornet [72], GPU-LSM [77]
CSR-based space management DCSR [67], GPMA [65], LPMA [78]
chain-based space management aimGraph [68], faimGraph [70], Slabhash [71]
Tab.3  A classification of GPU-based dynamic graph updating systems
Fig.9  An example of the graph representation used in Hornet and the process of conducting edge insertions on Hornet. (a) An example graph representation of Hornet (solid arrows indicate pointers of vertices to their edges); (b) inserting three edges (0, 4), (1, 4), (1, 5) to the Hornet in Fig.9(a)
Fig.10  The process of conducting insertions on GPU-LSM (grey parts indicate that the levels are filled, while white parts indicate empty levels)
Fig.11  The graph representation of DCSR and edge insertions to DCSR. (a) An initial DCSR’s graph representation of the example graph in Fig.1(d) (the segments are all of length 3, separated by bold lines); (b) inserting two edges (0, 3, 7) and (0, 4, 5) to the DCSR in Fig.11(a) (modifications to the initial DCSR are highlighted with grey)
Fig.12  An example of the basic PMA structure and a graph representation combining PMA with CSR. (a) Inserting an entry 27 to the PMA structure (the interval values in a tree node are used to locate the corresponding segment in the array; the grey part shows the process of re-balancing the PMA); (b) a graph representation that combines PMA with CSR (diverse colors indicate the neighbors and sentinels of different vertices)
Fig.13  Data structures used in faimGraph, including vertex data blocks, pages, a vertex queue, a page queue, and a memory manager
Fig.14  An example of the graph representation in Slabhash (buckets and slabs are edge blocks of different capacities)
Methods Typical systems
recomputing Tripathy et al. [83], T?dling et al. [84]
incremental computing Evograph [44], Makkar et al. [74], Zhang et al. [82],
HyPR [85], Guo et al. [75], Khanda et al. [86]
Tab.4  A classification of GPU-based dynamic graph computing systems
  
  
  
  
  
  
1 X, Shi Z, Zheng Y, Zhou H, Jin L, He B, Liu Q S Hua . Graph processing on GPUs: a survey. ACM Computing Surveys, 2018, 50( 6): 81
2 B, Li S, Gao Y, Liang Y, Kang T, Prestby Y, Gao R Xiao . Estimation of regional economic development indicator from transportation network analytics. Scientific Reports, 2020, 10( 1): 2647
3 M, Alkhamees S, Alsaleem M, Al-Qurishi M, Al-Rubaian A Hussain . User trustworthiness in online social networks: a systematic review. Applied Soft Computing, 2021, 103: 107159
4 S, Karamati J, Young R Vuduc . An energy-efficient single-source shortest path algorithm. In: Proceedings of 2018 IEEE International Parallel and Distributed Processing Symposium. 2018, 1080−1089
5 J, Yang J, McAuley J Leskovec . Community detection in networks with node attributes. In: Proceedings of the 13th International Conference on Data Mining. 2013, 1151−1156
6 J, Zhong B He . Medusa: simplified graph processing on GPUs. IEEE Transactions on Parallel and Distributed Systems, 2014, 25( 6): 1543–1552
7 K Ammar . Techniques and systems for large dynamic graphs. In: Proceedings of 2016 on SIGMOD’16 PhD Symposium. 2016, 7−11
8 J, Brailovskaia J Margraf . The relationship between active and passive Facebook use, Facebook flow, depression symptoms and Facebook addiction: a three-month investigation. Journal of Affective Disorders Reports, 2022, 10: 100374
9 M A, Muin K, Kapti T Yusnanto . Campus website security vulnerability analysis using Nessus. International Journal of Computer and Information System, 2022, 3( 2): 79–82
10 S R S, Gowda R, King M R P Kumar . Real-time tweets streaming and comparison using naïve Bayes classifier. In: Proceedings of the 3rd International Conference on Data Science, Machine Learning and Applications. 2023, 103−110
11 X, Qiu W, Cen Z, Qian Y, Peng Y, Zhang X, Lin J Zhou . Real-time constrained cycle detection in large dynamic graphs. Proceedings of the VLDB Endowment, 2018, 11( 12): 1876–1888
12 C, Ye Y, Li B, He Z, Li J Sun . GPU-accelerated graph label propagation for real-time fraud detection. In: Proceedings of 2021 International Conference on Management of Data. 2021, 2348−2356
13 A D, Kent L M, Liebrock J C Neil . Authentication graphs: analyzing user behavior within an enterprise network. Computers & Security, 2015, 48: 150–166
14 B, Wheatman H Xu . Packed compressed sparse row: a dynamic graph representation. In: Proceedings of 2018 IEEE High Performance Extreme Computing Conference. 2018, 1−7
15 P, Kumar H H Huang . GraphOne: a data store for real-time analytics on evolving graphs. ACM Transactions on Storage, 2019, 15( 4): 29
16 X, Zhu G, Feng M, Serafini X, Ma J, Yu L, Xie A, Aboulnaga W Chen . LiveGraph: a transactional graph storage system with purely sequential adjacency list scans. Proceedings of the VLDB Endowment, 2020, 13( 7): 1020–1034
17 Leo D, De P Boncz . Teseo and the analysis of structural dynamic graphs. Proceedings of the VLDB Endowment, 2021, 14( 6): 1053–1066
18 R, Cheng J, Hong A, Kyrola Y, Miao X, Weng M, Wu F, Yang L, Zhou F, Zhao E Chen . Kineograph: taking the pulse of a fast-changing and connected world. In: Proceedings of the 7th ACM European Conference on Computer Systems. 2012, 85−98
19 X, Shi B, Cui Y, Shao Y Tong . Tornado: a system for real-time iterative analysis over evolving data. In: Proceedings of 2016 International Conference on Management of Data. 2016, 417−430
20 Vora K, Gupta R, Xu G. KickStarter: fast and accurate computations on streaming graphs via trimmed approximations. In: Proceedings of the 22nd International Conference on Architectural Support for Programming Languages and Operating Systems. 2017, 237−251
21 F, Sheng Q, Cao H, Cai J, Yao C Xie . GraPU: accelerate streaming graph analysis through preprocessing buffered updates. In: Proceedings of the ACM Symposium on Cloud Computing. 2018, 301−312
22 Mariappan M, Vora K. GraphBolt: dependency-driven synchronous processing of streaming graphs. In: Proceedings of the 14th EuroSys Conference 2019. 2019, 25
23 X, Shi X, Luo J, Liang P, Zhao S, Di B, He H Jin . Frog: asynchronous graph processing on GPU with hybrid coloring model. IEEE Transactions on Knowledge and Data Engineering, 2018, 30( 1): 29–42
24 Sengupta D, Sundaram N, Zhu X, Willke T L, Young J, Wolf M, Schwan K. GraphIn: an online high performance incremental graph processing framework. In: Proceedings of the 22nd International Conference on Parallel and Distributed Computing. 2016, 319−333
25 T H, Cormen C E, Leiserson R L, Rivest C Stein . Introduction to Algorithms. 3rd ed. Cambridge: MIT Press, 2009
26 Z, Shao R, Li D, Hu X, Liao H Jin . Improving performance of graph processing on FPGA-DRAM platform by two-level vertex caching. In: Proceedings of 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 2019, 320−329
27 M T, Goodrich R Tamassia . Algorithm Design and Applications. Hoboken: Wiley Hoboken, 2015
28 O, Green P, Yalamanchili L M Munguía . Fast triangle counting on the GPU. In: Proceedings of the 4th Workshop on Irregular Applications: Architectures and Algorithms. 2014, 1−8
29 S, Park W, Lee B, Choe S G Lee . A survey on personalized PageRank computation algorithms. IEEE Access, 2019, 7: 163049–163062
30 P, Boldi M, Santini S Vigna . PageRank as a function of the damping factor. In: Proceedings of the 14th International Conference on World Wide Web. 2005, 557−566
31 N, Ohsaka T, Maehara K I Kawarabayashi . Efficient PageRank tracking in evolving networks. In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015, 875−884
32 S, Brin L Page . The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 1998, 30( 1-7): 107–117
33 S D, Kamvar T H, Haveliwala C D, Manning G H Golub . Extrapolation methods for accelerating PageRank computations. In: Proceedings of the 12th International Conference on World Wide Web. 2003, 261−270
34 G, Hou X, Chen S, Wang Z Wei . Massively parallel algorithms for personalized PageRank. Proceedings of the VLDB Endowment, 2021, 14( 9): 1668–1680
35 A, Mandal Hasan M Al . A distributed k-core decomposition algorithm on spark. In: Proceedings of 2017 IEEE International Conference on Big Data. 2017, 976−981
36 F, Victor C G, Akcora Y R, Gel M Kantarcioglu . Alphacore: data depth based core decomposition. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021, 1625−1633
37 H, Esfandiari S, Lattanzi V S Mirrokni . Parallel and streaming algorithms for K-core decomposition. In: Proceedings of the 35th International Conference on Machine Learning. 2018, 1396−1405
38 J I, Alvarez-Hamelin L, Dall’Asta A, Barrat A Vespignani . Large scale networks fingerprinting and visualization using the k-core decomposition. In: Proceedings of the 18th International Conference on Neural Information Processing Systems. 2005, 41−50
39 L, Zeng L, Zou M T, Özsu L, Hu F Zhang . GSI: GPU-friendly subgraph isomorphism. In: Proceedings of the 36th International Conference on Data Engineering. 2020, 1249−1260
40 A, Zaki M, Attia D, Hegazy S Amin . Comprehensive survey on dynamic graph models. International Journal of Advanced Computer Science and Applications, 2016, 7( 2): 573–582
41 Li D, Li W, Chen Y, Lin M, Lu S. Learning-based dynamic graph stream sketch. In: Proceedings of the 25th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. 2021, 383−394
42 D, Margan P Pietzuch . Large-scale stream graph processing: doctoral symposium. In: Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems. 2017, 378−381
43 F, Harary G Gupta . Dynamic graph models. Mathematical and Computer Modelling, 1997, 25( 7): 79–87
44 D, Sengupta S L Song . EvoGraph: on-the-fly efficient mining of evolving graphs on GPU. In: Proceedings of the 32nd International Conference on High Performance Computing. 2017, 97−119
45 A P, Iyer Q, Pu K, Patel J E, Gonzalez I Stoica . TEGRA: efficient Ad-Hoc analytics on evolving graphs. In: Proceedings of the 18th USENIX Symposium on Networked Systems Design and Implementation. 2021, 337−355
46 C, Aggarwal K Subbian . Evolutionary network analysis: a survey. ACM Computing Surveys, 2014, 47( 1): 10
47 Vlasselaer V, Van L, Akoglu T, Eliassi-Rad M, Snoeck B Baesens . Guilt-by-constellation: fraud detection by suspicious clique memberships. In: Proceedings of the 48th Hawaii International Conference on System Sciences. 2015, 918−927
48 S, Xu X, Liao Z, Shao Q, Hua H Jin . Maximal clique enumeration problem on graphs: status and challenges. SCIENTIA SINICA Informationis, 2022, 52( 5): 784–803
49 A McGregor . Graph stream algorithms: a survey. ACM SIGMOD Record, 2014, 43( 1): 9–20
50 K, Vora R, Gupta G Xu . Synergistic analysis of evolving graphs. ACM Transactions on Architecture and Code Optimization, 2016, 13( 4): 32
51 F, Sheng Q, Cao J Yao . Exploiting buffered updates for fast streaming graph analysis. IEEE Transactions on Computers, 2021, 70( 2): 255–269
52 Zhang J. A survey on streaming algorithms for massive graphs. In: Aggarwal C C, Wang H X, eds. Managing and Mining Graph Data. New York: Springer, 2010, 393−420
53 Bar-Yossef Z, Kumar R, Sivakumar D. Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 2002, 623−632
54 P, Zhao C C, Aggarwal M Wang . gSketch: on query estimation in graph streams. Proceedings of the VLDB Endowment, 2011, 5( 3): 193–204
55 H, Zhang P, Lofgren A Goel . Approximate personalized PageRank on dynamic graphs. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016, 1315−1324
56 K, Shin S, Oh J, Kim B, Hooi C Faloutsos . Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Transactions on Knowledge Discovery from Data, 2020, 14( 2): 12
57 A, Basak J, Lin R, Lorica X, Xie Z, Chishti A, Alameldeen Y Xie . SAGA-bench: software and hardware characterization of streaming graph analytics workloads. In: Proceedings of 2020 IEEE International Symposium on Performance Analysis of Systems and Software. 2020, 12−23
58 C, Ren E, Lo B, Kao X, Zhu R Cheng . On querying historical evolving graph sequences. Proceedings of the VLDB Endowment, 2011, 4( 11): 726–737
59 U, Khurana A Deshpande . Efficient snapshot retrieval over historical graph data. In: Proceedings of the 29th International Conference on Data Engineering. 2013, 997−1008
60 Han W, Miao Y, Li K, Wu M, Yang F, Zhou L, Prabhakaran V, Chen W, Chen E. Chronos: a graph engine for temporal graph analysis. In: Proceedings of the 9th European Conference on Computer Systems. 2014, 1
61 B, Steer F, Cuadrado R Clegg . Raphtory: streaming analysis of distributed temporal graphs. Future Generation Computer Systems, 2020, 102: 453–464
62 G, Rossetti R Cazabet . Community discovery in dynamic networks: a survey. ACM Computing Surveys, 2019, 51( 2): 35
63 P Holme . Modern temporal network theory: a colloquium. The European Physical Journal B, 2015, 88( 9): 234
64 P, Holme J Saramäki . Temporal networks. Physics Reports, 2012, 519( 3): 97–125
65 M, Sha Y, Li B, He K L Tan . Accelerating dynamic graph analytics on GPUs. Proceedings of the VLDB Endowment, 2017, 11( 1): 107–120
66 Mariappan M, Che J, Vora K. DZiG: sparsity-aware incremental processing of streaming graphs. In: Proceedings of the 16th European Conference on Computer Systems. 2021, 83−98
67 King J, Gilray T, Kirby R M, Might M. Dynamic sparse-matrix allocation on GPUs. In: Proceedings of the 31st International Conference on High Performance Computing. 2016, 61−80
68 M, Winter R, Zayer M Steinberger . Autonomous, independent management of dynamic graphs on GPUs. In: Proceedings of 2017 IEEE High Performance Extreme Computing Conference. 2017, 1−7
69 O, Green D A Bader . cuSTINGER: supporting dynamic graph algorithms for GPUs. In: Proceedings of 2016 IEEE High Performance Extreme Computing Conference. 2016, 1−6
70 M, Winter D, Mlakar R, Zayer H P, Seidel M Steinberger . faimGraph: high performance management of fully-dynamic graphs under tight memory constraints on the GPU. In: Proceedings of the SC18: International Conference for High Performance Computing, Networking, Storage and Analysis. 2018, 754−766
71 M A, Awad S, Ashkiani S D, Porumbescu J D Owens . Dynamic graphs on the GPU. In: Proceedings of 2020 IEEE International Parallel and Distributed Processing Symposium. 2020, 739−748
72 F, Busato O, Green N, Bombieri D A Bader . Hornet: an efficient data structure for dynamic sparse graphs and matrices on GPUs. In: Proceedings of 2018 IEEE High Performance extreme Computing Conference. 2018, 1−7
73 D, Ediger R, McColl J, Riedy D A Bader . STINGER: high performance data structure for streaming graphs. In: Proceedings of 2012 IEEE Conference on High Performance Extreme Computing. 2012, 1−5
74 D, Makkar D A, Bader O Green . Exact and parallel triangle counting in dynamic graphs. In: Proceedings of the 24th International Conference on High Performance Computing. 2017, 2−12
75 W, Guo Y, Li M, Sha K L Tan . Parallel personalized PageRank on dynamic graphs. Proceedings of the VLDB Endowment, 2017, 11( 1): 93–106
76 W, Jaiyeoba K Skadron . GraphTinker: a high performance data structure for dynamic graph processing. In: Proceedings of 2019 IEEE International Parallel and Distributed Processing Symposium. 2019, 1030−1041
77 S, Ashkiani S, Li M, Farach-Colton N, Amenta J D Owens . GPU LSM: a dynamic dictionary data structure for the GPU. In: Proceedings of 2018 IEEE International Parallel and Distributed Processing Symposium. 2018, 430−440
78 F, Zhang L, Zou Y Yu . LPMA - an efficient data structure for dynamic graph on GPUs. In: Proceedings of the 22nd International Conference on Web Information Systems Engineering 2021. 2021, 469−484
79 D, Ediger J, Riedy D A, Bader H Meyerhenke . Computational graph analytics for massive streaming data. In: Sarbazi-Azad H, Zomaya A Y, eds. Large Scale Network-Centric Distributed Systems. Hoboken: John Wiley & Sons, Inc., 2013, 619−648
80 M A, Bender H Hu . An adaptive packed-memory array. ACM Transactions on Database Systems, 2007, 32( 4): 26–es
81 S, Ashkiani M, Farach-Colton J D Owens . A dynamic hash table for the GPU. In: Proceedings of 2018 IEEE International Parallel and Distributed Processing Symposium. 2018, 419−429
82 T Zhang . Efficient incremental PageRank of evolving graphs on GPU. In: Proceedings of 2017 International Conference on Computer Systems, Electronics and Control. 2017, 1232−1236
83 A, Tripathy F, Hohman D H, Chau O Green . Scalable K-core decomposition for static graphs using a dynamic graph data structure. In: Proceedings of 2018 IEEE International Conference on Big Data. 2018, 1134−1141
84 D, Tödling M, Winter M Steinberger . Breadth-first search on dynamic graphs using dynamic parallelism on the GPU. In: Proceedings of 2019 IEEE High Performance Extreme Computing Conference. 2019, 1−7
85 H K, Giri M, Haque D S Banerjee . HyPR: hybrid page ranking on evolving graphs. In: Proceedings of the 27th International Conference on High Performance Computing, Data, and Analytics. 2020, 62−71
86 A, Khanda S, Srinivasan S, Bhowmick B, Norris S K Das . A parallel algorithm template for updating single-source shortest paths in large-scale dynamic networks. IEEE Transactions on Parallel and Distributed Systems, 2022, 33( 4): 929–940
87 T, Zhang J, Zhang W, Shu M Y, Wu X Liang . Efficient graph computation on hybrid CPU and GPU systems. The Journal of Supercomputing, 2015, 71( 4): 1563–1586
88 P, Desikan N, Pathak J, Srivastava V Kumar . Incremental page rank computation on evolving graphs. In: Proceedings of the Special Interest Tracks and Posters of the 14th International Conference on World Wide Web. 2005, 1094−1095
89 D, Ediger K, Jiang J, Riedy D A Bader . Massive streaming data analytics: a case study with clustering coefficients. In: Proceedings of 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum. 2010, 1−8
90 K, Hanauer M, Henzinger C Schulz . Recent advances in fully dynamic graph algorithms. In: Proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks. 2022, 1.11
91 P, Fournier-Viger G, He C, Cheng J, Li M, Zhou J C W, Lin U Yun . A survey of pattern mining in dynamic graphs. WIREs Data Mining and Knowledge Discovery, 2020, 10( 6): e1372
92 T C O’Connell . A survey of graph algorithms under extended streaming models of computation. In: Ravi S S, Shukla S K, eds. Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz. Dordrecht: Springer, 2009, 455−476
93 J, Skarding B, Gabrys K Musial . Foundations and modeling of dynamic networks using dynamic graph neural networks: a survey. IEEE Access, 2021, 9: 79143–79168
94 S M, Kazemi R, Goel K, Jain I, Kobyzev A, Sethi P, Forsyth P Poupart . Representation learning for dynamic graphs: a survey. The Journal of Machine Learning Research, 2020, 21( 1): 70
95 M, Besta M, Fischer V, Kalavri M, Kapralov T Hoefler . Practice of streaming processing of dynamic graphs: concepts, models, and systems. IEEE Transactions on Parallel and Distributed Systems, 2021,
https://doi.org/10.1109/TPDS.2021.3131677
96 Z, Ren Y, Gu C, Li F, Li G Yu . GPU-based dynamic hyperspace hash with full concurrency. Data Science and Engineering, 2021, 6( 3): 265–279
97 O Green . HashGraph-scalable hash tables using a sparse graph data structure. ACM Transactions on Parallel Computing, 2021, 8( 2): 11
98 M A, Awad S, Ashkiani R, Johnson M, Farach-Colton J D Owens . Engineering a high-performance GPU B-tree. In: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming. 2019, 145−157
99 Z, Yan Y, Lin L, Peng W Zhang . Harmonia: a high throughput B+tree for GPUs. In: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming. 2019, 133−144
100 Y, Zhang Y, Liang J, Zhao F, Mao L, Gu X, Liao H, Jin H, Liu S, Guo Y, Zeng H, Hu C, Li J, Zhang B Wang . EGraph: efficient concurrent GPU-based dynamic graph processing. IEEE Transactions on Knowledge and Data Engineering, 2022,
https://doi.org/10.1109/TKDE.2022.3171588
[1] FCS-22656-OF-HG_suppl_1 Download
[1] Xianghao XU, Fang WANG, Hong JIANG, Yongli CHENG, Dan FENG, Peng FANG. A disk I/O optimized system for concurrent graph processing jobs[J]. Front. Comput. Sci., 2024, 18(3): 183105-.
[2] Xinqiao LV, Wei XIAO, Yu ZHANG, Xiaofei LIAO, Hai JIN, Qiangsheng HUA. An effective framework for asynchronous incremental graph processing[J]. Front. Comput. Sci., 2019, 13(3): 539-551.
[3] Wuyang JU,Jianxin LI,Weiren YU,Richong ZHANG. iGraph: an incremental data processing system for dynamic graph[J]. Front. Comput. Sci., 2016, 10(3): 462-476.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed