{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:16:36Z","timestamp":1763468196824},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662444641"},{"type":"electronic","value":"9783662444658"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44465-8_33","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T06:33:02Z","timestamp":1407825182000},"page":"384-395","source":"Crossref","is-referenced-by-count":5,"title":["On the Complexity of List Ranking in the Parallel External Memory Model"],"prefix":"10.1007","author":[{"given":"Riko","family":"Jacob","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"Lieber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nodari","family":"Sitchinava","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"33_CR1","unstructured":"Wyllie, J.: The Complexity of Parallel Computation. PhD thesis, Cornell University (1979)"},{"key":"33_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BFb0040376","volume-title":"VLSI Algorithms and Architectures","author":"R.J. Anderson","year":"1988","unstructured":"Anderson, R.J., Miller, G.L.: Deterministic parallel list ranking. In: Reif, J.H. (ed.) AWOC 1988. LNCS, vol.\u00a0319, pp. 81\u201390. Springer, Heidelberg (1988)"},{"issue":"9","key":"33_CR3","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"33_CR4","unstructured":"Chiang, Y.J., Goodrich, M., Grove, E., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: Proceedings of SODA 1995, pp. 139\u2013149 (1995)"},{"issue":"8","key":"33_CR5","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"L.G. Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM\u00a033(8), 103\u2013111 (1990)","journal-title":"Commun. ACM"},{"issue":"1","key":"33_CR6","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J. Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: Mapreduce: Simplified data processing on large clusters. Commun. ACM\u00a051(1), 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Karloff, H.J., Suri, S., Vassilvitskii, S.: A model of computation for mapreduce. In: Charikar, M. (ed.) SODA, pp. 938\u2013948. SIAM (2010)","DOI":"10.1137\/1.9781611973075.76"},{"issue":"2","key":"33_CR8","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/S0097539795294141","volume":"29","author":"M. Goodrich","year":"1999","unstructured":"Goodrich, M.: Communication-efficient parallel sorting. SIAM J. Comput.\u00a029(2), 416\u2013432 (1999)","journal-title":"SIAM J. Comput."},{"key":"33_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-25591-5_39","volume-title":"Algorithms and Computation","author":"M. Goodrich","year":"2011","unstructured":"Goodrich, M., Sitchinava, N., Zhang, Q.: Sorting, searching, and simulation in the mapreduce framework. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 374\u2013383. Springer, Heidelberg (2011)"},{"key":"33_CR10","doi-asserted-by":"crossref","unstructured":"Arge, L., Goodrich, M., Nelson, M., Sitchinava, N.: Fundamental parallel algorithms for private-cache chip multiprocessors. In: SPAA 2008, pp. 197\u2013206 (2008)","DOI":"10.1145\/1378533.1378573"},{"key":"33_CR11","unstructured":"Greiner, G.: Sparse Matrix Computations and their I\/O Complexity. Dissertation, Technische Universit\u00e4t M\u00fcnchen, M\u00fcnchen (2012)"},{"key":"33_CR12","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Ramachandran, V.: Handbook of theoretical computer science, pp. 869\u2013941 (1990)","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"33_CR13","doi-asserted-by":"crossref","unstructured":"Vishkin, U.: Randomized speed-ups in parallel computation. In: STOC, pp. 230\u2013239 (1984)","DOI":"10.1145\/800057.808686"},{"key":"33_CR14","doi-asserted-by":"crossref","unstructured":"Arge, L., Goodrich, M., Sitchinava, N.: Parallel external memory graph algorithms. In: IPDPS, pp. 1\u201311. IEEE (2010)","DOI":"10.1109\/IPDPS.2010.5470440"},{"key":"33_CR15","doi-asserted-by":"crossref","unstructured":"Jacob, R., Lieber, T., Sitchinava, N.: On the complexity of list ranking in the parallel external memory model. CoRR abs\/1406.3279 (2014)","DOI":"10.1007\/978-3-662-44465-8_33"},{"key":"33_CR16","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In: FOCS, pp. 222\u2013227. IEEE Computer Society (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44465-8_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T11:18:46Z","timestamp":1558955926000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44465-8_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662444641","9783662444658"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44465-8_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}