{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T10:40:21Z","timestamp":1737369621209,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74456-6_19","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"194-205","source":"Crossref","is-referenced-by-count":5,"title":["Adapting Parallel Algorithms to the W-Stream Model, with Applications to Graph Problems"],"prefix":"10.1007","author":[{"given":"Camil","family":"Demetrescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruno","family":"Escoffier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel","family":"Moruz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Ribichini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","volume-title":"Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004)","author":"G. Aggarwal","year":"2004","unstructured":"Aggarwal, G., Datar, M., Rajagopalan, S., Ruhl, M.: On the streaming model augmented with a sorting primitive. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), IEEE Computer Society Press, Los Alamitos (2004)"},{"issue":"1","key":"19_CR2","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Computer and System Sciences\u00a058(1), 137\u2013147 (1999)","journal-title":"J. Computer and System Sciences"},{"issue":"5","key":"19_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0020-0190(90)90196-5","volume":"33","author":"R. Anderson","year":"1990","unstructured":"Anderson, R., Miller, G.: A simple randomized parallel algorithm for list-ranking. Information Processing Letters\u00a033(5), 269\u2013273 (1990)","journal-title":"Information Processing Letters"},{"key":"19_CR4","first-page":"1","volume-title":"Proceedings of the 21st ACM Symposium on Principles of Database Systems (PODS 2002)","author":"B. Babcock","year":"2002","unstructured":"Babcock, B., Babu, S., Datar, M., Motwani, R., Widom, J.: Models and issues in data stream systems. In: Proceedings of the 21st ACM Symposium on Principles of Database Systems (PODS 2002), pp. 1\u201316. ACM Press, New York (2002)"},{"key":"19_CR5","first-page":"623","volume-title":"Proc. 13th annual ACM-SIAM symposium on Discrete algorithms (SODA 2002)","author":"Z. Bar-Yossef","year":"2002","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proc. 13th annual ACM-SIAM symposium on Discrete algorithms (SODA 2002), pp. 623\u2013632. ACM Press, New York (2002)"},{"doi-asserted-by":"crossref","unstructured":"Blelloch, G., Maggs, B.: Parallel algorithms. In: The Computer Science and Engineering Handbook, pp. 277\u2013315 (1997)","key":"19_CR6","DOI":"10.1201\/9781420049503-c48"},{"key":"19_CR7","first-page":"139","volume-title":"Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1995)","author":"Y. Chiang","year":"1995","unstructured":"Chiang, Y., Goodrich, M., Grove, E., Tamassia, R., Vemgroff, D., Vitter, J.: External-memory graph algorithms. In: Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1995), pp. 139\u2013149. ACM Press, New York (1995)"},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1145\/1109557.1109635","volume-title":"Proc. 17th Annual ACM-SIAM Symposium of Discrete Algorithms (SODA 2006)","author":"C. Demetrescu","year":"2006","unstructured":"Demetrescu, C., Finocchi, I., Ribichini, A.: Trading off space for passes in graph streaming problems. In: Proc. 17th Annual ACM-SIAM Symposium of Discrete Algorithms (SODA 2006), pp. 714\u2013723. ACM Press, New York (2006)"},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","first-page":"207","volume-title":"Automata, Languages and Programming","author":"J. Feigenbaum","year":"2004","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 207\u2013216. Springer, Heidelberg (2004)"},{"unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: the value of space. In: Proceedings of the 16th ACM\/SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 745\u2013754 (2005)","key":"19_CR10"},{"issue":"1","key":"19_CR11","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/S0097539799361701","volume":"32","author":"J. Feigenbaum","year":"2002","unstructured":"Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.: An approximate L 1 difference algorithm for massive data streams. SIAM Journal on Computing\u00a032(1), 131\u2013151 (2002)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Gilbert, A., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., Strauss, M.: Fast, small-space algorithms for approximate histogram maintenance. In: Proc. 34th ACM Symposium on Theory of Computing (STOC 2002), pp. 389\u2013398. ACM Press, New York (2002)","key":"19_CR12","DOI":"10.1145\/509907.509966"},{"unstructured":"Golab, L., Ozsu, M.: Data stream management issues: a survey. Technical report, School of Computer Science, University of Waterloo, TR CS-2003-08 (2003)","key":"19_CR13"},{"key":"19_CR14","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1090\/dimacs\/050\/05","volume":"50","author":"M. Henzinger","year":"1999","unstructured":"Henzinger, M., Raghavan, P., Rajagopalan, S.: Computing on data streams. In: \u201cExternal Memory algorithms\u201d. DIMACS series in Discrete Mathematics and Theoretical Computer Science\u00a050, 107\u2013118 (1999)","journal-title":"DIMACS series in Discrete Mathematics and Theoretical Computer Science"},{"key":"19_CR15","volume-title":"An introduction to parallel algorithms","author":"J. J\u00e1j\u00e1","year":"1992","unstructured":"J\u00e1j\u00e1, J.: An introduction to parallel algorithms. Addison-Wesley, Reading (1992)"},{"doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambr. U. Press (1997)","key":"19_CR16","DOI":"10.1017\/CBO9780511574948"},{"issue":"4","key":"19_CR17","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal of Computing\u00a015(4), 1036\u20131053 (1986)","journal-title":"SIAM Journal of Computing"},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"I. Munro","year":"1980","unstructured":"Munro, I., Paterson, M.: Selection and sorting with limited storage. Theoretical Computer Science\u00a012, 315\u2013323 (1980)","journal-title":"Theoretical Computer Science"},{"unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Technical report (2003), Available at http:\/\/athos.rutgers.edu\/~muthu\/stream-1-1.ps","key":"19_CR19"},{"doi-asserted-by":"crossref","unstructured":"Reif, J.: Optimal parallel algorithms for integer sorting and graph connectivity. Technical Report TR 08-85, Aiken Comp. Lab, Harvard U., Cambridge (1985)","key":"19_CR20","DOI":"10.1109\/SFCS.1985.9"},{"unstructured":"Ruhl, M.: Efficient Algorithms for New Computational Models. PhD thesis, Massauchussets Institute of Technology (September 2003)","key":"19_CR21"},{"issue":"1","key":"19_CR22","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Shiloach, Y., Vishkin, U.: An o(logn) Parallel Connectivity Algorithm. J. Algorithms\u00a03(1), 57\u201367 (1982)","journal-title":"J. Algorithms"},{"unstructured":"Sullivan, M., Heybey, A.: Tribeca: A system for managing large databases of network traffic. In: Proceedings USENIX Annual Technical Conference (1998)","key":"19_CR23"},{"key":"19_CR24","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1109\/SFCS.1984.715896","volume-title":"Proc. 25th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1984)","author":"R. Tarjan","year":"1984","unstructured":"Tarjan, R., Vishkin, U.: Finding biconnected components and computing tree functions in logarithmic parallel time. In: Proc. 25th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1984), pp. 12\u201320. IEEE Computer Society Press, Los Alamitos (1984)"},{"issue":"1","key":"19_CR25","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1137\/0220006","volume":"20","author":"J. Ullman","year":"1991","unstructured":"Ullman, J., Yannakakis, M.: High-probability parallel transitive-closure algorithms. SIAM Journal on Computing\u00a020(1), 100\u2013125 (1991)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T09:36:37Z","timestamp":1737365797000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}