{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T04:30:19Z","timestamp":1778301019893,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540654520","type":"print"},{"value":"9783540492573","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-49257-7_17","type":"book-chapter","created":{"date-parts":[[2007,11,10]],"date-time":"2007-11-10T02:44:59Z","timestamp":1194662699000},"page":"257-276","source":"Crossref","is-referenced-by-count":21,"title":["Optimal Dynamic Range Searching inNon-replicating Index Structures"],"prefix":"10.1007","author":[{"given":"K. V.","family":"Ravi Kanth","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ambuj","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,1,15]]},"reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J. L. Bentley","year":"1975","unstructured":"J. L. Bentley. Multi-dimensional binary search trees used for associative searching. Communications of the ACM, 18:509\u2013517, 1975.","journal-title":"Communications of the ACM"},{"key":"17_CR2","unstructured":"S. Berchtold, D. A. Keim, and H. P. Kriegel. The X-tree: An index structure for high dimensional data. In Proc. Int. Conf. on Very Large Data Bases, pages 28\u201339, 1996."},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. The R* tree: An efficient and robust access method for points and rectangles. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 322\u2013331, May 23\u201325 1990.","DOI":"10.1145\/93597.98741"},{"issue":"2","key":"17_CR4","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. Journal of the ACM, 37(2):200\u2013212, April 1990.","journal-title":"Journal of the ACM"},{"key":"17_CR5","unstructured":"A. A. Diwan, S. Rane, S. Seshadri, and M. Sudarshan. Clustering techniques for minimizing external path length. Proc. Int. Conf. on Very Large Data Bases, pages 342\u2013353, 1996."},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"M. W. Freeston. The BANG file: A new kind of grid file. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 260\u2013269, 1987.","DOI":"10.1145\/38713.38743"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"M. W. Freeston. A general solution of the n-dimensional B-tree problem. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 80\u201392, May 1995.","DOI":"10.1145\/223784.223796"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"R. Grossi and F. Italiano. Efficient splitting and merging algorithms for order-decomposable searching problems. In International Colloquium on Automata, Languages and Programming (ICALP \u201897), pages 605\u2013615, July 1997.","DOI":"10.1007\/3-540-63165-8_215"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 47\u201357, June 1984.","DOI":"10.1145\/602259.602266"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"J. M. Hellerstein, E. Koutsoupias, and C. H. Papadimitriou. On the analysis of indexing schemes. In Proc. ACM Symp. on Principles of Database Systems, pages 249\u2013256, Tucson, Arizona, May 1997.","DOI":"10.1145\/263661.263688"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"N. Katayama and S. Satoh. The SR-tree: An index structure for high-dimensional nearest-neighbor queries. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 369\u2013380, May 1997.","DOI":"10.1145\/253260.253347"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias and D. S. Taylor. Tight bounds for 2-dimensional indexing schemes. In Proc. ACM Symp. on Principles of Database Systems, pages 52\u201358, Seattle, Washington, June 1998.","DOI":"10.1145\/275487.275494"},{"issue":"4","key":"17_CR13","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1145\/99935.99949","volume":"15","author":"D. B. Lomet","year":"1990","unstructured":"D. B. Lomet and B. Salzberg. The hB-tree: A multiattribute indexing method with good guaranteed performance. Proc. ACM Transactions on Database Systems, 15(4):625\u2013658, 1990.","journal-title":"Proc. ACM Transactions on Database Systems"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. Data Structures and Algorithms 3: Multidimensional Searching and Computational Geometry. Springer-Verlag, 1984.","DOI":"10.1007\/978-3-642-69900-9"},{"key":"17_CR15","unstructured":"M. Overmars. The design of dynamic data structures. Lecture Notes in Computer Science 156, 1983."},{"issue":"4","key":"17_CR16","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/0020-0190(81)90093-4","volume":"12","author":"M. Overmars","year":"1981","unstructured":"M. Overmars and J. van Leeuwen. Worst-case optimal insertion and deletion methods for decomposable searching problems. Information Processing Letters, 12(4):168\u2013172, 1981.","journal-title":"Information Processing Letters"},{"key":"17_CR17","volume-title":"Ph.D. thesis","author":"K. V. Ravi Kanth","year":"1998","unstructured":"K. V. Ravi Kanth. Indexing multi-dimensional data. In Ph.D. thesis, University of California, Santa Barbara, April 1998."},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"J. T. Robinson. The kdb-tree: A search structure for large multi-dimensional dynamic indexes. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 10\u201318, 1981.","DOI":"10.1145\/582318.582321"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"H. Samet. The design and analysis of spatial data structures. Addison-Wesley, 1989.","DOI":"10.1007\/3-540-52208-5_28"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"V. Samoladas and D. P. Miranker. A lower bound theorem for indexing schemes and its application to multidimensional range queries. In Proc. ACM Symp. on Principles of Database Systems, pages 44\u201351, Seattle, Washington, June 1998.","DOI":"10.1145\/275487.275493"},{"key":"17_CR21","unstructured":"S. Subramanian and S. Ramaswamy. The P-range tree: A new data structure for range searching in secondary memory. In Proc. ACM-SIAM Symposium on Discrete Algorithms, pages 378\u2013387, 1995."},{"key":"17_CR22","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R. E. Tarjan","year":"1979","unstructured":"R. E. Tarjan. A class of algorithms which require non-linear time to maintain disjoint sets. Journal of Computer and System Sciences, 18:110\u2013127, 1979.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"17_CR23","doi-asserted-by":"publisher","first-page":"748","DOI":"10.1137\/0218051","volume":"18","author":"P. M. Vaidya","year":"1989","unstructured":"P. M. Vaidya. Space-time tradeoffs for orthogonal range queries. SIAM Journal of Computing, 18(4):748\u2013758, 1989.","journal-title":"SIAM Journal of Computing"},{"key":"17_CR24","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1007\/BF01759075","volume":"6","author":"M. Kreveld van","year":"1991","unstructured":"M. van Kreveld and M. Overmars. The divided k-d tree. Algorithmica, 6:840\u2013858, 1991.","journal-title":"Algorithmica"},{"key":"17_CR25","doi-asserted-by":"crossref","unstructured":"D. White and R. Jain. Similarity indexing with the SS-tree. In Proc. Int. Conf. on Data Engineering, pages 516\u2013523, 1996.","DOI":"10.1109\/ICDE.1996.492202"}],"container-title":["Lecture Notes in Computer Science","Database Theory \u2014 ICDT\u201999"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49257-7_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T09:00:15Z","timestamp":1556960415000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49257-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540654520","9783540492573"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-49257-7_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1999]]}}}