{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:15:46Z","timestamp":1779174946737,"version":"3.51.4"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:p>We study index-based processing for connectivity queries within sliding windows on streaming graphs. These queries, which determine whether two vertices belong to the same connected component, are fundamental operations in real-time graph data processing and demand high throughput and low latency. While indexing methods that leverage data structures for fully dynamic connectivity can facilitate efficient query processing, they encounter significant challenges with deleting expired edges from the window during window updates. We introduce a novel indexing approach that eliminates the need for physically performing edge deletions. This is achieved through a unique bidirectional incremental computation framework, referred to as the BIC model. The BIC model implements two distinct incremental computations to compute connected components within the window, operating along and against the timeline, respectively. These computations are then merged to efficiently compute queries in the window. We propose techniques for optimized index storage, incremental index updates, and efficient query processing to improve BIC effectiveness. Empirically, BIC achieves a 14\u00d7 increase in throughput and a reduction in P95 latency by up to 3900\u00d7 when compared to state-of-the-art indexes.<\/jats:p>","DOI":"10.14778\/3675034.3675040","type":"journal-article","created":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T22:19:11Z","timestamp":1722982751000},"page":"2473-2486","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Incremental Sliding Window Connectivity over Streaming Graphs"],"prefix":"10.14778","volume":"17","author":[{"given":"Chao","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angela","family":"Bonifati","sequence":"additional","affiliation":[{"name":"Lyon 1 University, CNRS &amp; IUF, Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Tamer","family":"\u00d6zsu","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536229"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/264216.264223"},{"key":"e_1_2_1_3_1","volume-title":"Proc. 18th Int. World Wide Web Conf. 1061--1062","author":"Barbieri Davide Francesco","year":"2009","unstructured":"Davide Francesco Barbieri, Daniele Braga, Stefano Ceri, Emanuele Della Valle, and Michael Grossniklaus. 2009. C-SPARQL: SPARQL for Continuous Querying. In Proc. 18th Int. World Wide Web Conf. 1061--1062. 10.1145\/1526709.1526856"},{"key":"e_1_2_1_4_1","volume-title":"Proc. 9th Int. Semantic Web Conf. 96--111","author":"Calbimonte Jean-Paul","unstructured":"Jean-Paul Calbimonte, Oscar Corcho, and Alasdair J. G. Gray. 2010. Enabling Ontology-Based Access to Streaming Data Sources. In Proc. 9th Int. Semantic Web Conf. 96--111."},{"key":"e_1_2_1_5_1","first-page":"28","article-title":"Apache flink: Stream and batch processing in a single engine","volume":"38","author":"Carbone Paris","year":"2015","unstructured":"Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache flink: Stream and batch processing in a single engine. IEEE Data Eng. Bull. 38, 4 (2015), 28--38.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551868"},{"key":"e_1_2_1_7_1","volume-title":"Proc. 12th Extended Semantic Web Conf. 353--363","author":"Dell'Aglio Daniele","year":"2015","unstructured":"Daniele Dell'Aglio, Jean-Paul Calbimonte, Emanuele Della Valle, and Oscar Corcho. 2015. Towards a Unified Language for RDF Stream Query Processing. In Proc. 12th Extended Semantic Web Conf. 353--363."},{"key":"e_1_2_1_8_1","volume-title":"Proc. 28th Int. Conf. on Data Engineering. 1--5. 10","author":"Ediger David","year":"2012","unstructured":"David Ediger, Rob McColl, Jason Riedy, and David A. Bader. 2012. STINGER: High performance data structure for streaming graphs. In Proc. 28th Int. Conf. on Data Engineering. 1--5. 10.1109\/HPEC.2012.6408680"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/265910.265914"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_2_1_11_1","unstructured":"David Gibb Bruce Kapron Valerie King and Nolan Thorn. 2015. Dynamic graph connectivity with improved worst case update time and sublinear space. arXiv:1509.06464 [cs.DS]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/776985.776986"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/PL00009228","article-title":"Lower bounds for fully dynamic connectivity problems in graphs","volume":"22","author":"Henzinger Monika Rauch","year":"1998","unstructured":"Monika Rauch Henzinger and Michael L Fredman. 1998. Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22, 3 (1998), 351--362.","journal-title":"Algorithmica"},{"key":"e_1_2_1_14_1","volume-title":"Proc. 27th Annual ACM Symp. on Theory of Computing. Association for Computing Machinery","author":"Henzinger Monika Rauch","year":"1995","unstructured":"Monika Rauch Henzinger and Valerie King. 1995. Randomized Dynamic Graph Algorithms with Polylogarithmic Time per Operation. In Proc. 27th Annual ACM Symp. on Theory of Computing. Association for Computing Machinery, New York, NY, USA, 519--527. 10.1145\/225058.225269"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327209"},{"key":"e_1_2_1_17_1","volume-title":"White Paper: Financial Fraud Detection with Graph Data Science.","author":"Hodler Amy","year":"2023","unstructured":"Amy Hodler. 2023. White Paper: Financial Fraud Detection with Graph Data Science."},{"key":"e_1_2_1_18_1","volume-title":"Proc. 30th Annual ACM Symp. on Theory of Computing. 79--89","author":"Holm Jacob","year":"1998","unstructured":"Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. 1998. Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity. In Proc. 30th Annual ACM Symp. on Theory of Computing. 79--89. 10.1145\/276698.276715"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_20_1","volume-title":"Proc. 28th Annual ACM-SIAM Symp. on Discrete Algorithms. 510--520","author":"Huang Shang-En","year":"2017","unstructured":"Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie. 2017. Fully Dynamic Connectivity in O(Log n(Log Log n)2) Amortized Expected Time. In Proc. 28th Annual ACM-SIAM Symp. on Discrete Algorithms. 510--520."},{"key":"e_1_2_1_21_1","volume-title":"Proc. 4th Int. Workshop on Graph Data Management Experiences & Systems. Article 5, 6 pages. 10","author":"Iyer Anand Padmanabha","year":"2016","unstructured":"Anand Padmanabha Iyer, Li Erran Li, Tathagata Das, and Ion Stoica. 2016. Time-Evolving Graph Processing at Scale. In Proc. 4th Int. Workshop on Graph Data Management Experiences & Systems. Article 5, 6 pages. 10.1145\/2960414.2960419"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945398"},{"key":"e_1_2_1_23_1","volume-title":"Proc. 24th Annual ACM-SIAM Symp. on Discrete Algorithms. 1131--1142","author":"Kapron Bruce M.","year":"2013","unstructured":"Bruce M. Kapron, Valerie King, and Ben Mountjoy. 2013. Dynamic Graph Connectivity in Polylogarithmic Worst Case Time. In Proc. 24th Annual ACM-SIAM Symp. on Discrete Algorithms. 1131--1142."},{"key":"e_1_2_1_24_1","volume-title":"Faster Worst Case Deterministic Dynamic Connectivity. In 24th Annual European Symposium on Algorithms (ESA 2016","volume":"57","author":"Kejlberg-Rasmussen Casper","year":"2016","unstructured":"Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. 2016. Faster Worst Case Deterministic Dynamic Connectivity. In 24th Annual European Symposium on Algorithms (ESA 2016), Vol. 57. 53:1--53:15. 10.4230\/LIPIcs.ESA.2016.53"},{"key":"e_1_2_1_25_1","volume-title":"Proc. ACM SIGMOD Int. Conf. on Management of Data. 239--250","author":"Kulkarni Sanjeev","year":"2015","unstructured":"Sanjeev Kulkarni, Nikunj Bhagat, Maosong Fu, Vikas Kedigehalli, Christopher Kellogg, Sailesh Mittal, Jignesh M. Patel, Karthik Ramasamy, and Siddarth Taneja. 2015. Twitter Heron: Stream Processing at Scale. In Proc. ACM SIGMOD Int. Conf. on Management of Data. 239--250. 10.1145\/2723372.2742788"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3364180"},{"key":"e_1_2_1_27_1","volume-title":"Proc. 10th Int. Semantic Web Conf. 370--388","author":"Le-Phuoc Danh","year":"2011","unstructured":"Danh Le-Phuoc, Minh Dao-Tran, Josiane Xavier Parreira, and Manfred Hauswirth. 2011. A Native and Adaptive Approach for Unified Processing of Linked Streams and Linked Data. In Proc. 10th Int. Semantic Web Conf. 370--388."},{"key":"e_1_2_1_28_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_29_1","first-page":"10","volume-title":"Proc. 14th ACM SIGOPS\/EuroSys European Conf. on Comp. Syst. Article 25","author":"Mariappan Mugilan","year":"2019","unstructured":"Mugilan Mariappan and Keval Vora. 2019. GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs. In Proc. 14th ACM SIGOPS\/EuroSys European Conf. on Comp. Syst. Article 25, 16 pages. 10.1145\/3302424.3303974"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0304-3975(94)90159-7","article-title":"Complexity models for incremental computation","volume":"130","author":"Miltersen Peter Bro","year":"1994","unstructured":"Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, and Roberto Tamassia. 1994. Complexity models for incremental computation. Theor. Comput. Sci. 130, 1 (1994), 203--236.","journal-title":"Theor. Comput. Sci."},{"key":"e_1_2_1_32_1","first-page":"45","article-title":"Introducing the graph 500","volume":"19","author":"Murphy Richard C","year":"2010","unstructured":"Richard C Murphy, Kyle B Wheeler, Brian W Barrett, and James A Ang. 2010. Introducing the graph 500. Cray Users Group (CUG) 19 (2010), 45--74.","journal-title":"Cray Users Group (CUG)"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1177\/016555150202800601"},{"key":"e_1_2_1_35_1","volume-title":"Proc. ACM SIGMOD Int. Conf. on Management of Data. 1415--1430","author":"Pacaci Anil","year":"2020","unstructured":"Anil Pacaci, Angela Bonifati, and M. Tamer \u00d6zsu. 2020. Regular Path Query Evaluation on Streaming Graphs. In Proc. ACM SIGMOD Int. Conf. on Management of Data. 1415--1430. 10.1145\/3318464.3389733"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00667-4"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00548-x"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434642"},{"key":"e_1_2_1_41_1","volume-title":"Algorithms","author":"Sedgewick Robert","unstructured":"Robert Sedgewick and Kevin Wayne. 2011. Algorithms, 4th Edition. Addison-Wesley. I--XII, 1--955 pages.","edition":"4"},{"key":"e_1_2_1_42_1","volume-title":"Proc. 22nd Int. Euro-Par Conf. 319--333","author":"Sengupta Dipanjan","year":"2016","unstructured":"Dipanjan Sengupta, Narayanan Sundaram, Xia Zhu, Theodore L. Willke, Jeffrey Young, Matthew Wolf, and Karsten Schwan. 2016. GraphIn: An Online High Performance Incremental Graph Processing Framework. In Proc. 22nd Int. Euro-Par Conf. 319--333."},{"key":"e_1_2_1_43_1","volume-title":"Proc. 9th ACM Symp. on Cloud Computing. 301--312","author":"Sheng Feng","year":"2018","unstructured":"Feng Sheng, Qiang Cao, Haoran Cai, Jie Yao, and Changsheng Xie. 2018. GraPU: Accelerate Streaming Graph Analysis through Preprocessing Buffered Updates. In Proc. 9th ACM Symp. on Cloud Computing. 301--312. 10.1145\/3267809.3267811"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","first-page":"877","DOI":"10.14778\/3574245.3574270","article-title":"The LDBC Social Network Benchmark","volume":"16","author":"Sz\u00e1rnyas G\u00e1bor","year":"2022","unstructured":"G\u00e1bor Sz\u00e1rnyas, Jack Waudby, Benjamin A. Steer, D\u00e1vid Szak\u00e1llas, Altan Birler, Mingxi Wu, Yuchen Zhang, and Peter Boncz. 2022. The LDBC Social Network Benchmark: Business Intelligence Workload. Proc. VLDB Endowment 16, 4 (2022), 877--890.","journal-title":"Business Intelligence Workload. Proc. VLDB Endowment"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90042-4"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","article-title":"An Efficient Parallel Biconnectivity Algorithm","volume":"14","author":"Tarjan Robert E.","year":"1985","unstructured":"Robert E. Tarjan and Uzi Vishkin. 1985. An Efficient Parallel Biconnectivity Algorithm. SIAM J. on Comput. 14, 4 (1985), 862--874.","journal-title":"SIAM J. on Comput."},{"key":"e_1_2_1_48_1","volume-title":"Proc. 32nd Annual ACM Symp. on Theory of Computing. 343--350","author":"Thorup Mikkel","year":"2000","unstructured":"Mikkel Thorup. 2000. Near-Optimal Fully-Dynamic Graph Connectivity. In Proc. 32nd Annual ACM Symp. on Theory of Computing. 343--350. 10.1145\/335305.335345"},{"key":"e_1_2_1_49_1","volume-title":"Proc. ACM SIGMOD Int. Conf. on Management of Data. 147--156","author":"Toshniwal Ankit","year":"2014","unstructured":"Ankit Toshniwal, Siddarth Taneja, Amit Shukla, Karthik Ramasamy, Jignesh M. Patel, Sanjeev Kulkarni, Jason Jackson, Krishna Gade, Maosong Fu, Jake Donham, Nikunj Bhagat, Sailesh Mittal, and Dmitriy Ryaboy. 2014. Storm@twitter. In Proc. ACM SIGMOD Int. Conf. on Management of Data. 147--156. 10.1145\/2588555.2595641"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1140\/epjb\/e2009-00090-x","article-title":"Public transport networks: empirical analysis and modeling","volume":"68","author":"Ferber Christian Von","year":"2009","unstructured":"Christian Von Ferber, Taras Holovatch, Yu Holovatch, and V Palchykov. 2009. Public transport networks: empirical analysis and modeling. Eur. Phys. J. B 68 (2009), 261--275.","journal-title":"Eur. Phys. J. B"},{"key":"e_1_2_1_51_1","unstructured":"Zhengyu Wang. 2015. An Improved Randomized Data Structure for Dynamic Graph Connectivity. arXiv:1510.04590 [cs.DS]"},{"key":"e_1_2_1_52_1","volume-title":"The Free Encyclopedia","unstructured":"Wikipedia. 2023. Interval tree --- Wikipedia, The Free Encyclopedia. http:\/\/en.wikipedia.org\/w\/index.php?title=Interval%20tree&oldid=1178718117. [Online; accessed 23-October-2023]."},{"key":"e_1_2_1_53_1","volume-title":"Proc. 24th Annual ACM-SIAM Symp. on Discrete Algorithms. 1757--1769","author":"Wulff-Nilsen Christian","year":"2013","unstructured":"Christian Wulff-Nilsen. 2013. Faster Deterministic Fully-Dynamic Graph Connectivity. In Proc. 24th Annual ACM-SIAM Symp. on Discrete Algorithms. 1757--1769. 10.1137\/1.9781611973105.126"},{"key":"e_1_2_1_54_1","volume-title":"Proc. 49th Annual ACM Symp. on Theory of Computing. 1130--1143","author":"Wulff-Nilsen Christian","year":"2017","unstructured":"Christian Wulff-Nilsen. 2017. Fully-Dynamic Minimum Spanning Forest with Improved Worst-Case Update Time. In Proc. 49th Annual ACM Symp. on Theory of Computing. 1130--1143. 10.1145\/3055399.3055415"},{"key":"e_1_2_1_55_1","volume-title":"Proc. 24th ACM Symp. on Operating System Principles. 423--438","author":"Zaharia Matei","year":"2013","unstructured":"Matei Zaharia, Tathagata Das, Haoyuan Li, Timothy Hunter, Scott Shenker, and Ion Stoica. 2013. Discretized Streams: Fault-Tolerant Streaming Computation at Scale. In Proc. 24th ACM Symp. on Operating System Principles. 423--438. 10.1145\/2517349.2522737"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Chao Zhang Angela Bonifati and M. Tamer \u00d6zsu. 2024. Incremental Sliding Window Connectivity over Streaming Graphs. arXiv:2406.06754 [cs.DB]","DOI":"10.14778\/3675034.3675040"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3675034.3675040","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T07:40:56Z","timestamp":1732606856000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3675034.3675040"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6]]},"references-count":56,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["10.14778\/3675034.3675040"],"URL":"https:\/\/doi.org\/10.14778\/3675034.3675040","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,6]]},"assertion":[{"value":"2024-08-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}