{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:47:42Z","timestamp":1725662862473},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540108283"},{"type":"electronic","value":"9783540387169"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10828-9_53","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:26:18Z","timestamp":1330190778000},"page":"35-45","source":"Crossref","is-referenced-by-count":5,"title":["Trees as data and file structures"],"prefix":"10.1007","author":[{"given":"J.","family":"Nievergelt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"3_CR1","unstructured":"Aho, A. V., Hopcroft, J. E. and Ullman, J. D. The design and analysis of computer algorithms, Addison-Wesley, 1974."},{"key":"3_CR2","first-page":"263","volume":"146","author":"G. M. Adelson-Velskii","year":"1962","unstructured":"Adelson-Velskii, G. M. and Landis, Ye. M. An algorithm for the organization of information (in Russian), Dokl. Akad. Nauk SSSR, Vol 146, 263\u2013266, 1962.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"3_CR3","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1093\/comjnl\/18.2.135","volume":"18","author":"O. Amble","year":"1975","unstructured":"Amble, O. and Knuth, D. E. Ordered hash tables, Computer J., Vol 18, 135\u2013142, 1975.","journal-title":"Computer J."},{"issue":"5","key":"3_CR4","doi-asserted-by":"crossref","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. Proc. Letters, Vol 8, No 5, 244\u2013251, 1979.","journal-title":"Inform. Proc. Letters"},{"issue":"4","key":"3_CR5","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1109\/TSE.1979.234200","volume":"5","author":"J. L. Bentley","year":"1979","unstructured":"Bentley, J. L. Multidimensional binary search trees in database applications IEEE Trans. Software Engr., Vol 5, No 4, 333\u2013340, July 1979.","journal-title":"IEEE Trans. Software Engr."},{"key":"3_CR6","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R. and McCreight, E. M. Organization and maintenance of large ordered indexes, Acta Informatica, Vol 1, 173\u2013189, 1972.","journal-title":"Acta Informatica"},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00263762","volume":"9","author":"R. Bayer","year":"1977","unstructured":"Bayer, R. and Schkolnick, M. Concurrency of operations on B-trees, Acta Informatica, Vol 9, 1\u201321, 1977.","journal-title":"Acta Informatica"},{"key":"3_CR8","unstructured":"Blum, N. and Mehlhorn, K. On the average number of rebalancing operations in weight-balanced trees, Theor. Comp. Sci, 1978."},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Carter, J. L. and Wegman, M. Universal classes of hash functions, Report RC 6687, IBM Yorktown Heights, 1977.","DOI":"10.1145\/800105.803400"},{"issue":"1","key":"3_CR10","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/358808.358813","volume":"23","author":"R. J. Cichelli","year":"1980","unstructured":"Cichelli, R. J. Minimal perfect hash functions made simple, Comm. ACM, Vol 23, No 1, 17\u201319, Jan 1980.","journal-title":"Comm. ACM"},{"issue":"2","key":"3_CR11","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D. Comer","year":"1979","unstructured":"Comer, D. The ubiquitous B-tree, ACM Computing Surveys, Vol 11, No 2, 121\u2013138, June 1979.","journal-title":"ACM Computing Surveys"},{"key":"3_CR12","unstructured":"Edelsbrunner, H. and van Leeuwen, J. Multidimensional algorithms and data structures (Bibliography) Bulletin of the EATCS, 1980."},{"issue":"3","key":"3_CR13","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/320083.320092","volume":"4","author":"R. Fagin","year":"1979","unstructured":"Fagin, R., Nievergelt, J., Pippenger, N., and Strong, H. R., Extendible hashing \u2014 a fast access method for dynamic files, ACM Trans. Database Systems, Vol 4, No 3, 315\u2013344, Sep 1979.","journal-title":"ACM Trans. Database Systems"},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E. Fredkin","year":"1960","unstructured":"Fredkin, E. Trie memory, Comm. ACM, Vol 3, 490\u2013500, 1960.","journal-title":"Comm. ACM"},{"key":"3_CR15","unstructured":"Goldstine, H. H. and von Neumann, J. Planning and coding of problems for an electronic computing instrument, Part II, Vol 1, 1947; reprinted in A. H. Taub (ed.), \u201cJohn von Neumann \u2014 Collected Works\u201c, Vol 5, Pergamon Press, 1963."},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Guibas, L. and Sedgewick, R. A dichromatic framework for balanced trees, Proc. 19-th Annual Symp. Found. of Computer Sci., 8\u201321, IEEE, 1978.","DOI":"10.1109\/SFCS.1978.3"},{"key":"3_CR17","unstructured":"Hinterberger, H. and Nievergelt, J., Concurrent access control in extendible hash files, (submitted)"},{"key":"3_CR18","unstructured":"Knuth, D. E. The art of computer programming, Addison-Wesley, Vol 1, Fundamental Algorithms, 1968, Vol 3, Sorting and Searching, 1973."},{"issue":"3","key":"3_CR19","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1145\/320613.320619","volume":"5","author":"H. T. Kung","year":"1980","unstructured":"Kung, H. T. and Lehman, P. L. Concurrent manipulation of binary search trees, ACM Trans. Database Sys, Vol 5, No 3, 354\u2013382, Sep 1980.","journal-title":"ACM Trans. Database Sys"},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/BF01931695","volume":"18","author":"P. Larson","year":"1978","unstructured":"Larson, P. Dynamic hashing, BIT, Vol 18, 184\u2013201, 1978.","journal-title":"BIT"},{"key":"3_CR21","unstructured":"Larson, P. Linear hashing with partial expansions, Proc. 6-th Conf. on Very Large Databases, Montreal, Oct 1980."},{"key":"3_CR22","unstructured":"van Leeuwen, J. and Maurer, H. A. Dynamic systems of static data structures, Univ. Graz, Institut Informationsver. Report 42, Jan 1980."},{"key":"3_CR23","unstructured":"Litwin, W. Virtual hashing: a dynamically changing hashing, Proc. 4-th Conf. Very Large Databases, Berlin, 1978, 517\u2013523."},{"key":"3_CR24","unstructured":"Litwin, W. Linear hashing: a new tool for file and table addressing, Proc. 6-th Conf. on Very Large Databases, Montreal, Oct 1980."},{"key":"3_CR25","unstructured":"McCreight, E. M. Efficient algorithms for enumerating intersecting intervals and rectangles, XEROX PARC Report CSL-80-9, 1980."},{"key":"3_CR26","unstructured":"Mehlhorn, K. Arbitrary weight changes in dynamic trees, RAIRO, Th CS"},{"key":"3_CR27","unstructured":"Mehlhorn, K. Lower bounds on the efficiency of static to dynamic transforms of data structures, Univ. Saarland Report 1980."},{"issue":"1","key":"3_CR28","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J. Nievergelt","year":"1973","unstructured":"Nievergelt, J. and Reingold, E. M. Binary search trees of bounded balance, SIAM J. Computing, Vol 2, No 1, 33\u201343, Mar 1973.","journal-title":"SIAM J. Computing"},{"issue":"3","key":"3_CR29","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1145\/356631.356634","volume":"6","author":"J. Nievergelt","year":"1974","unstructured":"Nievergelt, J. Binary search trees and file organization, ACM Computing Surveys, Vol 6, No 3, 195\u2013207, Sep 1974.","journal-title":"ACM Computing Surveys"},{"key":"3_CR30","unstructured":"Nievergelt, J., Seveik, K. and Hinterberger, H. The grid file: a dynamic multikey access structure, (in preparation)"},{"issue":"3","key":"3_CR31","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1109\/TIT.1956.1056797","volume":"IT-2","author":"A. Newell","year":"1956","unstructured":"Newell, A. and Simon, H. A. The logic theory machine \u2014 A complex information processing system, IRE Trans. Information Theory, Vol. IT-2, No 3, 61\u201379, Sep 1956.","journal-title":"IRE Trans. Information Theory"},{"key":"3_CR32","unstructured":"Olivie', H. J. Half-balanced binary search trees, Report 81-01, IHAM, B-2000 Antwerp, 1981."},{"key":"3_CR33","unstructured":"Rosenberg, A. L. Storage mappings for extendible arrays, in R. T. Yeh (ed.), Current Trends in Programming Methodology, Vol IV: Data Structuring, Ch 10, Prentice-Hall 1978."},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"Saxe, J. B. and Bentley, J. L. Transforming static data structures to dynamic structures, 20-th IEEE Symp. Foundations of Computer Scsi., 148\u2013168, 1979.","DOI":"10.1109\/SFCS.1979.47"},{"issue":"11","key":"3_CR35","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1145\/359863.359887","volume":"20","author":"R. Sprugnoli","year":"1977","unstructured":"Sprugnoli, R. Perfect hashing functions: a single probe retrieving method for static sets, Comm. ACM, Vol 20, No 11, 841\u2013850, Nov 1977.","journal-title":"Comm. ACM"},{"issue":"11","key":"3_CR36","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1145\/359168.359175","volume":"22","author":"R. E. Tarjan","year":"1979","unstructured":"Tarjan, R. E. and Yao, A. C.-C. Storing a sparse table, Comm. ACM, Vol 22, No 11, 606\u2013611, Nov 1979.","journal-title":"Comm. ACM"},{"key":"3_CR37","unstructured":"Warnock, J. E. A hidden-surface algorithm for computer generated half-tone pictures, Univ. Utah, Dept. Computer Sci. TR 4\u201315, 1969."},{"key":"3_CR38","unstructured":"Willard, D. E. Balanced forests of h-d trees as a dynamic data structure, Harvard Univ., Aiken Computer Lab Report TR-23, 1978."}],"container-title":["Lecture Notes in Computer Science","CAAP '81"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10828-9_53.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:03:27Z","timestamp":1605643407000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10828-9_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540108283","9783540387169"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/3-540-10828-9_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}