{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T14:41:41Z","timestamp":1773412901342,"version":"3.50.1"},"reference-count":40,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2109988"],"award-info":[{"award-number":["CCF-2109988"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Data from emerging applications, such as cybersecurity and social networking, can be abstracted as graphs whose edges are updated sequentially in the form of a stream. The challenging problem of interactive graph stream analytics is the quick response of the queries on terabyte and beyond graph stream data from end users. In this paper, a succinct and efficient double index data structure is designed to build the sketch of a graph stream to meet general queries. A single pass stream model, which includes general sketch building, distributed sketch based analysis algorithms and regression based approximation solution generation, is developed, and a typical graph algorithm\u2014triangle counting\u2014is implemented to evaluate the proposed method. Experimental results on power law and normal distribution graph streams show that our method can generate accurate results (mean relative error less than 4%) with a high performance. All our methods and code have been implemented in an open source framework, Arkouda, and are available from our GitHub repository, Bader-Research. This work provides the large and rapidly growing Python community with a powerful way to handle terabyte and beyond graph stream data using their laptops.<\/jats:p>","DOI":"10.3390\/a14080221","type":"journal-article","created":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T11:53:23Z","timestamp":1626868403000},"page":"221","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Interactive Graph Stream Analytics in Arkouda"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8435-1611","authenticated-orcid":false,"given":"Zhihui","family":"Du","sequence":"first","affiliation":[{"name":"Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver Alvarado","family":"Rodriguez","sequence":"additional","affiliation":[{"name":"Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph","family":"Patchett","sequence":"additional","affiliation":[{"name":"Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7380-5876","authenticated-orcid":false,"given":"David A.","family":"Bader","sequence":"additional","affiliation":[{"name":"Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,7,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/2627692.2627694","article-title":"Graph stream algorithms: A survey","volume":"43","author":"McGregor","year":"2014","journal-title":"ACM Sigmod Rec."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jcss.1997.1545","article-title":"The space complexity of approximating the frequency moments","volume":"58","author":"Alon","year":"1999","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Manku, G.S., and Motwani, R. (2002). Approximate frequency counts over data streams. VLDB\u201902: Proceedings of the 28th International Conference on Very Large Databases, Elsevier.","DOI":"10.1016\/B978-155860869-6\/50038-X"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","article-title":"An improved data stream summary: The count-min sketch and its applications","volume":"55","author":"Cormode","year":"2005","journal-title":"J. Algorithms"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"213","DOI":"10.14778\/1453856.1453884","article-title":"Tighter estimation using bottom k sketches","volume":"1","author":"Cohen","year":"2008","journal-title":"Proc. VLDB Endow."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Zhao, P., Aggarwal, C.C., and Wang, M. (2011). gSketch: On query estimation in graph streams. arXiv.","DOI":"10.14778\/2078331.2078335"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Tang, N., Chen, Q., and Mitra, P. (July, January 26). Graph stream summarization: From big bang to big crunch. Proceedings of the 2016 International Conference on Management of Data (SIGMOD), San Francisco, CA, USA.","DOI":"10.1145\/2882903.2915223"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1037\/1082-989X.2.2.131","article-title":"Principles and procedures of exploratory data analysis","volume":"2","author":"Behrens","year":"1997","journal-title":"Psychol. Methods"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1086\/289110","article-title":"The philosophy of exploratory data analysis","volume":"50","author":"Good","year":"1983","journal-title":"Philos. Sci."},{"key":"ref_10","first-page":"265","article-title":"Exploratory data analysis as a foundation of inductive research","volume":"27","author":"Jebb","year":"2017","journal-title":"Hum. Resour. Manag. Rev."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Merrill, M., Reus, W., and Neumann, T. (2019, January 22). Arkouda: Interactive data exploration backed by Chapel. Proceedings of the ACM SIGPLAN 6th on Chapel Implementers and Users Workshop (CHIUW), Phoenix, AZ, USA.","DOI":"10.1145\/3329722.3330148"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Reus, W. (2020, January 22). CHIUW 2020 Keynote: Arkouda: Chapel-Powered, Interactive Supercomputing for Data Science. Proceedings of the Chapel Implementers and Users Workshop (CHIUW), 2020 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Online.","DOI":"10.1109\/IPDPSW50202.2020.00109"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"e1226","DOI":"10.1002\/widm.1226","article-title":"Triangle counting in large networks: A review","volume":"8","author":"Dave","year":"2018","journal-title":"Wiley Interdiscip. Rev. Data Min. Knowl. Discov."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Dhulipala, L., Blelloch, G.E., and Shun, J. (2019, January 22\u201326). Low-latency graph streaming using compressed purely-functional trees. Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Phoenix, AZ, USA.","DOI":"10.1145\/3314221.3314598"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Macko, P., Marathe, V.J., Margo, D.W., and Seltzer, M.I. (2015, January 13\u201317). Llama: Efficient graph analytics using large multiversioned arrays. Proceedings of the 2015 IEEE 31st International Conference on Data Engineering (ICDE), Seoul, South Korea.","DOI":"10.1109\/ICDE.2015.7113298"},{"key":"ref_16","unstructured":"Kumar, P., and Huang, H.H. (2019, January 25\u201328). Graphone: A data store for real-time analytics on evolving graphs. Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST19), Boston, MA, USA."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Vora, K., Gupta, R., and Xu, G. (2017, January 8\u201312). Kickstarter: Fast and accurate computations on streaming graphs via trimmed approximations. Proceedings of the 22nd International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Xi\u2019an, China.","DOI":"10.1145\/3037697.3037748"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Mariappan, M., and Vora, K. (2019, January 25\u201328). GraphBolt: Dependency-driven synchronous processing of streaming graphs. Proceedings of the Fourteenth European Conference on Computer Systems (EuroSys), Dresden, Germany.","DOI":"10.1145\/3302424.3303974"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Mariappan, M., Che, J., and Vora, K. (2021, January 26\u201328). DZiG: Sparsity-aware incremental processing of streaming graphs. Proceedings of the Sixteenth European Conference on Computer Systems (EuroSys), Online.","DOI":"10.1145\/3447786.3456230"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Wolf, M.M., Deveci, M., Berry, J.W., Hammond, S.D., and Rajamanickam, S. (2017, January 12\u201314). Fast linear algebra-based triangle counting with KokkosKernels. Proceedings of the 2017 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2017.8091043"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Ya\u015far, A., Rajamanickam, S., Wolf, M., Berry, J., and \u00c7ataly\u00fcrek, \u00dc.V. (2018, January 25\u201327). Fast triangle counting using Cilk. Proceedings of the 2018 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2018.8547563"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Bisson, M., and Fatica, M. (2017, January 12\u201314). Static graph challenge on GPU. Proceedings of the 2017 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2017.8091034"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Pandey, S., Li, X.S., Buluc, A., Xu, J., and Liu, H. (2019, January 24\u201326). H-index: Hash-indexing for parallel triangle counting on GPUs. Proceedings of the 2019 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2019.8916492"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Blanco, M., Low, T.M., and Kim, K. (2019, January 24\u201326). Exploration of fine-grained parallelism for load balancing eager k-truss on GPU and CPU. Proceedings of the 2019 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2019.8916473"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Pearce, R. (2017, January 12\u201314). Triangle counting for scale-free graphs at scale in distributed memory. Proceedings of the 2017 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2017.8091051"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Pearce, R., Steil, T., Priest, B.W., and Sanders, G. (2019, January 24\u201326). One quadrillion triangles queried on one million processors. Proceedings of the 2019 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.","DOI":"10.1109\/HPEC.2019.8916243"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Ghosh, S., and Halappanavar, M. (2020, January 21\u201325). TriC: Distributed-memory Triangle Counting by Exploiting the Graph Structure. Proceedings of the 2020 IEEE High Performance Extreme Computing Conference (HPEC), Online.","DOI":"10.1109\/HPEC43674.2020.9286167"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/j.ipl.2011.12.007","article-title":"Colorful triangle counting and a MapReduce implementation","volume":"112","author":"Pagh","year":"2012","journal-title":"Inf. Process. Lett."},{"key":"ref_29","first-page":"623","article-title":"Reductions in streaming algorithms, with an application to counting triangles in graphs","volume":"2","author":"Kumar","year":"2002","journal-title":"SODA"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1870","DOI":"10.14778\/2556549.2556569","article-title":"Counting and Sampling Triangles from a Graph Stream","volume":"6","author":"Pavan","year":"2013","journal-title":"Proc. VLDB Endow."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Braverman, V., Ostrovsky, R., and Vilenchik, D. (2013, January 8\u201312). How hard is counting triangles in the streaming model?. Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), Riga, Latvia.","DOI":"10.1007\/978-3-642-39206-1_21"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Buriol, L.S., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., and Sohler, C. (2006, January 26\u201328). Counting triangles in data streams. Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), Chicago, IL, USA.","DOI":"10.1145\/1142351.1142388"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Jha, M., Seshadhri, C., and Pinar, A. (2013, January 11\u201314). A space efficient streaming algorithm for triangle counting using the birthday paradox. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Chicago, IL, USA.","DOI":"10.1145\/2487575.2487678"},{"key":"ref_34","unstructured":"Rossum, G. (1995). Python Reference Manual, Centre for Mathematics and Computer Science (CWI)."},{"key":"ref_35","unstructured":"Chamberlain, B.L., Ronaghan, E., Albrecht, B., Duncan, L., Ferguson, M., Harshbarger, B., Iten, D., Keaton, D., Litvinov, V., and Sahabu, P. (2018, January 22\u201324). Chapel comes of age: Making scalable programming productive. Proceedings of the Cray User Group (CUG), Stockholm, Sweden."},{"key":"ref_36","unstructured":"Hintjens, P. (2013). ZeroMQ: Messaging for Many Applications, O\u2019Reilly Media, Inc."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/j.socnet.2009.07.002","article-title":"Explaining the power-law degree distribution in a social commerce network","volume":"31","author":"Stephen","year":"2009","journal-title":"Soc. Netw."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"2115","DOI":"10.1126\/science.287.5461.2115a","article-title":"Power-law distribution of the world wide web","volume":"287","author":"Adamic","year":"2000","journal-title":"Science"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/316194.316229","article-title":"On power-law relationships of the internet topology","volume":"29","author":"Faloutsos","year":"1999","journal-title":"ACM Sigcomm Comput. Commun. Rev."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Meyerhenke, H., Sanders, P., and Wagner, D. (2013). Graph Partitioning and Graph Clustering. Proceedings of the 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, 13\u201314 February 2012, American Mathematical Society. Contemporary Mathematics.","DOI":"10.1090\/conm\/588"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/221\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:32:57Z","timestamp":1760164377000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/8\/221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":40,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["a14080221"],"URL":"https:\/\/doi.org\/10.3390\/a14080221","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,21]]}}}