{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T10:15:37Z","timestamp":1743156937754,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662242"},{"type":"electronic","value":"9783540485230"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48523-6_34","type":"book-chapter","created":{"date-parts":[[2007,12,10]],"date-time":"2007-12-10T12:06:31Z","timestamp":1197288391000},"page":"372-381","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Efficient Techniques for Maintaining Multidimensional Keys in Linked Data Structures (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,1,18]]},"reference":[{"key":"34_CR1","first-page":"1259","volume":"3","author":"G.M. Adelson-Velskii","year":"1962","unstructured":"G.M. Adel\u2019son-Vel\u2019skii and E M. Landis. An algorithm for the organization of information. Soviet Mathematics Doklady, 3 (1962), 1259\u20131263.","journal-title":"Soviet Mathematics Doklady"},{"key":"34_CR2","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"S. W. Bent","year":"1985","unstructured":"Samuel W. Bent, Daniel D. Sleator and Robert E. Tarjan. Biased search trees. SIAM Journal on Computing 14 (1985), 545\u2013568.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR3","unstructured":"Jon L. Bentley and Robert Sedgewick. Fast algorithms for sorting and searching strings. In Proc. 8th ACM-SIAM Symp. on Discrete Algorithms (1997), 360\u2013369."},{"key":"34_CR4","unstructured":"Gerth St\u00f8lting Brodal. Finger search trees with constant insertion time. In Proc. 9th ACM-SIAM Symp. on Discrete Algorithms (1998), 540\u2013549."},{"key":"34_CR5","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1137\/0209045","volume":"9","author":"M. R. Brown","year":"1980","unstructured":"Mark R. Brown and Robert E. Tarjan. Design and analysis of a data structure for representing sorted lists. SIAM Journal on Computing 9 (1980), 594\u2013614.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1145\/363958.363987","volume":"7","author":"H. A. Clampett","year":"1964","unstructured":"Henry A. Clampett. Randomized binary searching with the tree structures. Communications of ACM 7 (1964), 163\u2013165.","journal-title":"Communications of ACM"},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"Paul F. Dietz and Daniel D. Sleator. Two algorithms for maintaining order in a list. In Proc. 19th ACM Symp. on Theory of Computing (1987), 365\u2013372.","DOI":"10.1145\/28395.28434"},{"key":"34_CR8","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"J. R. Driscoll","year":"1989","unstructured":"James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. J. of Computer and System Sciences 38 (1989), 86\u2013124.","journal-title":"J. of Computer and System Sciences"},{"key":"34_CR9","unstructured":"Paolo Ferragina and Roberto Grossi. The String B-Tree: A new data structure for string search in external memory and its applications. Journal of ACM, to appear. Preliminary version in Proc. 27th ACM Symp. on Theory of Comp. (1995) 693\u2013702."},{"key":"34_CR10","unstructured":"Teofilo F. Gonzalez. The on-line d-dimensional dictionary problem. In Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms (1992), 376\u2013385."},{"key":"34_CR11","first-page":"375","volume":"33","author":"R. H. Gueting","year":"1980","unstructured":"Ralf H. Gueting and Hans-Peter Kriegel. Multidimensional B-tree: An efficient dynamic file structure for exact match queries. In Proc. 10th GI Conference, Informatik-Fachberichte, Springer, 33 (1980), 375\u2013388.","journal-title":"Proc. 10th GI Conference"},{"key":"34_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"Scott Huddleston and Kurt Mehlhorn. A new data structure for representing sorted lists. Acta Informatica 17 (1982), 157\u2013184.","journal-title":"Acta Informatica"},{"key":"34_CR13","unstructured":"Robert W. Irving. Sufix binary search trees. Research Report, Department of Computer Science, University of Glasgow, April 1997."},{"key":"34_CR14","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF00299635","volume":"26","author":"C. Levcopoulos","year":"1988","unstructured":"Christos Levcopoulos and Mark H. Overmars. A balanced search tree with O(1) worst-case update time. Acta Informatica 26 (1988), 269\u2013277.","journal-title":"Acta Informatica"},{"key":"34_CR15","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Udi Manber and Eugene W. Myers. Sufix arrays: A new method for on-line string searches. SIAM Journal on Computing 22 (1993), 935\u2013948.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR16","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1137\/0208014","volume":"8","author":"K. Mehlhorn","year":"1979","unstructured":"Kurt Mehlhorn. Dynamic binary search. SIAM J. on Computing 8 (1979), 175\u2013198.","journal-title":"SIAM J. on Computing"},{"key":"34_CR17","doi-asserted-by":"crossref","unstructured":"Kurt Mehlhorn. Data structures and algorithms: 1. Searching and sorting, Springer, (1984).","DOI":"10.1007\/978-3-642-69672-5"},{"key":"34_CR18","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J. Nievergelt","year":"1973","unstructured":"J\u00fcrg Nievergelt and Edward M. Reingold. Binary search trees of bounded balance. SIAM Journal on Computing 2 (1973), 33\u201343.","journal-title":"SIAM Journal on Computing"},{"key":"34_CR19","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/BF01940876","volume":"16","author":"R. Seidel","year":"1996","unstructured":"Raimund Seidel and Cecilia R. Aragon. Randomized search trees. Algorithmica 16 (1996), 464\u2013497.","journal-title":"Algorithmica"},{"key":"34_CR20","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D. D. Sleator","year":"1985","unstructured":"Daniel D. Sleator and Robert E. Tarjan. Self-adjusting binary search trees. Journal of ACM 32 (1985), 652\u2013686.","journal-title":"Journal of ACM"},{"key":"34_CR21","doi-asserted-by":"crossref","unstructured":"Robert E. Tarjan. Data structures and network algorithms, CBMS-NSF Reg. Conf. Ser. Appl. Math. 44, SIAM (1983).","DOI":"10.1137\/1.9781611970265"},{"key":"34_CR22","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1109\/TC.1984.1676438","volume":"C-33","author":"V. K. Vaishnavi","year":"1984","unstructured":"Vijay K. Vaishnavi. Multidimensional height-balanced trees. IEEE Transactions on Computers C-33 (1984), 334\u2013343.","journal-title":"IEEE Transactions on Computers"},{"key":"34_CR23","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1109\/12.30849","volume":"C-38","author":"V. K. Vaishnavi","year":"1989","unstructured":"Vijay K. Vaishnavi. Multidimensional balanced binary trees. IEEE Transactions on Computers C-38 (1989), 968\u2013985.","journal-title":"IEEE Transactions on Computers"},{"key":"34_CR24","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1006\/jcss.1996.0025","volume":"52","author":"V. K. Vaishnavi","year":"1996","unstructured":"Vijay K. Vaishnavi. On k-dimensional balanced binary trees. Journal of Computer and System Sciences 52 (1996), 328\u2013348.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48523-6_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T03:07:41Z","timestamp":1642820861000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-48523-6_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662242","9783540485230"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-48523-6_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"18 January 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}