{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T05:06:41Z","timestamp":1737522401896,"version":"3.33.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,9,28]],"date-time":"2007-09-28T00:00:00Z","timestamp":1190937600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,1]]},"DOI":"10.1007\/s00453-007-9007-8","type":"journal-article","created":{"date-parts":[[2007,9,27]],"date-time":"2007-09-27T18:19:16Z","timestamp":1190917156000},"page":"50-68","source":"Crossref","is-referenced-by-count":5,"title":["Cache-Oblivious R-Trees"],"prefix":"10.1007","volume":"53","author":[{"given":"Lars","family":"Arge","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"de Berg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Herman","family":"Haverkort","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,9,28]]},"reference":[{"key":"9007_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Arge, L., Danner, A., Holland-Minkley, B.: Cache-oblivious data structures for orthogonal range searching. In: Proc. ACM Symposium on Computational Geometry, pp. 237\u2013245 (2003)","DOI":"10.1145\/777792.777828"},{"key":"9007_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Arge, L., Procopiuc, O., Vitter, J.S.: A framework for index bulk loading and dynamization. In: Proc. International Colloquium on Automata, Languages, and Programming, pp. 115\u2013127 (2001)","DOI":"10.1007\/3-540-48224-5_10"},{"key":"9007_CR3","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/s00454-002-2817-1","volume":"28","author":"P.K. Agarwal","year":"2002","unstructured":"Agarwal, P.K., de Berg, M., Gudmundsson, J., Hammar, M., Haverkort, H.J.: Box-trees and R-trees with near-optimal query time. Discrete Comput. Geom. 28, 291\u2013312 (2002)","journal-title":"Discrete Comput. Geom."},{"key":"9007_CR4","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/conm\/223\/03131","volume-title":"Advances in Discrete and Computational Geometry","author":"P.K. Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. In: Chazelle, B., Goodman, J.E., Pollack, R. (eds.) Advances in Discrete and Computational Geometry. Contemporary Mathematics, vol. 223, pp. 1\u201356. American Mathematical Society, Providence (1999)"},{"issue":"9","key":"9007_CR5","doi-asserted-by":"crossref","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 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"9007_CR6","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/978-1-4615-0005-6_9","volume-title":"Handbook of Massive Data Sets","author":"L. Arge","year":"2002","unstructured":"Arge, L.: External memory data structures. In: Abello, J., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Massive Data Sets, pp. 313\u2013358. Kluwer Academic, Dordrecht (2002)"},{"key":"9007_CR7","doi-asserted-by":"crossref","unstructured":"Arge, L., Bender, M., Demaine, E., Holland-Minkley, B., Munro, J.I.: Cache-oblivious priority-queue and graph algorithms. In: Proc. ACM Symposium on Theory of Computation, pp. 268\u2013276 (2002)","DOI":"10.1145\/509907.509950"},{"key":"9007_CR8","doi-asserted-by":"crossref","unstructured":"Arge, L., de Berg, M., Haverkort, H.J., Yi, K.: The priority R-tree: a practically efficient and worst-case-optimal R-tree. In: Symp. of the ACM Special Interest Group on Management of Data (SIGMOD), Paris, 2004, pp. 347\u2013358","DOI":"10.1145\/1007568.1007608"},{"issue":"2","key":"9007_CR9","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.comgeo.2003.04.001","volume":"29","author":"L. Arge","year":"2004","unstructured":"Arge, L., Vahrenhold, J.: I\/O-efficient dynamic planar point location. Comput. Geom. Theory Appl. 29(2), 147\u2013162 (2004)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9007_CR10","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.: Organization and maintenance of large ordered indexes. Acta Inform. 1, 173\u2013189 (1972)","journal-title":"Acta Inform."},{"key":"9007_CR11","doi-asserted-by":"crossref","unstructured":"Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R*-tree: an efficient and robust access method for points and rectangles. In: Proc. SIGMOD International Conference on Management of Data, pp. 322\u2013331 (1990)","DOI":"10.1145\/93605.98741"},{"key":"9007_CR12","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Cole, R., Raman, R.: Exponential structures for cache-oblivious algorithms. In: Proc. International Colloquium on Automata, Languages, and Programming, pp. 195\u2013207 (2002)","DOI":"10.1007\/3-540-45465-9_18"},{"key":"9007_CR13","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. In: Proc. IEEE Symposium on Foundations of Computer Science, pp. 339\u2013409 (2000)","DOI":"10.1109\/SFCS.2000.892128"},{"key":"9007_CR14","unstructured":"Bender, M.A., Duan, Z., Iacono, J., Wu, J.: A locality-preserving cache-oblivious dynamic dictionary. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 29\u201338 (2002)"},{"issue":"5","key":"9007_CR15","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J.L. Bentley","year":"1979","unstructured":"Bentley, J.L.: Decomposable searching problems. Inf. Process. Lett. 8(5), 244\u2013251 (1979)","journal-title":"Inf. Process. Lett."},{"key":"9007_CR16","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Jacob, R.: Cache oblivious search trees via binary trees of small height. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 39\u201348 (2002)","DOI":"10.7146\/brics.v8i36.21696"},{"key":"9007_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/3-540-36136-7_20","volume-title":"International Symposium on Algorithms and Computation","author":"G.S. Brodal","year":"2002","unstructured":"Brodal, G.S., Fagerberg, R.: Funnel heap\u2014a cache oblivious priority queue. In: International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 2518, pp. 219\u2013228. Springer, Berlin (2002)"},{"issue":"2","key":"9007_CR18","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D. Comer","year":"1979","unstructured":"Comer, D.: The ubiquitous B-tree. ACM Comput. Surv. 11(2), 121\u2013137 (1979)","journal-title":"ACM Comput. Surv."},{"key":"9007_CR19","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proc. IEEE Symposium on Foundations of Computer Science, pp. 285\u2013298 (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"issue":"2","key":"9007_CR20","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1145\/280277.280279","volume":"30","author":"V. Gaede","year":"1998","unstructured":"Gaede, V., G\u00fcnther, O.: Multidimensional access methods. ACM Comput. Surv. 30(2), 170\u2013231 (1998)","journal-title":"ACM Comput. Surv."},{"key":"9007_CR21","doi-asserted-by":"crossref","unstructured":"Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proc. SIGMOD International Conference on Management of Data, pp. 47\u201357 (1984)","DOI":"10.1145\/602259.602266"},{"key":"9007_CR22","unstructured":"Haverkort, H.J.: Results on geometric networks and data structures. PhD thesis, Utrecht University (2004)"},{"key":"9007_CR23","unstructured":"Kamel, I., Faloutsos, C.: Hilbert R-tree: An improved R-tree using fractals. In: Proc. International Conference on Very Large Databases, pp. 500\u2013509 (1994)"},{"key":"9007_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/3-540-49257-7_17","volume-title":"Proc. International Conference on Database Theory","author":"K.V.R. Kanth","year":"1999","unstructured":"Kanth, K.V.R., Singh, A.K.: Optimal dynamic range searching in non-replicating index structures. In: Proc. International Conference on Database Theory. Lecture Notes in Computer Science, vol. 1540, pp. 257\u2013276. Springer, Berlin (1999)"},{"key":"9007_CR25","series-title":"Advanced Information and Knowledge Processing","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84628-293-5","volume-title":"R-Trees: Theory and Applications","author":"Y. Manolopoulos","year":"2006","unstructured":"Manolopoulos, Y., Nanopoulos, A., Papadopoulos, A.N., Theodoridis, Y.: R-Trees: Theory and Applications. Advanced Information and Knowledge Processing. Springer, Berlin (2006)"},{"key":"9007_CR26","unstructured":"Prokop, H.: Cache-oblivious algorithms. Master\u2019s thesis, Massachusetts Institute of Technology, Cambridge, MA, June 1999"},{"key":"9007_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/3-540-44688-5_6","volume-title":"Proc. Workshop on Algorithm Engineering","author":"N. Rahman","year":"2001","unstructured":"Rahman, N., Cole, R., Raman, R.: Optimized predecessor data structures for internal memory. In: Proc. Workshop on Algorithm Engineering. Lecture Notes in Computer Science, vol. 2141, pp. 67\u201378. Springer, Berlin (2001)"},{"key":"9007_CR28","unstructured":"Sellis, T., Roussopoulos, N., Faloutsos, C.: The R+-tree: a dynamic index for multi-dimensional objects. In: Proc. International Conference on Very Large Databases, pp. 507\u2013518 (1987)"},{"issue":"2","key":"9007_CR29","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J.S. Vitter","year":"2001","unstructured":"Vitter, J.S.: External memory algorithms and data structures: dealing with MASSIVE data. ACM Comput. Surv. 33(2), 209\u2013271 (2001)","journal-title":"ACM Comput. Surv."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9007-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9007-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9007-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T07:22:33Z","timestamp":1737444153000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9007-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,28]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["9007"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9007-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2007,9,28]]}}}