{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:51:11Z","timestamp":1725663071835},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167617"},{"type":"electronic","value":"9783540398592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16761-7_94","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:53:08Z","timestamp":1330195988000},"page":"444-453","source":"Crossref","is-referenced-by-count":2,"title":["Lower bounds for dynamic range query problems that permit subtraction (extended abstract)"],"prefix":"10.1007","author":[{"given":"Dan E.","family":"Willard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suny","family":"Albany","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"46_CR1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J.L. Bentley","year":"1975","unstructured":"J.L. Bentley, Multidimensional binary tree used for associative searching, Comm. of ACM 18 (1975), pp. 509\u2013517.","journal-title":"Comm. of ACM"},{"key":"46_CR2","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/358841.358850","volume":"23","author":"J.L. Bentley","year":"1980","unstructured":"__, Multidimensional divide-and-conquer, Comm. of ACM 23 (1980), pp. 214\u2013228.","journal-title":"Comm. of ACM"},{"key":"46_CR3","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF00263991","volume":"13","author":"J.L. Bentley","year":"1980","unstructured":"J.L. Bentley and H.A. Mauer, Efficient worst-case data structures for range searching, Acta Informatica 13 (1980), pp. 155\u2013168.","journal-title":"Acta Informatica"},{"key":"46_CR4","unstructured":"J.L. Bentley and M.I. Shamos, A problem in multi-variate statistics: algorithm, data structure and applications, 15-th Allerton Conf. on Comm., Contr., and Comp. (1977), p. 193\u2013201."},{"key":"46_CR5","unstructured":"J.L. Bentley and J.B. Saxe, Decomposable searching problems #1: static to dynamic transformations, J. Alg. (1980), pp. 301\u2013358."},{"key":"46_CR6","doi-asserted-by":"crossref","unstructured":"B. Chazelle, Filter Search a New Approach to Query Processing, 24th IEEE Symp. on Foundations of Computer Science, 1983, pp. 122\u2013132.","DOI":"10.1109\/SFCS.1983.17"},{"key":"46_CR7","unstructured":"_____, Slimming Down Data Structures a Functinal Approach to Algorithm Design, 25-th IEEE Symp. on Foundations of Computer Science, pp 165\u2013174."},{"key":"46_CR8","unstructured":"_____, A Functional Approach to Data Structures and Its Use in Multidimensional Searching, an expanded version of [Ch85a] issued as Brown Univ TR CS-85-16, 1985."},{"key":"46_CR9","unstructured":"B. Chazelle and L.J. Guibas, Fractional Cascading: A Data Structure Technique with Geometric Applications, 12-th ICALP (1985), pp. 90\u2013100."},{"key":"46_CR10","first-page":"34","volume":"15","author":"H. Edelsbrunner","year":"1981","unstructured":"H. Edelsbrunner, A Note on Dynamic Range Searching, Bulletin of EATCS 15(1981), pp. 34\u201340.","journal-title":"Bulletin of EATCS"},{"key":"46_CR11","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1016\/0020-0190(82)90068-0","volume":"14","author":"H. Edelsbrunner","year":"1982","unstructured":"H. Edelsbrunner and M. Overmars, On the equivalence of some rectangle search problems, Inf. Proc. Letters 14(1982), pp. 124\u2013127.","journal-title":"Inf. Proc. Letters"},{"key":"46_CR12","unstructured":"H. Edelsbrunner and E. Welzl, Halfplanar range search in linear space and O(N.695) time, Univ. of Graz report F111, 1983."},{"key":"46_CR13","doi-asserted-by":"crossref","unstructured":"M.L. Fredman, The Inherent Compl. of Dynamic Data Structures Which Accomodate Range Queries, 21st FOCS, 1980, pp 191\u2013199.","DOI":"10.1109\/SFCS.1980.47"},{"key":"46_CR14","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1145\/322276.322281","volume":"28","author":"M.L. Fredman","year":"1981","unstructured":"__, A lower bound on the complexity of orthogonal range queries, Journal of ACM 28 (1981), pp. 696\u2013706.","journal-title":"Journal of ACM"},{"key":"46_CR15","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0196-6774(81)90009-2","volume":"1","author":"M.L. Fredman","year":"1981","unstructured":"__, The Spanning Bound as a Measure of Range Query Complexity, Journal of Algorithms 1 (1981), pp 77\u201387.","journal-title":"Journal of Algorithms"},{"key":"46_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0210001","volume":"10","author":"M.L. Fredman","year":"1981","unstructured":"__, Lower Bounds on the Complexity of Some Optimal Data Structures, SIAM J. Comp. 10 (1981), pp 1\u201310.","journal-title":"SIAM J. Comp."},{"key":"46_CR17","unstructured":"_____, private communication, June 1985."},{"key":"46_CR18","doi-asserted-by":"crossref","unstructured":"O. Fries, K. Mehlhorn and St. Naher, Dynamization of geometric Data Structures, 1-st ACM Com. Geom. Conference, 1985, 168\u2013177.","DOI":"10.1145\/323233.323256"},{"key":"46_CR19","unstructured":"P. Flajolet and C. Puech, Tree Structures for Partial Match Retrieval, 24-th IEEE Symp. on FOCS (1983), pp. 282\u2013286."},{"key":"46_CR20","unstructured":"H. Gabow, J. Bentley and R. Tarjan, Scaling and Related Techniques for Geometry, 16th ACM STOC Symp. (1984), pp. 135\u2013143."},{"key":"46_CR21","unstructured":"R.G. Karlsson, J.I. Munro and E.L. Robertson, The Nearest Neighbor Problem on Bounded Domains The 12-th ICALP Symposium, (1985), pp. 318\u2013327."},{"key":"46_CR22","unstructured":"M. Katz and D. Volper, Data Structures for Retrieval on Square Grids, to appear in SIAM J. on Comp."},{"key":"46_CR23","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1109\/TC.1984.1676388","volume":"33","author":"D.T. Lee","year":"1984","unstructured":"D.T. Lee and F. Preparata, Computational Geometry A Survey, IEEE Trans Comp 33 (1984), pp. 1072\u20131101.","journal-title":"IEEE Trans Comp"},{"key":"46_CR24","first-page":"23","volume":"9","author":"D.T. Lee","year":"1977","unstructured":"D.T. Lee and C.K. Wong, Worst-case analysis of region and partial region searches in multi-dimensional binary search trees and balance quad trees, Acta Informatica 9 (1977), pp. 23\u201329.","journal-title":"Acta Informatica"},{"key":"46_CR25","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1145\/320613.320618","volume":"5","author":"D.T. Lee","year":"1980","unstructured":"D.T. Lee and C.K. Wong, Quintary tree: a file structure for multidimensional database systems, ACM TODS 5 (1980), pp. 339\u2013347.","journal-title":"ACM TODS"},{"key":"46_CR26","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0020-0190(82)90119-3","volume":"15","author":"G.S. Lueker","year":"1982","unstructured":"G.S. Lueker and D.E. Willard, A data structure for dynamic range queries, Inf. Proc. Letters 15 (1982), pp. 209\u2013213.","journal-title":"Inf. Proc. Letters"},{"key":"46_CR27","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, Data Structures and Algorithms (Volume 3), a 12-page summary of [Fr81a]'s formalism appears here; Springer-Verlag, 1984; pp60\u201372.","DOI":"10.1007\/978-3-642-69900-9"},{"key":"46_CR28","unstructured":"M. Overmars, Range Searching on a Grid, Univ. Utrecht, RUU-CS-85-179, 1985."},{"key":"46_CR29","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02241781","volume":"26","author":"M. Overmars","year":"1981","unstructured":"M. Overmars and J v. Leeuvwen, Two General Methods for Dynamizing Decomposable Searching Problems, Computing 26 (1981), pp155\u2013166.","journal-title":"Computing"},{"key":"46_CR30","doi-asserted-by":"crossref","unstructured":"F.P. Preperata and M. I. Shamos, Computational Geometry An Introduction, Springer-Verlag, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"46_CR31","unstructured":"P.M. Vaidya, Space Time Tradeoffs for Orthogonal Range Queries, 17-th ACM STOC (1985), pp. 169\u2013174."},{"key":"46_CR32","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1137\/0211012","volume":"11","author":"D.E. Willard","year":"1982","unstructured":"D.E. Willard, Polygon Retrieval, SIAM J. on Comp. 11(1982), pp. 149\u2013165.","journal-title":"SIAM J. on Comp."},{"key":"46_CR33","first-page":"233","volume":"14","author":"D.E. Willard","year":"1985","unstructured":"__, New data structure for orthogonal range queries, SIAM Journal on Computing, 14(1985), pp. 233\u2013253.","journal-title":"SIAM Journal on Computing"},{"key":"46_CR34","doi-asserted-by":"crossref","unstructured":"_____, Reduced Memory Space for Multi-Dimensional Serach Trees, 2-nd Symposium on Theoretical Aspects of Computer Science (published in Springer-Verlag LNCS182), 1985, pp. 363\u2013374.","DOI":"10.1007\/BFb0024024"},{"key":"46_CR35","unstructured":"_____, On the application of sheared retrieval to orthogonal range queries, published in the Proceedings of the Second ACM Symposium on Computational Geometry, June 1986."},{"key":"46_CR36","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1145\/3828.3839","volume":"32","author":"D.E. Willard","year":"1985","unstructured":"D.E. Willard and G.S. Lueker, Adding range restriction capabiity to dynamic data structures, JACM 32 (1985) pp.597\u2013619.","journal-title":"JACM"},{"key":"46_CR37","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0214022","volume":"14","author":"A.C. Yao","year":"1985","unstructured":"A.C. Yao, On the complexity of maintaining partial sums, SIAM Journal on Computing, 14(1985), pp. 277\u2013289.","journal-title":"SIAM Journal on Computing"}],"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-16761-7_94.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T17:44:31Z","timestamp":1687283071000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16761-7_94"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167617","9783540398592"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-16761-7_94","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}