{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T13:28:39Z","timestamp":1754486919467},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602200"},{"type":"electronic","value":"9783540447474"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_86","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:53:48Z","timestamp":1330278828000},"page":"473-481","source":"Crossref","is-referenced-by-count":2,"title":["On the difficulty of range searching"],"prefix":"10.1007","author":[{"given":"Arne","family":"Andersson","sequence":"first","affiliation":[]},{"given":"Kurt","family":"Swanson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"41_CR1","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley. Decomposable searching problems. Inform. Process. Lett., 8:244\u2013251, 1979.","journal-title":"Inform. Process. Lett."},{"key":"41_CR2","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF00263991","volume":"13","author":"J. L. Bentley","year":"1980","unstructured":"J. L. Bentley and H. A. Maurer. Efficient worst-case data structures for range searching. Acta Inform., 13:155\u2013168, 1980.","journal-title":"Acta Inform."},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"B. Chazelle. Filtering search: a new approach to query-answering. In Proc. 24th Annu. IEEE Sympos. Found. Comput. Sci., pages 122\u2013132, 1983.","DOI":"10.1109\/SFCS.1983.17"},{"key":"41_CR4","doi-asserted-by":"crossref","unstructured":"B. Chazelle. Slimming down search structures: A functional approach to algorithm design. In Proc. 26th Annu. IEEE Sympos. Found. Comput. Sci., pages 165\u2013174, 1985.","DOI":"10.1109\/SFCS.1985.51"},{"key":"41_CR5","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B. Chazelle","year":"1988","unstructured":"B. Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput., 17:427\u2013462, 1988.","journal-title":"SIAM J. Comput."},{"key":"41_CR6","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1145\/77600.77614","volume":"37","author":"B. Chazelle","year":"1990","unstructured":"B. Chazelle. Lower bounds for orthogonal range searching, I: the reporting case. J. ACM, 37:200\u2013212, 1990.","journal-title":"J. ACM"},{"issue":"3","key":"41_CR7","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1145\/79147.79149","volume":"37","author":"B. Chazelle","year":"1990","unstructured":"B. Chazelle. Lower bounds for orthogonal range searching: II. the arithmetic model. Journal of the ACM, 37(3):439\u2013463, July 1990.","journal-title":"Journal of the ACM"},{"key":"41_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"R. A. Finkel","year":"1974","unstructured":"R. A. Finkel and J. L. Bentley. Quad trees: a data structure for retrieval on composite keys. Acta Inform., 4:1\u20139, 1974.","journal-title":"Acta Inform."},{"key":"41_CR9","doi-asserted-by":"crossref","unstructured":"M. L. Fredman and D. E. Willard. Blasting through the information theoretic barrier with fusion trees. In Proc. 22nd Annu. ACM Sympos. Theory Comput., pages 1\u20137, 1990.","DOI":"10.1145\/100216.100217"},{"key":"41_CR10","doi-asserted-by":"crossref","unstructured":"G. S. Lueker. A data structure for orthogonal range queries. In Proc. 19th Annu. IEEE Sympos. Found. Comput. Sci., pages 28\u201334, 1978.","DOI":"10.1109\/SFCS.1978.1"},{"key":"41_CR11","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E. M. McCreight","year":"1985","unstructured":"E. M. McCreight. Priority search trees. SIAM J. Comput., 14:257\u2013276, 1985.","journal-title":"SIAM J. Comput."},{"key":"41_CR12","unstructured":"P. B. Miltersen. Personal communication."},{"key":"41_CR13","doi-asserted-by":"crossref","unstructured":"P. B. Miltersen. Lower bounds for union-split-find related problems on random access machines. In Proc. 26th Ann. ACM STOC, pages 625\u2013634, 1994.","DOI":"10.1145\/195058.195415"},{"key":"41_CR14","doi-asserted-by":"crossref","unstructured":"P. B. Miltersen, N. Nisan, S. Safra, and A. Wigderson. On data structures and asymmetric communication complexity. In Proc. 27th Annu. ACM Sympos. Theory Comput., 1995. To appear.","DOI":"10.1145\/225058.225093"},{"key":"41_CR15","doi-asserted-by":"crossref","unstructured":"J. B. Saxe and J. L. Bentley. Transforming static data structures to dynamic structures. In Proc. 20th Annu. IEEE Sympos. Found. Comput. Sci., pages 148\u2013168, 1979.","DOI":"10.1109\/SFCS.1979.47"},{"key":"41_CR16","unstructured":"D. E. Willard. A new time complexity for orthogonal range queries. In Proc. 20th Allerton Conf. Commun. Control Comput., pages 462\u2013471, 1982."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_86.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:33:50Z","timestamp":1619573630000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_86"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_86","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}