{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T18:27:38Z","timestamp":1791052058834,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540405351","type":"print"},{"value":"9783540450726","type":"electronic"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45072-6_4","type":"book-chapter","created":{"date-parts":[[2011,1,8]],"date-time":"2011-01-08T08:23:33Z","timestamp":1294475013000},"page":"46-65","source":"Crossref","is-referenced-by-count":69,"title":["Bkd-Tree: A Dynamic Scalable kd-Tree"],"prefix":"10.1007","author":[{"given":"Octavian","family":"Procopiuc","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pankaj K.","family":"Agarwal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lars","family":"Arge","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Arge, L., Procopiuc, O., Vitter, J.S.: A framework for index bulk loading and dynamization. In: Proc. Intl. Colloq. Automata, Languages and Programming, pp. 115\u2013127 (2001)","DOI":"10.1007\/3-540-48224-5_10"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The Input\/Output complexity of sorting and related problems. Commun. ACM\u00a031, 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/978-1-4615-0005-6_9","volume-title":"Handbook of Massive Data Sets","author":"L. Arge","year":"2002","unstructured":"Arge, L.: External memory data structures. In: Abello, J., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Massive Data Sets, pp. 313\u2013358. Kluwer, Dordrecht (2002)"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Arge, L., Procopiuc, O., Vitter, J.S.: Implementing I\/O-efficient data structures using TPIE. In: Proc. European Symp. on Algorithms, pp. 88\u2013100 (2002)","DOI":"10.1007\/3-540-45749-6_12"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Arge, L., Samoladas, V., Vitter, J.S.: On two-dimensional indexability and optimal range search indexing. In: Proc. ACM Symp. Principles of Database Systems, vol.\u00a047, pp. 346\u2013357 (1999)","DOI":"10.1145\/303976.304010"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R*-tree: An efficient and robust access method for points and rectangles. In: Proc. SIGMOD Intl. Conf. on Management of Data, pp. 322\u2013331 (1990)","DOI":"10.1145\/93597.98741"},{"issue":"9","key":"4_CR7","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J.L. Bentley","year":"1975","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM\u00a018(9), 509\u2013517 (1975)","journal-title":"Commun. ACM"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J.L. Bentley","year":"1979","unstructured":"Bentley, J.L.: Decomposable searching problems. Inform. Process. Lett.\u00a08, 244\u2013251 (1979)","journal-title":"Inform. Process. Lett."},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/BFb0100987","volume-title":"Advances in Database Technology - EDBT \u201998","author":"S. Berchtold","year":"1998","unstructured":"Berchtold, S., B\u00f6hm, C., Kriegel, H.-P.: Improving the query performance of high-dimensional index structures by bulk load operations. In: Schek, H.-J., Saltor, F., Ramos, I., Alonso, G. (eds.) EDBT 1998. LNCS, vol.\u00a01377, pp. 216\u2013230. Springer, Heidelberg (1998)"},{"key":"4_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s007780050030","volume":"6","author":"G. Evangelidis","year":"1997","unstructured":"Evangelidis, G., Lomet, D., Salzberg, B.: The hB\u03a0-tree: A multi-attribute index supporting concurrency, recovery and node consolidation. The VLDB Journal\u00a06, 1\u201325 (1997)","journal-title":"The VLDB Journal"},{"issue":"2","key":"4_CR11","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1145\/280277.280279","volume":"30","author":"V. Gaede","year":"1998","unstructured":"Gaede, V., G\u00fcnther, O.: Multidimensional access methods. ACM Computing Surveys\u00a030(2), 170\u2013231 (1998)","journal-title":"ACM Computing Surveys"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Grossi, R., Italiano, G.F.: Efficient cross-tree for external memory. In: Abello, J., Vitter, J.S. (eds.) External Memory Algorithms and Visualization, pp. 87\u2013106. American Mathematical Society, Providence (1999), Revised version available at \n                      ftp:\/\/ftp.di.unipi.it\/pub\/techreports\/TR-00-16.ps.Z","DOI":"10.1090\/dimacs\/050\/04"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Guttman, A.: R-trees: A dynamic index structure for spatial searching. In: Proc. SIGMOD Intl. Conf. on Management of Data, pp. 47\u201357 (1984)","DOI":"10.1145\/971697.602266"},{"key":"4_CR14","unstructured":"Jagadish, H.V., Narayan, P.P.S., Seshadri, S., Sudarshan, S., Kanneganti, R.: Incremental organization for data recording and warehousing. In: Proc. Intl. Conf. on Very Large Data Bases, pp. 16\u201325 (1997)"},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/3-540-49257-7_17","volume-title":"Database Theory - ICDT\u201999","author":"K.V.R. Kanth","year":"1998","unstructured":"Kanth, K.V.R., Singh, A.K.: Optimal dynamic range searching in nonreplicating index structures. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, pp. 257\u2013276. Springer, Heidelberg (1998)"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF00263763","volume":"9","author":"D.T. Lee","year":"1977","unstructured":"Lee, D.T., Wong, C.K.: Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees. Acta Informatica\u00a09, 23\u201329 (1977)","journal-title":"Acta Informatica"},{"issue":"3","key":"4_CR17","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/290593.290598","volume":"27","author":"D. Lomet","year":"1998","unstructured":"Lomet, D.: B-tree page size when caching is considered. SIGMOD Record\u00a027(3), 28\u201332 (1998)","journal-title":"SIGMOD Record"},{"issue":"4","key":"4_CR18","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1145\/99935.99949","volume":"15","author":"D.B. Lomet","year":"1990","unstructured":"Lomet, D.B., Salzberg, B.: The hB-Tree: A multiattribute indexing method with good guaranteed performance. ACM Trans. on Database Systems\u00a015(4), 625\u2013658 (1990)","journal-title":"ACM Trans. on Database Systems"},{"issue":"1","key":"4_CR19","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/348.318586","volume":"9","author":"J. Nievergelt","year":"1984","unstructured":"Nievergelt, J., Hinterberger, H., Sevcik, K.C.: The grid file: An adaptable, symmetric multikey file structure. ACM Trans. on Database Systems\u00a09(1), 38\u201371 (1984)","journal-title":"ACM Trans. on Database Systems"},{"issue":"4","key":"4_CR20","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/s002360050048","volume":"33","author":"P.E. O\u2019Neil","year":"1996","unstructured":"O\u2019Neil, P.E., Cheng, E., Gawlick, D., O\u2019Neil, E.J.: The log-structured mergetree (LSM-tree). Acta Informatica, 33(4):351\u2013385 (1996)","journal-title":"Acta Informatica"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","volume-title":"The Design of Dynamic Data Structures","author":"M. Overmars","year":"1983","unstructured":"Overmars, M.: The Design of Dynamic Data Structures. LNCS, vol.\u00a0156. Springer, Heidelberg (1983)"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Robinson, T.: The K-D-B-tree: A search structure for large multidimensional dynamic indexes. In: Proc. SIGMOD Intl. Conf. on Management of Data, pp. 10\u201318 (1981)","DOI":"10.1145\/582318.582321"},{"key":"4_CR23","volume-title":"The design and analysis of spatial data structures","author":"H. Samet","year":"1990","unstructured":"Samet, H.: The design and analysis of spatial data structures. Addison-Wesley, Reading (1990)"},{"key":"4_CR24","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(79)90110-8","volume":"8","author":"Y.V. Silva Filho","year":"1979","unstructured":"Silva Filho, Y.V.: Average case analysis of region search in balanced k-d trees. Inform. Process. Lett.\u00a08, 219\u2013223 (1979)","journal-title":"Inform. Process. Lett."},{"key":"4_CR25","unstructured":"TIGER\/Line Files, 1997 Technical Documentation. U.S. Census Bureau (1998), \n                      http:\/\/www.census.gov\/geo\/tiger\/TIGER97D.pdf"}],"container-title":["Lecture Notes in Computer Science","Advances in Spatial and Temporal Databases"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45072-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T14:21:43Z","timestamp":1778250103000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-45072-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405351","9783540450726"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45072-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}