{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:08:18Z","timestamp":1775912898496,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"5-6","license":[{"start":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T00:00:00Z","timestamp":1726617600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T00:00:00Z","timestamp":1726617600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"National Super Computing Mission, India","award":["DST\/NSM\/R&D Exascale\/2021\/18"],"award-info":[{"award-number":["DST\/NSM\/R&D Exascale\/2021\/18"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s10766-024-00774-z","type":"journal-article","created":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T22:25:59Z","timestamp":1726784759000},"page":"400-453","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Meerkat: A Framework for Dynamic Graph Algorithms on GPUs"],"prefix":"10.1007","volume":"52","author":[{"given":"Kevin Jude","family":"Concessao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Unnikrishnan","family":"Cheramangalath","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ricky","family":"Dev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rupesh","family":"Nasre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,18]]},"reference":[{"key":"774_CR1","doi-asserted-by":"publisher","unstructured":"Malhotra, G., Chappidi, H., Nasre, R. Rauchwerger, L.: (ed.) Fast Dynamic Graph Algorithms. Languages and Compilers for Parallel Computing - 30th International Workshop, LCPC 2017, College Station, TX, USA, October 11-13, 2017, Revised Selected Papers, Vol. 11403 of Lecture Notes in Computer Science, 262\u2013277 (Springer), (2017). https:\/\/doi.org\/10.1007\/978-3-030-35225-7_17","DOI":"10.1007\/978-3-030-35225-7_17"},{"key":"774_CR2","doi-asserted-by":"publisher","unstructured":"Awad, M.A., Ashkiani, S., Porumbescu, S.D., Owens, J.D.: Dynamic graphs on the GPU (2020). https:\/\/doi.org\/10.1109\/IPDPS47924.2020.00081","DOI":"10.1109\/IPDPS47924.2020.00081"},{"key":"774_CR3","doi-asserted-by":"crossref","unstructured":"Winter, M., Mlakar, D., Zayer, R., Seidel, H.-P., Steinberger, M.: Faimgraph: high performance management of fully-dynamic graphs under tight memory constraints on the gpu. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis, SC \u201918 (IEEE Press), (2018)","DOI":"10.1109\/SC.2018.00063"},{"key":"774_CR4","doi-asserted-by":"publisher","unstructured":"Busato, F., Green, O., Bombieri, N., Bader, D.\u00a0A.: Hornet: an efficient data structure for dynamic sparse graphs and matrices on gpus. In: 2018 IEEE High Performance extreme Computing Conference (HPEC), 1\u20137 (IEEE), (2018). https:\/\/doi.org\/10.1109\/HPEC.2018.8547541","DOI":"10.1109\/HPEC.2018.8547541"},{"key":"774_CR5","doi-asserted-by":"publisher","unstructured":"Green, O., Bader, D.\u00a0A.: cuSTINGER: supporting dynamic graph algorithms for gpus. In: 2016 IEEE High Performance Extreme Computing Conference (HPEC), 1\u20136 (2016). https:\/\/doi.org\/10.1109\/HPEC.2016.7761622","DOI":"10.1109\/HPEC.2016.7761622"},{"key":"774_CR6","doi-asserted-by":"publisher","unstructured":"Ashkiani, S., Farach-Colton, M., Owens, J.\u00a0D.: A dynamic hash table for the GPU. In: 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 419\u2013429 (2018). https:\/\/doi.org\/10.1109\/IPDPS.2018.00052","DOI":"10.1109\/IPDPS.2018.00052"},{"key":"774_CR7","doi-asserted-by":"publisher","unstructured":"Ediger, D., McColl, R., Riedy, J., Bader, D.\u00a0A.: Stinger: high performance data structure for streaming graphs. In: 2012 IEEE Conference on High Performance Extreme Computing, 1\u20135 (2012). https:\/\/doi.org\/10.1109\/HPEC.2012.6408680","DOI":"10.1109\/HPEC.2012.6408680"},{"key":"774_CR8","doi-asserted-by":"publisher","first-page":"107","DOI":"10.14778\/3151113.3151122","volume":"11","author":"M Sha","year":"2017","unstructured":"Sha, M., Li, Y., He, B., Tan, K.-L.: Accelerating dynamic graph analytics on GPUs. Proc. VLDB Endow. 11, 107\u2013120 (2017). https:\/\/doi.org\/10.14778\/3151113.3151122","journal-title":"Proc. VLDB Endow."},{"key":"774_CR9","unstructured":"Nvidia. Nvidia warp primitives. https:\/\/developer.nvidia.com\/blog\/using-cuda-warp-level-primitives\/"},{"key":"774_CR10","unstructured":"CUDA C++ Programming Guide - Cooperative Groups (2023). https:\/\/docs.nvidia.com\/cuda\/cuda-c-programming-guide\/index.html#cooperative-groups. [Accessed 08-11-2023]"},{"key":"774_CR11","doi-asserted-by":"publisher","unstructured":"Vora, K., Gupta, R., Xu, G.: Kickstarter: fast and accurate computations on streaming graphs via trimmed approximations. In: Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS \u201917, 237\u2013251 (Association for Computing Machinery, New York, NY, USA), (2017). https:\/\/doi.org\/10.1145\/3037697.3037748","DOI":"10.1145\/3037697.3037748"},{"key":"774_CR12","unstructured":"Arasu, A., Novak, J., Tomkins, A., Tomlin, J.\u00a0A.: Pagerank computation and the structure of the web: experiments and algorithms (2002)"},{"key":"774_CR13","doi-asserted-by":"publisher","unstructured":"Makkar, D., Bader, D.\u00a0A., Green, O.: Exact and parallel triangle counting in dynamic graphs. In: 2017 IEEE 24th International Conference on High Performance Computing (HiPC), 2\u201312 (2017). https:\/\/doi.org\/10.1109\/HiPC.2017.00011","DOI":"10.1109\/HiPC.2017.00011"},{"issue":"1","key":"774_CR14","doi-asserted-by":"publisher","first-page":"2980","DOI":"10.1038\/srep02980","volume":"3","author":"M De Domenico","year":"2013","unstructured":"De Domenico, M., Lima, A., Mougel, P., Musolesi, M.: The anatomy of a scientific rumor. Scientific reports 3(1), 2980 (2013). https:\/\/doi.org\/10.1038\/srep02980","journal-title":"Scientific reports"},{"key":"774_CR15","doi-asserted-by":"publisher","unstructured":"Backstrom, L., Huttenlocher, D., Kleinberg, J., Lan, X.: Group formation in large social networks: membership, growth, and evolution. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD \u201906, 44\u201354 (Association for Computing Machinery, New York, NY, USA), (2006). https:\/\/doi.org\/10.1145\/1150402.1150412","DOI":"10.1145\/1150402.1150412"},{"key":"774_CR16","unstructured":"Takac, L., Z\u00e1bovsk\u00fd, M.: Data analysis in public social networks. In: International Scientific Conference and International Workshop Present Day Trends of Innovations 1\u20136 (2012)"},{"key":"774_CR17","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Lang, K.\u00a0J., Dasgupta, A., Mahoney, M.\u00a0W.: Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters (2008). arXiv:0810.1355","DOI":"10.1080\/15427951.2009.10129177"},{"key":"774_CR18","doi-asserted-by":"publisher","unstructured":"Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media. CHI \u201910, 1361\u20131370 (Association for Computing Machinery, New York, NY, USA, 2010). https:\/\/doi.org\/10.1145\/1753326.1753532","DOI":"10.1145\/1753326.1753532"},{"key":"774_CR19","doi-asserted-by":"publisher","unstructured":"Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. In: Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, MDS \u201912 (Association for Computing Machinery, New York, NY, USA), (2012). https:\/\/doi.org\/10.1145\/2350190.2350193","DOI":"10.1145\/2350190.2350193"},{"key":"774_CR20","unstructured":"DIMACS Implementation Challege. http:\/\/www.diag.uniroma1.it\/\/challenge9\/download.shtml"},{"key":"774_CR21","doi-asserted-by":"publisher","unstructured":"Hong, C., Dhulipala, L., Shun, J.: Exploring the design space of static and incremental graph connectivity algorithms on gpus. Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques, PACT \u201920, 55\u201369 (Association for Computing Machinery, New York, NY, USA), (2020). https:\/\/doi.org\/10.1145\/3410463.3414657","DOI":"10.1145\/3410463.3414657"},{"key":"774_CR22","doi-asserted-by":"publisher","first-page":"1020","DOI":"10.14778\/3384345.3384351","volume":"13","author":"X Zhu","year":"2020","unstructured":"Zhu, X.: Livegraph: a transactional graph storage system with purely sequential adjacency list scans. Proc. VLDB Endow 13, 1020\u20131034 (2020). https:\/\/doi.org\/10.14778\/3384345.3384351","journal-title":"Proc. VLDB Endow"},{"key":"774_CR23","doi-asserted-by":"publisher","unstructured":"Jaiyeoba, W., Skadron, K.: Graphtinker: a high performance data structure for dynamic graph processing. In: 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 1030\u20131041 (2019). https:\/\/doi.org\/10.1109\/IPDPS.2019.00110","DOI":"10.1109\/IPDPS.2019.00110"},{"issue":"4","key":"774_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3364180","volume":"15","author":"P Kumar","year":"2020","unstructured":"Kumar, P., Huang, H.H.: Graphone: a data store for real-time analytics on evolving graphs. ACM Trans. Storage 15(4), 1\u201340 (2020). https:\/\/doi.org\/10.1145\/3364180","journal-title":"ACM Trans. Storage"},{"key":"774_CR25","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.14778\/3447689.3447708","volume":"14","author":"D De Leo","year":"2021","unstructured":"De Leo, D., Boncz, P.: Teseo and the analysis of structural dynamic graphs. Proc. VLDB Endow. 14, 1053\u20131066 (2021). https:\/\/doi.org\/10.14778\/3447689.3447708","journal-title":"Proc. VLDB Endow."},{"key":"774_CR26","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.14778\/3514061.3514065","volume":"15","author":"P Fuchs","year":"2022","unstructured":"Fuchs, P., Margan, D., Giceva, J.: Sortledton: a universal, transactional graph data structure. Proc. VLDB Endow. 15, 1173\u20131186 (2022). https:\/\/doi.org\/10.14778\/3514061.3514065","journal-title":"Proc. VLDB Endow."},{"key":"774_CR27","doi-asserted-by":"crossref","unstructured":"Chen, D., et\u00a0al.: Graphfly: efficient asynchronous streaming graphs processing via dependency-flow. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC \u201922 (IEEE Press, 2022)","DOI":"10.1109\/SC41404.2022.00050"},{"key":"774_CR28","doi-asserted-by":"publisher","unstructured":"Pandey, P., Wheatman, B., Xu, H., Buluc, A.: Terrace: a hierarchical graph container for skewed dynamic graphs. In: Proceedings of the 2021 International Conference on Management of Data, SIGMOD \u201921, 1372\u20131385 (Association for Computing Machinery, New York, NY, USA), (2021). https:\/\/doi.org\/10.1145\/3448016.3457313","DOI":"10.1145\/3448016.3457313"},{"key":"774_CR29","doi-asserted-by":"publisher","unstructured":"Dhulipala, L., Blelloch, G.\u00a0E., Shun, J.: Low-latency graph streaming using compressed purely-functional trees. In: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019, 918\u2013934 (Association for Computing Machinery, New York, NY, USA), (2019). https:\/\/doi.org\/10.1145\/3314221.3314598","DOI":"10.1145\/3314221.3314598"},{"key":"774_CR30","doi-asserted-by":"publisher","unstructured":"Afarin, M., Gao, C., Rahman, S., Abu-Ghazaleh, N., Gupta, R.: Commongraph: graph analytics on evolving data. In: Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, ASPLOS 2023, 133\u2013145 (Association for Computing Machinery, New York, NY, USA), (2023). https:\/\/doi.org\/10.1145\/3575693.3575713","DOI":"10.1145\/3575693.3575713"},{"key":"774_CR31","doi-asserted-by":"crossref","unstructured":"Zhang, F., Zou, L., Yu, Y. Zhang, W., Zou, L., Maamar, Z., Chen, L.: (eds) Lpma - an efficient data structure for dynamic graph on gpus. Web Information Systems Engineering \u2013 WISE 2021, 469\u2013484 (Springer International Publishing, Cham), (2021)","DOI":"10.1007\/978-3-030-90888-1_36"},{"key":"774_CR32","doi-asserted-by":"publisher","unstructured":"Winter, M., Zayer, R., Steinberger, M.: Autonomous, independent management of dynamic graphs on gpus. In: 2017 IEEE High Performance Extreme Computing Conference (HPEC), 1\u20137 (2017). https:\/\/doi.org\/10.1109\/HPEC.2017.8091058","DOI":"10.1109\/HPEC.2017.8091058"},{"key":"774_CR33","doi-asserted-by":"publisher","first-page":"5823","DOI":"10.1109\/TKDE.2022.3171588","volume":"35","author":"Y Zhang","year":"2023","unstructured":"Zhang, Y., et al.: Egraph: efficient concurrent GPU-based dynamic graph processing. IEEE Transactions on Knowledge and Data Engineering 35, 5823\u20135836 (2023). https:\/\/doi.org\/10.1109\/TKDE.2022.3171588","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"774_CR34","doi-asserted-by":"publisher","unstructured":"Vora, K., Koduru, S.\u00a0C., Gupta, R.: Aspire: exploiting asynchronous parallelism in iterative algorithms using a relaxed consistency based DSM. In: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA \u201914, 861\u2013878 (Association for Computing Machinery, New York, NY, USA), (2014). https:\/\/doi.org\/10.1145\/2660193.2660227","DOI":"10.1145\/2660193.2660227"},{"key":"774_CR35","doi-asserted-by":"publisher","unstructured":"Bender, M.\u00a0A., Hu, H.: An adaptive packed-memory array. In: Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS \u201906, 20\u201329 (Association for Computing Machinery, New York, NY, USA), (2006). https:\/\/doi.org\/10.1145\/1142351.1142355","DOI":"10.1145\/1142351.1142355"},{"key":"774_CR36","doi-asserted-by":"publisher","unstructured":"Fagerberg, R.: Cache-Oblivious B-Tree, 121\u2013123 (Springer US, Boston, MA), (2008). https:\/\/doi.org\/10.1007\/978-0-387-30162-4_61","DOI":"10.1007\/978-0-387-30162-4_61"},{"key":"774_CR37","doi-asserted-by":"publisher","unstructured":"Shun, J., Blelloch, G.\u00a0E.: Ligra: a lightweight graph processing framework for shared memory. In: Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP \u201913, 135\u2013146 (Association for Computing Machinery, New York, NY, USA), (2013)https:\/\/doi.org\/10.1145\/2442516.2442530","DOI":"10.1145\/2442516.2442530"},{"key":"774_CR38","doi-asserted-by":"publisher","first-page":"653","DOI":"10.14778\/3436905.3436923","volume":"14","author":"L Dhulipala","year":"2020","unstructured":"Dhulipala, L., Hong, C., Shun, J.: Connectit: a framework for static and incremental parallel graph connectivity algorithms. Proc. VLDB Endow. 14, 653\u2013667 (2020). https:\/\/doi.org\/10.14778\/3436905.3436923","journal-title":"Proc. VLDB Endow."},{"key":"774_CR39","doi-asserted-by":"publisher","unstructured":"Soman, J., Kishore, K., Narayanan, P.\u00a0J.: A fast gpu algorithm for graph connectivity. In: 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), 1\u20138 (2010). https:\/\/doi.org\/10.1109\/IPDPSW.2010.5470817","DOI":"10.1109\/IPDPSW.2010.5470817"},{"key":"774_CR40","doi-asserted-by":"publisher","unstructured":"Jaiganesh, J., Burtscher, M.: A high-performance connected components implementation for gpus. In: Proceedings of the 27th International Symposium on High-Performance Parallel and Distributed Computing, HPDC \u201918, 92\u2013104 (Association for Computing Machinery, New York, NY, USA), (2018). https:\/\/doi.org\/10.1145\/3208040.3208041","DOI":"10.1145\/3208040.3208041"},{"key":"774_CR41","doi-asserted-by":"publisher","unstructured":"Sutton, M., Ben-Nun, T., Barak, A.: Optimizing parallel graph connectivity computation via subgraph sampling. In: 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 12\u201321 (2018). https:\/\/doi.org\/10.1109\/IPDPS.2018.00012","DOI":"10.1109\/IPDPS.2018.00012"},{"key":"774_CR42","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/978-3-030-41886-1_6","volume-title":"Dynamic Graph Algorithms","author":"U Cheramangalath","year":"2020","unstructured":"Cheramangalath, U., Nasre, R., Srikant, Y.N.: Dynamic Graph Algorithms, pp. 137\u2013151. Springer International Publishing, Berlin (2020). https:\/\/doi.org\/10.1007\/978-3-030-41886-1_6"},{"key":"774_CR43","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0304-3975(95)00079-8","volume":"158","author":"G Ramalingam","year":"1996","unstructured":"Ramalingam, G., Reps, T.: On the computational complexity of dynamic graph problems. Theor. Comput. Sci. 158, 233\u2013277 (1996). https:\/\/doi.org\/10.1016\/0304-3975(95)00079-8","journal-title":"Theor. Comput. Sci."},{"key":"774_CR44","unstructured":"CUDA Pro Tip: Write Flexible Kernels with Grid-Stride Loops | NVIDIA Technical Blog \u2014 developer.nvidia.com. https:\/\/developer.nvidia.com\/blog\/cuda-pro-tip-write-flexible-kernels-grid-stride-loops\/. [Accessed 08-11-2023]"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-024-00774-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-024-00774-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-024-00774-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T19:07:18Z","timestamp":1727377638000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-024-00774-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,18]]},"references-count":44,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["774"],"URL":"https:\/\/doi.org\/10.1007\/s10766-024-00774-z","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,18]]},"assertion":[{"value":"16 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}},{"value":"All authors have consented to the publication of this manuscript.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}}]}}