{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T08:10:07Z","timestamp":1746346207057,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662447765"},{"type":"electronic","value":"9783662447772"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44777-2_10","type":"book-chapter","created":{"date-parts":[[2014,8,16]],"date-time":"2014-08-16T10:43:15Z","timestamp":1408185795000},"page":"112-124","source":"Crossref","is-referenced-by-count":2,"title":["The Batched Predecessor Problem in External Memory"],"prefix":"10.1007","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[]},{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[]},{"given":"Mayank","family":"Goswami","sequence":"additional","affiliation":[]},{"given":"Dzejla","family":"Medjedovic","sequence":"additional","affiliation":[]},{"given":"Pablo","family":"Montes","sequence":"additional","affiliation":[]},{"given":"Meng-Tsung","family":"Tsai","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Arge, L., Larsen, K.D.: Orthogonal range reporting: Query lower bounds, optimal structures in 3-d, and higher-dimensional improvements. In: 26th Annual Symposium on Computational Geometry (SoCG), pp. 240\u2013246 (2010)","DOI":"10.1145\/1810959.1811001"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Afshani, P., Arge, L., Larsen, K.G.: Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model. In: 28th Annual Symposium on Computational Geometry (SoCG), pp. 323\u2013332 (2012)","DOI":"10.1145\/2261250.2261299"},{"key":"10_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, 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"issue":"1","key":"10_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-003-1021-x","volume":"37","author":"L. Arge","year":"2003","unstructured":"Arge, L.: The buffer tree: A technique for designing batched external data structures. Algorithmica\u00a037(1), 1\u201324 (2003)","journal-title":"Algorithmica"},{"issue":"2","key":"10_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF02579310","volume":"2","author":"B. Bollob\u00e1s","year":"1982","unstructured":"Bollob\u00e1s, B., Fernandez de la Vega, W.: The diameter of random regular graphs. Combinatorica\u00a02(2), 125\u2013134 (1982)","journal-title":"Combinatorica"},{"key":"10_CR6","unstructured":"Brodal, G.S., Fagerberg, R.: Lower bounds for external memory dictionaries. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 546\u2013554 (2003)"},{"key":"10_CR7","unstructured":"Buchsbaum, A.L., Goldwasser, M., Venkatasubramanian, S., Westbrook, J.R.: On external memory graph traversal. In: 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 859\u2013860 (2000)"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Dittrich, W., Hutchinson, D., Maheshwari, A.: Blocking in parallel multisearch problems (extended abstract). In: 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 98\u2013107 (1998)","DOI":"10.1145\/277651.277676"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Tsay, J.J., Cheng, N.C., Vitter, J., Vengroff, D.E., Vitter, J.S.: External-memory computational geometry. In: 1993 IEEE 34th Annual Foundations of Computer Science (FOCS), pp. 714\u2013723 (1993)","DOI":"10.1109\/SFCS.1993.366816"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Hellerstein, J.M., Koutsoupias, E., Papadimitriou, C.H.: On the analysis of indexing schemes. In: 16th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 249\u2013256 (1997)","DOI":"10.1145\/263661.263688"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/505241.505244","volume":"49","author":"J.M. Hellerstein","year":"2002","unstructured":"Hellerstein, J.M., Koutsoupias, E., Miranker, D.P., Papadimitriou, C.H., Samoladas, V.: On a model of indexability and its bounds for range queries. J. ACM\u00a049, 35\u201355 (2002)","journal-title":"J. ACM"},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/11561071_23","volume-title":"Algorithms \u2013 ESA 2005","author":"M. Karpinski","year":"2005","unstructured":"Karpinski, M., Nekrich, Y.: Predecessor queries in constant time? In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 238\u2013248. Springer, Heidelberg (2005)"},{"key":"10_CR13","unstructured":"Knudsen, M., Larsen, K.: I\/O-complexity of comparison and permutation problems. Master\u2019s thesis, DAIMI (November 1992)"},{"key":"10_CR14","unstructured":"Knuth, D.E.: The Art of Computer Programming: Sorting and Searching, vol.\u00a03. Addison-Wesley (1973)"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 232\u2013240 (2006)","DOI":"10.1145\/1132516.1132551"},{"issue":"1","key":"10_CR16","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0195-6698(85)80023-8","volume":"6","author":"V. R\u00f6dl","year":"1985","unstructured":"R\u00f6dl, V.: On a packing and covering problem. European Journal of Combinatorics\u00a06(1), 69\u201378 (1985)","journal-title":"European Journal of Combinatorics"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Samoladas, V., Miranker, D.P.: A lower bound theorem for indexing schemes and its application to multidimensional range queries. In: 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 44\u201351 (1998)","DOI":"10.1145\/275487.275493"},{"key":"10_CR18","unstructured":"Subramanian, S., Ramaswamy, S.: The p-range tree: A new data structure for range searching in secondary memory. In: Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 378\u2013387 (1995)"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Tamassia, R., Vitter, J.S.: Optimal cooperative search in fractional cascaded data structures. In: Algorithmica, pp. 307\u2013316 (1990)","DOI":"10.1145\/97444.97698"},{"key":"10_CR20","unstructured":"Tao, T., Vu, V.H.: Additive Combinatorics. Cambridge University Press (2009)"},{"issue":"2","key":"10_CR21","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R.E. Tarjan","year":"1979","unstructured":"Tarjan, R.E.: A class of algorithms which require nonlinear time to maintain disjoint sets. Journal of Computer and System Sciences\u00a018(2), 110\u2013127 (1979)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44777-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T07:34:17Z","timestamp":1746344057000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44777-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662447765","9783662447772"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44777-2_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}