{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T08:21:54Z","timestamp":1769156514844,"version":"3.49.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["EIA-9972879"],"award-info":[{"award-number":["EIA-9972879"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.023.301612.015.003"],"award-info":[{"award-number":["639.023.301612.015.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-04-1-0278"],"award-info":[{"award-number":["W911NF-04-1-0278"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["DAG07\/08"],"award-info":[{"award-number":["DAG07\/08"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>\n            We present the priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query using\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>N<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            )\n            <jats:sup>\n              1\u22121\/\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            +\n            <jats:italic>T<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            ) I\/Os, where\n            <jats:italic>N<\/jats:italic>\n            is the number of\n            <jats:italic>d<\/jats:italic>\n            -dimensional (hyper-) rectangles stored in the R-tree,\n            <jats:italic>B<\/jats:italic>\n            is the disk block size, and\n            <jats:italic>T<\/jats:italic>\n            is the output size. This is provably asymptotically optimal and significantly better than other R-tree variants, where a query may visit all\n            <jats:italic>N<\/jats:italic>\n            \/\n            <jats:italic>B<\/jats:italic>\n            leaves in the tree even when\n            <jats:italic>T<\/jats:italic>\n            = 0. We also present an extensive experimental study of the practical performance of the PR-tree using both real-life and synthetic data. This study shows that the PR-tree performs similarly to the best-known R-tree variants on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.\n          <\/jats:p>","DOI":"10.1145\/1328911.1328920","type":"journal-article","created":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T16:08:32Z","timestamp":1207066112000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":99,"title":["The priority R-tree"],"prefix":"10.1145","volume":"4","author":[{"given":"Lars","family":"Arge","sequence":"first","affiliation":[{"name":"MADALGO, University of Aarhus, Aarhus N, Denmark"}]},{"given":"Mark De","family":"Berg","sequence":"additional","affiliation":[{"name":"TU Eindhoven, Eindhoven, the Netherlands"}]},{"given":"Herman","family":"Haverkort","sequence":"additional","affiliation":[{"name":"TU Eindhoven, Eindhoven, the Netherlands"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Kowloon, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2008,3,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2817-1"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), 115--127","author":"Agarwal P. K.","unstructured":"Agarwal , P. K. , Arge , L. , Procopiuc , O. , and Vitter , J. S . 2001. A framework for index bulk loading and dynamization . In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), 115--127 . Agarwal, P. K., Arge, L., Procopiuc, O., and Vitter, J. S. 2001. A framework for index bulk loading and dynamization. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), 115--127."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2003.04.001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0107-6"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA), 88--100","author":"Arge L.","unstructured":"Arge , L. , Procopiuc , O. , and Vitter , J. S . 2002b. Implementing I\/O-efficient data structures using TPIE . In Proceedings of the European Symposium on Algorithms (ESA), 88--100 . Arge, L., Procopiuc, O., and Vitter, J. S. 2002b. Implementing I\/O-efficient data structures using TPIE. In Proceedings of the European Symposium on Algorithms (ESA), 88--100."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_8_1","volume-title":"-P","author":"Berchtold S.","year":"1998","unstructured":"Berchtold , S. , B\u00f6hm , C. , and Kriegel , H . -P . 1998 . Improving the query performance of high-dimensional index structures by bulk load operations. In Proceedings of the Conference on Extending Database Technology. Lecture Notes in Computer Science, vol. 1377 . Springer , 216--230. Berchtold, S., B\u00f6hm, C., and Kriegel, H.-P. 1998. Improving the query performance of high-dimensional index structures by bulk load operations. In Proceedings of the Conference on Extending Database Technology. Lecture Notes in Computer Science, vol. 1377. Springer, 216--230."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/46.3.319"},{"key":"e_1_2_1_10_1","volume-title":"The Discrepancy Method: Randomness and Complexity","author":"Chazelle B.","unstructured":"Chazelle , B. 2001. The Discrepancy Method: Randomness and Complexity . Cambridge University Press , New York . Chazelle, B. 2001. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, New York."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_12_1","volume-title":"Client-Server Paradise. In Proceedings of the International Conference on Very Large Databases, 558--569","author":"DeWitt D. J.","unstructured":"DeWitt , D. J. , Kabra , N. , Luo , J. , Patel , J. M. , and Yu , J . -B. 1994 . Client-Server Paradise. In Proceedings of the International Conference on Very Large Databases, 558--569 . DeWitt, D. J., Kabra, N., Luo, J., Patel, J. M., and Yu, J.-B. 1994. Client-Server Paradise. In Proceedings of the International Conference on Very Large Databases, 558--569."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/288692.288723"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513407"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the International Conference on Very Large Databases, 500--509","author":"Kamel I.","unstructured":"Kamel , I. , and Faloutsos , C . 1994. Hilbert R-tree: An improved R-tree using fractals . In Proceedings of the International Conference on Very Large Databases, 500--509 . Kamel, I., and Faloutsos, C. 1994. Hilbert R-tree: An improved R-tree using fractals. In Proceedings of the International Conference on Very Large Databases, 500--509."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/170088.170403"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Conference on Database Theory. Lecture Notes in Computer Science","volume":"154","author":"Kanth K. V. R.","unstructured":"Kanth , K. V. R. , and Singh , A. K . 1999. Optimal dynamic range searching in non-replicating index structures . In Proceedings of the International Conference on Database Theory. Lecture Notes in Computer Science , vol. 154 . Springer, 257--276. Kanth, K. V. R., and Singh, A. K. 1999. Optimal dynamic range searching in non-replicating index structures. In Proceedings of the International Conference on Database Theory. Lecture Notes in Computer Science, vol. 154. Springer, 257--276."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering, 497--506","author":"Leutenegger S. T.","unstructured":"Leutenegger , S. T. , L\u00f3pez , M. A. , and Edgington , J . 1996. STR: A simple and efficient algorithm for R-tree packing . In Proceedings of the IEEE International Conference on Data Engineering, 497--506 . Leutenegger, S. T., L\u00f3pez, M. A., and Edgington, J. 1996. STR: A simple and efficient algorithm for R-tree packing. In Proceedings of the IEEE International Conference on Data Engineering, 497--506."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Manolopoulos Y. Nanopoulos A. Papadopoulos A. N. and Theodoridis Y. 2005. R-Trees: Theory and Applications. Springer.   Manolopoulos Y. Nanopoulos A. Papadopoulos A. N. and Theodoridis Y. 2005. R-Trees: Theory and Applications. Springer.","DOI":"10.1007\/978-1-84628-293-5"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Symposium on Spatial and Temporal Databases.","author":"Procopiuc O.","unstructured":"Procopiuc , O. , Agarwal , P. K. , Arge , L. , and Vitter , J. S . 2003. BKD-Tree: A dynamic scalable KD-Tree . In Proceedings of the International Symposium on Spatial and Temporal Databases. Procopiuc, O., Agarwal, P. K., Arge, L., and Vitter, J. S. 2003. BKD-Tree: A dynamic scalable KD-Tree. In Proceedings of the International Symposium on Spatial and Temporal Databases."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/582318.582321"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/318898.318900"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Conference on Very Large Databases, 507--518","author":"Sellis T.","unstructured":"Sellis , T. , Roussopoulos , N. , and Faloutsos , C . 1987. The R&plus;-Tree: A dynamic index for multi-dimensional objects . In Proceedings of the International Conference on Very Large Databases, 507--518 . Sellis, T., Roussopoulos, N., and Faloutsos, C. 1987. The R&plus;-Tree: A dynamic index for multi-dimensional objects. In Proceedings of the International Conference on Very Large Databases, 507--518."},{"key":"e_1_2_1_26_1","volume-title":"1997 technical documentation","author":"Line","unstructured":"TIGER. 1998. TIGER\/ Line #8482; files , 1997 technical documentation . Washington, DC . http:\/\/www.census.gov\/geo\/tiger\/TIGER97D.pdf. TIGER. 1998. TIGER\/Line#8482; files, 1997 technical documentation. Washington, DC. http:\/\/www.census.gov\/geo\/tiger\/TIGER97D.pdf."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328920","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1328911.1328920","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:03Z","timestamp":1750254963000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1328911.1328920"}},"subtitle":["A practically efficient and worst-case optimal R-tree"],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1328911.1328920"],"URL":"https:\/\/doi.org\/10.1145\/1328911.1328920","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2005-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}