{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,20]],"date-time":"2025-09-20T22:09:31Z","timestamp":1758406171274},"publisher-location":"Dordrecht","reference-count":24,"publisher":"Springer Netherlands","isbn-type":[{"type":"print","value":"9781402096877"},{"type":"electronic","value":"9781402096884"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-1-4020-9688-4_17","type":"book-chapter","created":{"date-parts":[[2009,4,20]],"date-time":"2009-04-20T10:15:15Z","timestamp":1240222515000},"page":"455-476","source":"Crossref","is-referenced-by-count":12,"title":["A Survey of Graph Algorithms Under Extended Streaming Models of Computation"],"prefix":"10.1007","author":[{"given":"Thomas C.","family":"O\u2019Connell","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"G. Aggarwal, M. Datar, S. Rajagopalan, and M. Ruhl. On the streaming model augmented with a sorting primitive. In Proc. 45th Annual IEEE Symp. Foundations of Computer Science (FOCS\u201904), pages 540\u2013549, Rome, Italy, 2004.","DOI":"10.1109\/FOCS.2004.48"},{"issue":"1","key":"17_CR2","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. J. Computer and System Sciences, 58(1):137\u2013147, 1999.","journal-title":"J. Computer and System Sciences"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In Proc. 21st ACM SIGMOD-SIGACT-SIGART Symp. Principles of Database Systems, pages 1\u201316, Madison, WI, 2002.","DOI":"10.1145\/543613.543615"},{"key":"17_CR4","unstructured":"Z. Bar-Yossef, R. Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proc. 13th Annual ACM-SIAM Symp. Discrete Algorithms, pages 623\u2013632, San Francisco, CA, 2002."},{"issue":"4","key":"17_CR5","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"Z. Bar-Yossef","year":"2004","unstructured":"Z. Bar-Yossef, T. Jayram, R. Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Computer and System Sciences, 68(4):702\u2013732, 2004.","journal-title":"J. Computer and System Sciences"},{"issue":"1-3","key":"17_CR6","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/S0304-3975(02)00569-8","volume":"299","author":"A.\u00a0L. Buchsbaum","year":"2003","unstructured":"A.\u00a0L. Buchsbaum, R. Giancarlo, and J.\u00a0R. Westbrook. On finding common neighborhoods in massive graphs. Theoretical Computer Science, 299(1-3):707\u2013718, 2003.","journal-title":"Theoretical Computer Science"},{"key":"17_CR7","volume-title":"Introduction to algorithms","author":"T.\u00a0H. Cormen","year":"2001","unstructured":"T.\u00a0H. Cormen, C.\u00a0E. Leiserson, R.\u00a0L. Rivest, and C. Stein. Introduction to algorithms. McGraw\u2013Hill\/MIT Press, Cambridge, 2001."},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"C. Demetrescu, I. Finocchi, and A. Ribichini. Trading off space for passes in graph streaming problems. In Proc. 17th Annual ACM-SIAM Symp. Discrete Algorithms, pages 714\u2013723, Miami, FL, 2006.","DOI":"10.1145\/1109557.1109635"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"M. Elkin and J. Zhang. Efficient algorithms for constructing (1+\u03b5, \u03b2)-spanners in the distributed and streaming models. In Proc. 23rd Annual ACM Symp. Principles of Distributed Computing, pages 160\u2013168, St. John\u2019s, Canada, 2004.","DOI":"10.1145\/1011767.1011791"},{"issue":"5","key":"17_CR10","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D. Eppstein","year":"1997","unstructured":"D. Eppstein, Z. Galil, G.\u00a0F. Italiano, and A. Nissenzweig. Sparsification: a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669\u2013696, 1997.","journal-title":"J. ACM"},{"key":"17_CR11","unstructured":"J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. Graph distances in the streaming model: the value of space. In Proc. 16th Annual ACM-SIAM Symp. Discrete Algorithms, pages 745\u2013754, Vancouver, Canada, 2005."},{"issue":"2-3","key":"17_CR12","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J. Feigenbaum","year":"2005","unstructured":"J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science, 348(2-3):207\u2013216, 2005.","journal-title":"Theoretical Computer Science"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"R. Guha, R. Kumar, D. Sivakumar, and R. Sundaram. Unweaving a web of documents. In Proc. 11th ACM SIGKDD Intl. Conf. Knowledge Discovery in Data Mining, pages 574\u2013579, Chicago, IL, 2005.","DOI":"10.1145\/1081870.1081939"},{"key":"17_CR14","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"107","volume-title":"External Memory Algorithms","author":"M. Henzinger","year":"2000","unstructured":"M. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on data streams. In External Memory Algorithms. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume\u00a050, pages 107\u2013118. American Mathematical Society, Providence, 2000."},{"key":"17_CR15","series-title":"The Art of Computer Programming","volume-title":"Sorting and Searching","author":"D.\u00a0E. Knuth","year":"1998","unstructured":"D.\u00a0E. Knuth. Sorting and Searching. The Art of Computer Programming, volume\u00a03. Addison\u2013Wesley\u2013Longman, Redwood City, 2nd edition, 1998.","edition":"2"},{"key":"17_CR16","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574948","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1996","unstructured":"E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, New York, 1996."},{"issue":"3","key":"17_CR17","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"J.\u00a0I. Munro","year":"1980","unstructured":"J.\u00a0I. Munro and M.\u00a0S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12(3):315\u2013323, 1980.","journal-title":"Theoretical Computer Science"},{"key":"17_CR18","unstructured":"S. Muthukrishnan. Data streams: algorithms and applications. In Proc. 14th Annual ACM-SIAM Symp. Discrete Algorithms, page 413, Baltimore, MD, 2003."},{"key":"17_CR19","unstructured":"L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford Digital Libraries, Nov. 1999."},{"key":"17_CR20","unstructured":"M. Ruhl. Efficient algorithms for new computational models. PhD Thesis, Department of Computer Science, MIT, Cambridge, MA, 2003."},{"key":"17_CR21","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.\u00a0E. Tarjan","year":"1983","unstructured":"R.\u00a0E. Tarjan. Data Structures and Network Algorithms. SIAM, Philadelphia, 1983."},{"issue":"1-2","key":"17_CR22","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0020-0190(00)00128-9","volume":"76","author":"R. Uehara","year":"2000","unstructured":"R. Uehara and Z. Chen. Parallel approximation algorithms for maximum weighted matching in general graphs. Information Processing Letters, 76(1-2):13\u201317, 2000.","journal-title":"Information Processing Letters"},{"issue":"2","key":"17_CR23","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J.\u00a0S. Vitter","year":"2001","unstructured":"J.\u00a0S. Vitter. External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys, 33(2):209\u2013271, 2001.","journal-title":"ACM Computing Surveys"},{"key":"17_CR24","doi-asserted-by":"crossref","unstructured":"A.\u00a0C. Yao. Some complexity questions related to distributive computing (preliminary report). In Proc. 11th Annual ACM Symp. Theory of Computing, pages 209\u2013213, Atlanta, GA, Apr.\u2013May 1979.","DOI":"10.1145\/800135.804414"}],"container-title":["Fundamental Problems in Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4020-9688-4_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,29]],"date-time":"2021-04-29T05:55:37Z","timestamp":1619675737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4020-9688-4_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9781402096877","9781402096884"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-1-4020-9688-4_17","relation":{},"subject":[],"published":{"date-parts":[[2009]]}}}