Skip to content

axtonsun/awesome-streaming-graphs

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

11 Commits
README.md
README.md
 
 

Repository files navigation

awesome-streaming-graphs

Awesome

Must-read papers on streaming graph

Content

1. Keynote
2. Survey
3. System
4. Graph Stream Summarization
5. Exact Algorithms
 5.1 Subgraph Matching  5.2 Regular Path Query
6. Approximation Algorithms
 6.1 Triangle Count  6.2 Butterfly Count

Keynote

  1. Streaming Graph Processing and Analytics. [slides] [DEBS'20 video] [PKUMOD'20 video]

    M. Tamer Özsu.

  2. Graph Processing: A Panaromic View and Some open Problems. [slides] [VLDB'19 video] [PKUMOD'20 video]

    M. Tamer Özsu.

  3. An Introduction to Graph Analytics Platform - Very Short Version. [slides]

    M. Tamer Özsu.

Survey papers

  1. 图数据流的模型、算法和系统[J]. 大数据, 2018, 4(4): 44-55. [paper]

    李友焕, 邹磊.

  2. Graph stream algorithms: a survey. SIGMOD Rec. 43(1): 9-20 (2014) [paper]

    Andrew McGregor.

System

  1. RisGraph: A Real-Time Streaming System for Evolving Graphs to Support Sub-millisecond Per-update Analysis at Millions Ops/s. SIGMOD Conference 2021: 513-527 [paper]

    Guanyu Feng, Zixuan Ma, Daixuan Li, Shengqi Chen, Xiaowei Zhu, Wentao Han, Wenguang Chen

  2. GraphOne: A Data Store for Real-time Analytics on Evolving Graphs. FAST 2019: 249-263 [paper] [slides] [video]

    Pradeep Kumar, H. Howie Huang.

Graph Stream Summarization

  1. Auxo: A Scalable and Efficient Graph Stream Summarization Structure. Proc. VLDB Endow. 16(6): 1386-1398 (2023) [paper]

    Zhiguo Jiang, Hanhua Chen, Hai Jin.

  2. Horae: A Graph Stream Summarization Structure for Efficient Temporal Range Query. ICDE 2022: 2792-2804 [paper]

    Ming Chen, Renxiang Zhou, Hanhua Chen, Jiang Xiao, Hai Jin, Bo Li.

  3. Scube: Efficient Summarization for Skewed Graph Streams. ICDCS 2022: 100-110 [paper]

    Ming Chen, Renxiang Zhou, Hanhua Chen, Hai Jin.

  4. Graph Stream Sketch: Summarizing Graph Streams With High Speed and Accuracy. IEEE Trans. Knowl. Data Eng. 35(6): 5901-5914 (2023) [paper]

    Xiangyang Gou, Lei Zou, Chenxingyu Zhao, Tong Yang.

  5. Fast and Accurate Graph Stream Summarization. ICDE 2019: 1118-1129 [paper]

    Xiangyang Gou, Lei Zou, Chenxingyu Zhao, Tong Yang.

  6. Incremental Lossless Graph Summarization. KDD 2020: 317-327 [paper] [slides] [video]

    Jihoon Ko, Yunbum Kook, Kijung Shin.

  7. Graph Stream Summarization: From Big Bang to Big Crunch. SIGMOD Conference 2016: 1481-1496 [paper] [slides]

    Nan Tang, Qing Chen, Prasenjit Mitra.

Exact Algorithms

Subgraph Matching

  1. TC-Match: Fast Time-constrained Continuous Subgraph Matching. Proc. VLDB Endow. 17(11): 2791-2804 (2024) [paper] [code]

    Jianye Yang, Sheng Fang, Zhaoquan Gu, Ziyi Ma, Xuemin Lin, Zhihong Tian.

  2. CSM-TopK: Continuous Subgraph Matching with TopK Density Constraints. ICDE 2024: 3084-3097 [paper] [code]

    Chuchu Gao, Youhuan Li, Zhibang Yang, Xu Zhou.

  3. Efficient Multi-Query Oriented Continuous Subgraph Matching. ICDE 2024: 3230-3243 [paper]

    Ziyi Ma, Jianye Yang, Xu Zhou, Guoqing Xiao, Jianhua Wang, Liang Yang, Kenli Li, Xuemin Lin.

  4. Time-Constrained Continuous Subgraph Matching Using Temporal Information for Filtering and Backtracking. ICDE 2024: 3257-3269 [paper]

    Seunghwan Min, Jihoon Jang, Kunsoo Park, Dora Giammarresi, Giuseppe F. Italiano, Wook-Shin Han.

  5. NewSP: A New Search Process for Continuous Subgraph Matching over Dynamic Graphs. ICDE 2024: 3324-3337 [paper]

    Ziming Li, Youhuan Li, Xinhuan Chen, Lei Zou, Yang Li, Xiaofeng Yang, Hongbo Jiang.

  6. Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction. Proc. ACM Manag. Data 1(1): 15:1-15:26 (2023) [paper] [code] [video]

    Rongjian Yang, Zhijie Zhang, Weiguo Zheng, Jeffrey Xu Yu.

  7. An In-Depth Study of Continuous Subgraph Matching. Proc. VLDB Endow. 15(7): 1403-1416 (2022) [paper] [code]

    Xibo Sun, Shixuan Sun, Qiong Luo, Bingsheng He.

  8. RapidFlow: An Efficient Approach to Continuous Subgraph Matching. Proc. VLDB Endow. 15(11): 2415-2427 (2022) [paper] [code]

    Shixuan Sun, Xibo Sun, Bingsheng He, Qiong Luo.

  9. RapidMatch: A Holistic Approach to Subgraph Query Processing. Proc. VLDB Endow. 14(2): 176-188 (2020) [paper] [code]

    Shixuan Sun, Xibo Sun, Yulin Che, Qiong Luo, Bingsheng He.

  10. Symmetric Continuous Subgraph Matching with Bidirectional Dynamic Programming. Proc. VLDB Endow. 14(8): 1298-1310 (2021) [paper] [code]

    Seunghwan Min, Sung Gwan Park, Kunsoo Park, Dora Giammarresi, Giuseppe F. Italiano, Wook-Shin Han.

  11. Space-Efficient Subgraph Search Over Streaming Graph With Timing Order Constraint. IEEE Trans. Knowl. Data Eng. 34(9): 4453-4467 (2022) [paper]

    Youhuan Li, Lei Zou, M. Tamer Özsu, Dongyan Zhao.

  12. Time Constrained Continuous Subgraph Search Over Streaming Graphs. ICDE 2019: 1082-1093 [paper] [code]

    Youhuan Li, Lei Zou, M. Tamer Özsu, Dongyan Zhao.

  13. TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data. SIGMOD Conference 2018: 411-426 [paper]

    Kyoungmin Kim, In Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, Geonhwa Jeong.

  14. General dynamic Yannakakis: conjunctive queries with theta joins under updates. VLDB J. 29(2-3): 619-653 (2020) [paper]

    Muhammad Idris, Martín Ugarte, Stijn Vansummeren, Hannes Voigt, Wolfgang Lehner.

  15. The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates. SIGMOD Conference 2017: 1259-1274 [paper]

    Muhammad Idris, Martín Ugarte, Stijn Vansummeren.

  16. Graphflow: An active graph database. SIGMOD Conference 2017: 1695-1698 [paper]

    Chathura Kankanamge, Siddhartha Sahu, Amine Mhedhbi, Jeremy Chen, Semih Salihoglu.

  17. A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs. EDBT 2015: 157-168 [paper] [slides]

    Sutanay Choudhury, Lawrence B. Holder, George Chin Jr., Khushbu Agarwal, John Feo.

  18. Incremental graph pattern matching. ACM Trans. Database Syst. 38(3): 18 (2013) [paper]

    Wenfei Fan, Xin Wang, Yinghui Wu.

  19. Incremental graph pattern matching. SIGMOD Conference 2011: 925-936 [paper]

    Wenfei Fan, Jianzhong Li, Jizhou Luo, Zijing Tan, Xin Wang, Yinghui Wu.

Regular Path Query

  1. MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs. Proc. ACM Manag. Data 2(1): 5:1-5:26 (2024) [paper]

    Siyuan Zhang, Zhenying He, Yinan Jing, Kai Zhang, X. Sean Wang.

  2. LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs. Proc. VLDB Endow. 17(5): 1047-1059 [paper] [code]

    Xiangyang Gou, Xinyi Ye, Lei Zou, Jeffrey Xu Yu.

  3. Evaluating complex queries on streaming graphs. ICDE 2022: 272-285 [paper] [code] [slides] [video]

    Anil Pacaci, Angela Bonifati, M. Tamer Özsu.

  4. Regular Path Query Evaluation on Streaming Graphs. SIGMOD Conference 2020: 1415-1430 [paper] [slides] [video]

    Anil Pacaci, Angela Bonifati, M. Tamer Özsu.

Approximation Algorithms

Triangle Count

  1. Compact Estimator for Streaming Triangle Counting. IEEE Trans. Knowl. Data Eng. 36(8): 3712-3724 (2024) [paper]

    Jiqing Gu, Chao Song, Haipeng Dai, Li Lu, Ming Liu.

  2. Sliding window-based approximate triangle counting with bounded memory usage. VLDB J. 32(5): 1087-1110 (2023) [paper] [code]

    Xiangyang Gou, Lei Zou.

  3. Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges. SIGMOD Conference 2021: 645-657 [paper] [code]

    Xiangyang Gou, Lei Zou.

  4. Distributed Triangle Approximately Counting Algorithms in Simple Graph Stream. ACM Trans. Knowl. Discov. Data 16(4): 79:1-79:43 (2022) [paper] [code]

    Xu Yang, Chao Song, Mengdi Yu, Jiqing Gu, Ming Liu.

  5. Distributed Triangle Counting Algorithms in Simple Graph Stream. ICPADS 2019: 294-301 [paper]

    Mengdi Yu, Chao Song, Jiqing Gu, Ming Liu.

  6. CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams. ACM Trans. Knowl. Discov. Data 15(3): 38:1-38:30 (2021) [paper] [code]

    Kijung Shin, Euiwoong Lee, Jinoh Oh, Mohammad Hammoud, Christos Faloutsos.

  7. Tri-Fly: Distributed Estimation of Global and Local Triangle Counts in Graph Streams. PAKDD (3) 2018: 651-663 [paper] [code]

    Kijung Shin, Mohammad Hammoud, Euiwoong Lee, Jinoh Oh, Christos Faloutsos.

  8. Fast, Accurate and Provable Triangle Counting in Fully Dynamic Graph Streams. ACM Trans. Knowl. Discov. Data 14(2): 12:1-12:39 (2020) [paper] [code]

    Kijung Shin, Sejoon Oh, Jisu Kim, Bryan Hooi, Christos Faloutsos.

  9. Think Before You Discard: Accurate Triangle Counting in Graph Streams with Deletions. ECML/PKDD (2) 2018: 141-157 [paper] [code]

    Kijung Shin, Jisu Kim, Bryan Hooi, Christos Faloutsos.

  10. Temporal locality-aware sampling for accurate triangle counting in real graph streams. VLDB J. 29(6): 1501-1525 (2020) [paper] [code]

    Dongjin Lee, Kijung Shin, Christos Faloutsos.

  11. WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams. . ICDM 2017: 1087-1092 [paper] [code]

    Kijung Shin.

  12. REPT: A Streaming Algorithm of Approximating Global and Local Triangle Counts in Parallel. ICDE 2019: 758-769 [paper]

    Pinghui Wang, Peng Jia, Yiyan Qi, Yu Sun, Jing Tao, Xiaohong Guan

  13. FURL: Fixed-memory and uncertainty reducing local triangle counting for multigraph streams. Data Min. Knowl. Discov. 33(5): 1225-1253 (2019) [paper] [Code]

    Minsoo Jung, Yongsub Lim, Sunmin Lee, U Kang.

  14. Memory-Efficient and Accurate Sampling for Counting Local Triangles in Graph Streams: From Simple to Multigraphs. ACM Trans. Knowl. Discov. Data 12(1): 4:1-4:28 (2018) [paper] [Code]

    Yongsub Lim, Minsoo Jung, U Kang.

  15. MASCOT: Memory-efficient and Accurate Sampling for Counting Local Triangles in Graph Streams. KDD 2015: 685-694 [paper] [Code]

    Yongsub Lim, U Kang.

  16. Approximately Counting Triangles in Large Graph Streams Including Edge Duplicates with a Fixed Memory Usage. Proc. VLDB Endow. 11(2): 162-175 (2017) [paper]

    Pinghui Wang, Yiyan Qi, Yu Sun, Xiangliang Zhang, Jing Tao, Xiaohong Guan.

  17. TRIÈST: Counting Local and Global Triangles in Fully Dynamic Streams with Fixed Memory Size. ACM Trans. Knowl. Discov. Data 11(4): 43:1-43:50 (2017) [paper] [code]

    Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, Eli Upfal.

  18. TRIÈST: Counting Local and Global Triangles in Fully-Dynamic Streams with Fixed Memory Size. KDD 2016: 825-834 [paper] [code]

    Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, Eli Upfal.

Butterfly Count

  1. Counting Butterflies in Fully Dynamic Bipartite Graph Streams. ICDE 2024: 2917-2930 [paper]

    Serafeim Papadias, Zoi Kaoudi, Varun Pandey, Jorge-Arnulfo Quiané-Ruiz, Volker Markl.

  2. Approximately Counting Butterflies in Large Bipartite Graph Streams. IEEE Trans. Knowl. Data Eng. 34(12): 5621-5635 (2022) [paper]

    Rundong Li, Pinghui Wang, Peng Jia, Xiangliang Zhang, Junzhou Zhao, Jing Tao, Ye Yuan, Xiaohong Guan.

  3. sGrapp: Butterfly Approximation in Streaming Graphs. ACM Trans. Knowl. Discov. Data 16(4): 76:1-76:43 (2022) [paper] [code]

    Aida Sheshbolouki, M. Tamer Özsu.

  4. FLEET: Butterfly Estimation from a Bipartite Graph Stream. CIKM 2019: 1201-1210 [paper] [code]

    Seyed-Vahid Sanei-Mehri, Yu Zhang, Ahmet Erdem Sariyüce, Srikanta Tirthapura.

About

Must-read papers on streaming graph

Topics

paper-list streaming-graph

Resources

Readme
Activity

Stars

0 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published