{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:26:46Z","timestamp":1787387206291,"version":"build-2736575974"},"reference-count":47,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,2]]},"abstract":"<jats:p>Consider a set of N records corresponding to points in k-dimensional space ($k \\geqq 2$). This article introduces one new data structure which uses memory $O(N\\log ^{k - 1} N)$ for supporting orthogonal range queries with worst-case complexity $O(\\log ^{k - 1} N)$ and several modifications of this proposal for a dynamic environment. These results are especially useful when $k = 2$.<\/jats:p>","DOI":"10.1137\/0214019","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"232-253","source":"Crossref","is-referenced-by-count":115,"title":["New Data Structures for Orthogonal Range Queries"],"prefix":"10.1137","volume":"14","author":[{"given":"Dan E.","family":"Willard","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RAHHOU174","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"RAVSH81","doi-asserted-by":"crossref","unstructured":"Z. Avid, E. Shamir,  A direct solution to range search and related problems for product regions,  Proc. 22nd Annual Symposium on Foundations of Computer Science,  1981,  123\u2013216","DOI":"10.1109\/SFCS.1981.5"},{"key":"RBE75","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"RBE80","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358850"},{"key":"RBEMA80","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263991"},{"key":"RBESA80","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"RBESH77","unstructured":"J. L. Bentley, M. I. Shamos,  A problem in multivariate statistics: algorithm, data structure, and applications,  Proc. Fifteenth Allerton Conference on Communication, Control, and Computing,  1977,  193\u2013201"},{"key":"RBEWO80","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675628"},{"key":"RBO81","doi-asserted-by":"publisher","DOI":"10.1137\/0210056"},{"key":"RCH83","doi-asserted-by":"crossref","unstructured":"B. Chazelle,  New algorithmic methods based on filtering,  24th IEEE Symposium on Foundations of Computer Science,  1983,  122\u2013132","DOI":"10.1109\/SFCS.1983.17"},{"key":"RCOYA83","doi-asserted-by":"crossref","unstructured":"R. Cole, C. Yap,  Geometric retrieval problems,  25th IEEE Symposium on Foundations of Computer Science,  1984,  112\u2013121","DOI":"10.1109\/SFCS.1983.22"},{"key":"RDI82","doi-asserted-by":"crossref","unstructured":"P. F. Dietz,  Maintaining order in a linked list,  Proc.14th Annual ACM Symposium on Theory of Computing,  1982,  122\u2013128","DOI":"10.1145\/800070.802184"},{"key":"RDI84","unstructured":"P. F. Dietz, an improved version of [Di82] to appear in Information and Control"},{"key":"RDOMU80","doi-asserted-by":"crossref","unstructured":"D. Dobkin, J. I. Munro,  Efficient use of the past,  Proc. 21st Annual Symposium on Foundations of Computer Science,  1980,  200\u2013206","DOI":"10.1109\/SFCS.1980.18"},{"key":"RED80","unstructured":"H. Edelsbrunner,  Dynamic data structures for orthogonal intersections queries, Report, #59, Technische Universit\u00e4t Graz,  1980"},{"key":"RED81","first-page":"34","volume":"15","author":"Edelsbrunner H.","year":"1981","journal-title":"Bulletin of EATCS"},{"key":"REDOV83","unstructured":"H. Edelsbrunner, M. H. Overmars,  Batch dynamic solutions for decomposable search problems,  1983, V. Graz F118"},{"key":"RFIBE74","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"RFR81A","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322281"},{"key":"RFR8LB","doi-asserted-by":"publisher","DOI":"10.1137\/0210001"},{"key":"RKN73","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald E.","year":"1973"},{"key":"RLEWO77","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263763"},{"key":"RLEWO80","doi-asserted-by":"publisher","DOI":"10.1145\/320613.320618"},{"key":"RLEWO81","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90033-X"},{"key":"RLU78","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.1"},{"key":"RLU79","unstructured":"G. S. Lueker,  A transformation for adding range restriction capability to dynamic datq structures for decomposable searching problems, Technical Report, #129, Department of Information and Computer Science, Univ. California, Irvine,  1979"},{"key":"RLUWI82","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90119-3"},{"key":"RMC81","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"RNIRE73","doi-asserted-by":"publisher","DOI":"10.1137\/0202005"},{"key":"ROV83","volume-title":"The design of dynamic data structures","author":"Overmars Mark H.","year":"1983"},{"key":"ROVLE82","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264354"},{"key":"RVAWO80","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(80)90034-9"},{"key":"RWI78A","unstructured":"D. E. Willard, Ph.D. Thesis,  Predicate-oriented database search algorithms, Harvard University,  1978, Also in Outstanding Dissertations in Computer Science, Garland Publishing, New York, 1979"},{"key":"RWI78B","unstructured":"D. E. Willard,  New data structures for orthogonal queries, Technical Report, TR-22-78, Center for Research in Computing Technology, Harvard Univ., Cambridge, MA,  1978, (the earlier draft of this report)"},{"key":"RWI78C","unstructured":"D. E. Willard,  Balanced forests of  K- d* trees as a dynamic data structure, Technical Report, TR-23-78, Center for Research in Computing Technology, Harvard Univ., Cambridge, MA,  1978"},{"key":"RWI79","unstructured":"D. E. Willard,  The super- B-tree algorithm, Technical Report, TR-03-79, Center for Research in Computing Technology, Harvard Univ., Cambridge, MA,  1979"},{"key":"RWI80","unstructured":"D. E. Willard,  K- d trees in a dynamic environment, Technical Report, 80-1, Department of Computer Science, Univ. Iowa, Ames,  1980"},{"key":"RWI81","unstructured":"D. E. Willard,  Two very fast tree data structures,  Proc.19th Annual Allertou Conference on Communication, Control and Computing,  1981,  355\u2013363"},{"key":"RWI82","doi-asserted-by":"publisher","DOI":"10.1137\/0211012"},{"key":"RWI83A","first-page":"663","volume-title":"Twenty-first annual Allerton conference on communication, control, and computing (Monticello, Ill., 1983)","author":"Willard Dan E.","year":"1983"},{"key":"RWI83B","unstructured":"D. E. Willard,  Abstract predicate retrieval theory, SUNY Albany Technical Report, 83-3,  1983"},{"key":"RWI84A","unstructured":"D. E. Willard,  A very efficient algorithm for evaluating relational calculus expressions,  ACM SIGMOD Conference,  1984"},{"key":"RWI84B","doi-asserted-by":"crossref","unstructured":"D. E. Willard,  A sampling algorithm for differentiable batch retrieval problems,  11th Int. Colloquium on Automata, Languages and Programming (ICALP-1984) 0587.68085","DOI":"10.1007\/3-540-13345-3_48"},{"key":"RWI84C","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90020-5"},{"key":"RWILU84","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3839"},{"key":"RYA82","unstructured":"A. C. Yao,  On the complexity of maintaining partial sums,  14th ACM STOC Symposium,  1982,  128\u2013135"},{"key":"RYA83","doi-asserted-by":"crossref","unstructured":"F. Yao,  A  3-space partition and its applications,  15th ACM Conference on Theory of Computing,  1983,  258\u2013264","DOI":"10.1145\/800061.808755"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:27Z","timestamp":1787337747000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,2]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,2]]}},"alternative-id":["10.1137\/0214019"],"URL":"https:\/\/doi.org\/10.1137\/0214019","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,2]]}}}