{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T20:37:41Z","timestamp":1765485461654,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>\n            Data stream processing has recently received increasing attention as a computational paradigm for dealing with massive data sets. Surprisingly, no algorithm with both sublinear space and passes is known for natural graph problems in classical read-only streaming. Motivated by technological factors of modern storage systems, some authors have recently started to investigate the computational power of less restrictive models where writing streams is allowed. In this article, we show that the use of intermediate temporary streams is powerful enough to provide effective space-passes tradeoffs for natural graph problems. In particular, for any space restriction of\n            <jats:italic>s<\/jats:italic>\n            bits, we show that single-source shortest paths in directed graphs with small positive integer edge weights can be solved in\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>3\/2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )\/\u221a\n            <jats:italic>s<\/jats:italic>\n            ) passes. The result can be generalized to deal with multiple sources within the same bounds. This is the first known streaming algorithm for shortest paths in directed graphs. For undirected connectivity, we devise an\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            )\/\n            <jats:italic>s<\/jats:italic>\n            ) passes algorithm. Both problems require \u03a9(\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>s<\/jats:italic>\n            ) passes under the restrictions we consider. We also show that the model where intermediate temporary streams are allowed can be strictly more powerful than classical streaming for some problems, while maintaining all of its hardness for others.\n          <\/jats:p>","DOI":"10.1145\/1644015.1644021","type":"journal-article","created":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T13:16:40Z","timestamp":1282655800000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Trading off space for passes in graph streaming problems"],"prefix":"10.1145","volume":"6","author":[{"given":"Camil","family":"Demetrescu","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irene","family":"Finocchi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Ribichini","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,12,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0088-5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.48"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90127-H"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02)","author":"Bar-Yossef Z.","key":"e_1_2_1_6_1","unstructured":"Bar-Yossef , Z. , Kumar , R. , and Sivakumar , D . 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02) . ACM, New York, 623--632. Bar-Yossef, Z., Kumar, R., and Sivakumar, D. 2002. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02). ACM, New York, 623--632."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250891"},{"key":"e_1_2_1_8_1","unstructured":"Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms Second Edition. The MIT Press Cambridge MA.   Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms Second Edition. The MIT Press Cambridge MA."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science","volume":"4708","author":"Demetrescu C.","unstructured":"Demetrescu , C. , Escoffier , B. , Moruz , G. , and Ribichini , A . 2007. Adapting parallel algorithms to the W-Stream model, with applications to graph problems . In Proceedings of the Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science , vol. 4708 . Springer-Verlag, Berlin, Germany, 194--205. Demetrescu, C., Escoffier, B., Moruz, G., and Ribichini, A. 2007. Adapting parallel algorithms to the W-Stream model, with applications to graph problems. In Proceedings of the Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 4708. Springer-Verlag, Berlin, Germany, 194--205."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science","volume":"3142","author":"Feigenbaum J.","unstructured":"Feigenbaum , J. , Kannan , S. , McGregor , A. , Suri , S. , and Zhang , J . 2004. On graph problems in a semi-streaming model . In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science , vol. 3142 . Springer-Verlag, Berlin, Germany. Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., and Zhang, J. 2004. On graph problems in a semi-streaming model. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 3142. Springer-Verlag, Berlin, Germany."},{"volume-title":"Proceedings of the 16th ACM\/SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Feigenbaum J.","key":"e_1_2_1_11_1","unstructured":"Feigenbaum , J. , Kannan , S. , McGregor , A. , Suri , S. , and Zhang , J . 2005. Graph distances in the streaming model: The value of space . In Proceedings of the 16th ACM\/SIAM Symposium on Discrete Algorithms (SODA). ACM , New York, 745--754. Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., and Zhang, J. 2005. Graph distances in the streaming model: The value of space. In Proceedings of the 16th ACM\/SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 745--754."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361701"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509966"},{"volume-title":"DIMACS 2001-43","author":"Gilbert A.","key":"e_1_2_1_14_1","unstructured":"Gilbert , A. , Kotidis , Y. , Muthukrishnan , S. , and Strauss , M . 2001. Quicksand: Quick summary and analysis of network data. Tech. rep ., DIMACS 2001-43 . Gilbert, A., Kotidis, Y., Muthukrishnan, S., and Strauss, M. 2001. Quicksand: Quick summary and analysis of network data. Tech. rep., DIMACS 2001-43."},{"key":"e_1_2_1_15_1","unstructured":"Golab L. and Ozsu M. 2003. Data stream management issues a survey. Tech. rep. TR CS-2003-08. School of Computer Science University of Waterloo.  Golab L. and Ozsu M. 2003. Data stream management issues a survey. Tech. rep. TR CS-2003-08. School of Computer Science University of Waterloo."},{"key":"e_1_2_1_16_1","unstructured":"Greene D. and Knuth D. 1982. Mathematics for the Analysis of Algorithms. Birkh\u00e4user.   Greene D. and Knuth D. 1982. Mathematics for the Analysis of Algorithms. Birkh\u00e4user."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1033"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142387"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_87"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065197"},{"volume-title":"Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (FOCS'95)","author":"Henzinger M.","key":"e_1_2_1_21_1","unstructured":"Henzinger , M. , and King , V . 1995. Fully dynamic biconnectivity and transitive closure . In Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (FOCS'95) . IEEE Computer Society Press, Los Alamitos, CA, 664--672. Henzinger, M., and King, V. 1995. Fully dynamic biconnectivity and transitive closure. In Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (FOCS'95). IEEE Computer Society Press, Los Alamitos, CA, 664--672."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Henzinger M. Raghavan P. and Rajagopalan S. 1999. Computing on data streams. In External Memory Algorithms. DIMACS series in Discrete Mathematics and Theoretical Computer Science 50 107--118.   Henzinger M. Raghavan P. and Rajagopalan S. 1999. Computing on data streams. In External Memory Algorithms. DIMACS series in Discrete Mathematics and Theoretical Computer Science 50 107--118.","DOI":"10.1090\/dimacs\/050\/05"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Kushilevitz E. and Nisan N. 1997. Communication Complexity. Cambridge Univirsity Press Cambridge UK.   Kushilevitz E. and Nisan N. 1997. Communication Complexity. Cambridge Univirsity Press Cambridge UK.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"key":"e_1_2_1_26_1","unstructured":"Muthukrishnan S. 2003. Data streams: Algorithms and applications. Tech. rep. http:\/\/athos.rutgers.edu\/~muthu\/stream-1-1.ps.  Muthukrishnan S. 2003. Data streams: Algorithms and applications. Tech. rep. http:\/\/athos.rutgers.edu\/~muthu\/stream-1-1.ps."},{"volume-title":"Proceedings of the USENIX Annual Technical Conference.","author":"Sullivan M.","key":"e_1_2_1_28_1","unstructured":"Sullivan , M. , and Heybey , A . 1998. Tribeca: A system for managing large databases of network traffic . In Proceedings of the USENIX Annual Technical Conference. Sullivan, M., and Heybey, A. 1998. Tribeca: A system for managing large databases of network traffic. In Proceedings of the USENIX Annual Technical Conference."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220006"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644015.1644021","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1644015.1644021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:44Z","timestamp":1750278404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644015.1644021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1644015.1644021"],"URL":"https:\/\/doi.org\/10.1145\/1644015.1644021","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}