{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T04:42:21Z","timestamp":1782967341136,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540438649","type":"print"},{"value":"9783540454656","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_37","type":"book-chapter","created":{"date-parts":[[2007,5,27]],"date-time":"2007-05-27T01:12:57Z","timestamp":1180228377000},"page":"426-438","source":"Crossref","is-referenced-by-count":25,"title":["Cache Oblivious Distribution Sweeping"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Fagerberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"issue":"9","key":"37_CR1","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal and J. S. Vitter. The input\/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116\u20131127, Sept. 1988.","journal-title":"Communications of the ACM"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"L. Arge, M. A. Bender, E. D. Demaine, B. Holland-Minkley, and J. I. Munro. Cache-oblivious priority queue and graph algorithm applications. In Proc. 34th Ann. ACM Symp. on Theory of Computing. ACM Press, 2002. To appear.","DOI":"10.1145\/509907.509950"},{"key":"37_CR3","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF01758844","volume":"8","author":"M. J. Atallah","year":"1992","unstructured":"M. J. Atallah and J.-J. Tsay. On the parallel-decomposability of geometric problems. Algorithmica, 8:209\u2013231, 1992.","journal-title":"Algorithmica"},{"key":"37_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173\u2013189, 1972.","journal-title":"Acta Informatica"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"M. A. Bender, R. Cole, and R. Raman. Exponential structures for efficient cache-oblivious algorithms. In Proc. 29th International Colloquium on Automata, Languages, and Programming (ICALP), 2002. These proceedings.","DOI":"10.1007\/3-540-45465-9_18"},{"key":"37_CR6","doi-asserted-by":"crossref","unstructured":"M. A. Bender, E. Demaine, and M. Farach-Colton. Cache-oblivious B-trees. In Proc. 41st Ann. Symp. on Foundations of Computer Science, pages 399\u2013409, 2000.","DOI":"10.1109\/SFCS.2000.892128"},{"key":"37_CR7","unstructured":"M. A. Bender, Z. Duan, J. Iacono, and J. Wu. A locality-preserving cache-oblivious dynamic dictionary. In Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 29\u201339, 2002."},{"key":"37_CR8","unstructured":"J. L. Bentley. Algorithms for Klee\u2019s rectangle problems. Carnegie-Mellon University, Pittsburgh, Penn., Department of Computer Science, unpublished notes, 1977."},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"G. S. Brodal and R. Fagerberg. Cache oblivious distribution sweeping. Technical Report RS-02-18, BRICS, Dept. of Computer Science, University of Aarhus, 2002.","DOI":"10.7146\/brics.v9i18.21964"},{"key":"37_CR10","doi-asserted-by":"crossref","unstructured":"G. S. Brodal, R. Fagerberg, and R. Jacob. Cache oblivious search trees via binary trees of small height. In Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 39\u201348, 2002.","DOI":"10.7146\/brics.v8i36.21696"},{"key":"37_CR11","volume-title":"Computational Geometry: Algorithms and Applications","author":"B. M de","year":"1997","unstructured":"M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer Verlag, Berlin, 1997."},{"key":"37_CR12","doi-asserted-by":"crossref","unstructured":"M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In 40th Annual Symposium on Foundations of Computer Science, pages 285\u2013297, 1999.","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"37_CR13","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. External-memory computational geometry. In Proc. 34th Ann. Symp. on Foundations of Computer Science, pages 714\u2013723, 1993.","DOI":"10.1109\/SFCS.1993.366816"},{"key":"37_CR14","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett., 1:132\u2013133, 1972.","journal-title":"Inf. Process. Lett."},{"key":"37_CR15","unstructured":"J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, second edition, 1996."},{"issue":"4","key":"37_CR16","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"H. T. Kung","year":"1975","unstructured":"H. T. Kung, F. Luccio, and F. P. Preparata. On finding the maxima of a set of vectores. Journal of the ACM, 22(4):469\u2013476, Oct. 1975.","journal-title":"Journal of the ACM"},{"key":"37_CR17","unstructured":"H. Prokop. Cache-oblivious algorithms. Master\u2019s thesis, Massachusetts Institute of Technology, June 1999."},{"issue":"2","key":"37_CR18","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J. S. Vitter","year":"2001","unstructured":"J. S. Vitter. External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys, 33(2):209\u2013271, June 2001.","journal-title":"ACM Computing Surveys"},{"key":"37_CR19","doi-asserted-by":"crossref","unstructured":"D. E. Willard and Y. C. Wee. Quasi-valid range querying and its implications for nearest neighbor problems. In Proceedings of the Fourth Annual Symposium on Computational Geometry, pages 34\u201343. ACM Press, 1988.","DOI":"10.1145\/73393.73398"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45465-9_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T11:05:47Z","timestamp":1556449547000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_37","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}