{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:37Z","timestamp":1760202637268},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540569398"},{"type":"electronic","value":"9783540478263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56939-1_58","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:55:08Z","timestamp":1330257308000},"page":"15-27","source":"Crossref","is-referenced-by-count":15,"title":["Dynamic interpolation search in o(log log n) time"],"prefix":"10.1007","author":[{"given":"Arne","family":"Andersson","sequence":"first","affiliation":[]},{"given":"Christer","family":"Mattsson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"L. Devroye. Lecture Notes on Bucket Algorithms. Birkh\u00e4user, 1985. ISBN 0-8176-3328-6.","DOI":"10.1016\/0196-6774(85)90015-X"},{"issue":"1","key":"2_CR2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1145\/322358.322364","volume":"30","author":"G. Frederickson","year":"1983","unstructured":"G. Frederickson. Implicit Data Structures for the Dictionary Problem. Journal of the ACM, 30(1):80\u201394, 1983.","journal-title":"Journal of the ACM"},{"key":"2_CR3","unstructured":"G. H. Gonnet. Interpolation and Interplation Hash Searching. PhD thesis, University of Waterloo, February 1977."},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"A. Itai, A.G. Konheim, and M. Rodeh. A sparse table implementation of priority queues. In Proc. 8th ICALP, pages 417\u2013431, 1981.","DOI":"10.1007\/3-540-10843-2_34"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn and A. Tsakalidis. Dynamic interpolation search. In Proc. 12th ICALP, 1985.","DOI":"10.1007\/BFb0015768"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn and A. Tsakalidis. Dynamic interpolation search. To appear in Journal of the ACM, 1993.","DOI":"10.1145\/174130.174139"},{"key":"2_CR7","unstructured":"M. H. Overmars. The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science. Springer Verlag, 1983. ISBN 3-540-12330-X."},{"key":"2_CR8","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF00299635","volume":"26","author":"M. H. Overmars","year":"1988","unstructured":"M. H. Overmars and C. Levcopoulos. A balanced search tree with O(1) worst-case update time. Acta Informatica, 26:269\u2013277, 1988.","journal-title":"Acta Informatica"},{"issue":"6","key":"2_CR9","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0020-0190(77)90072-2","volume":"6","author":"Y. Perl","year":"1977","unstructured":"Y. Perl and E. M. Reingold. Understanding the Complexity of Interpolation Search. Information Processing Letters, 6(6):219\u2013222, December 1977.","journal-title":"Information Processing Letters"},{"issue":"4","key":"2_CR10","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1147\/rd.12.0130","volume":"1","author":"W. W. Peterson","year":"1957","unstructured":"W. W. Peterson. Addressing for Random-Access Storage. IBM J. Res. Development, 1 (4):130\u2013146, April 1957.","journal-title":"IBM J. Res. Development"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"D. E. Willard. Searching Unindexed and Nonuniformly Generated Files in log log N Time. SIAM Journal on Computing, 14(4), 1985.","DOI":"10.1137\/0214071"},{"key":"2_CR12","first-page":"173","volume-title":"The Complexity of Searching an Ordered Random Table","author":"A. C. Yao","year":"1976","unstructured":"A. C. Yao and F. F. Yao. The Complexity of Searching an Ordered Random Table. In Proceeding Seventeenth Annual Symposium on Foundations of Computer Science, pages 173\u2013177, HOUSTON TX, October 1976. IEEE."}],"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-56939-1_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:07:27Z","timestamp":1605647247000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56939-1_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569398","9783540478263"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-56939-1_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}