{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:47:44Z","timestamp":1758268064423},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540359043"},{"type":"electronic","value":"9783540359050"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_34","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T10:46:45Z","timestamp":1151491605000},"page":"382-394","source":"Crossref","is-referenced-by-count":12,"title":["Dynamic Interpolation Search Revisited"],"prefix":"10.1007","author":[{"given":"Alexis","family":"Kaporis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Makris","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Spyros","family":"Sioutas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Athanasios","family":"Tsakalidis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kostas","family":"Tsichlas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"34_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/3-540-56939-1_58","volume-title":"Automata, Languages and Programming","author":"A. Andersson","year":"1993","unstructured":"Andersson, A., Mattson, C.: Dynamic Interpolation Search in o(loglogn) Time. In: Lingas, A., Carlsson, S., Karlsson, R. (eds.) ICALP 1993. LNCS, vol.\u00a0700, pp. 15\u201327. Springer, Heidelberg (1993)"},{"key":"34_CR2","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1145\/335305.335344","volume-title":"Proc.\u00a032nd ACM Symposium on Theory of Computing \u2013 STOC 2001","author":"A. Anderson","year":"2000","unstructured":"Anderson, A., Thorup, M.: Tight(er) Worst-case Bounds on Dynamic Searching and Priority Queues. In: Proc.\u00a032nd ACM Symposium on Theory of Computing \u2013 STOC 2001, pp. 335\u2013342. ACM Press, New York (2000)"},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0020-0190(80)90139-8","volume":"10","author":"F.W. Burton","year":"1980","unstructured":"Burton, F.W., Lewis, G.N.: A robust variation of Interpolation Search. Information Processing Latters\u00a010, 198\u2013201 (1980)","journal-title":"Information Processing Latters"},{"issue":"1","key":"34_CR4","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P. Beame","year":"2002","unstructured":"Beame, P., Fich, F.: Optimal bounds for the predecessor problem and related problems. Journal of Computer and System Sciences\u00a065(1), 38\u201372 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR5","unstructured":"Demaine, E., Jones, T., Patrascu, M.: Interpolation Search for Non-Independent Data. In: Proc. 15th ACM-SIAM Symp. on Discrete Algorithms \u2013 SODA 2004, pp. 522\u2013523 (2004)"},{"key":"34_CR6","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W. Feller","year":"1971","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, 2nd edn., vol.\u00a0II. Wiley, New York (1971)","edition":"2"},{"key":"34_CR7","unstructured":"Foster, K.E.: A statistically based interpolation binary search. TR, Winthrop College, SC"},{"issue":"1","key":"34_CR8","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1145\/322358.322364","volume":"30","author":"G. Frederickson","year":"1983","unstructured":"Frederickson, G.: Implicit Data Structures for the Dictionary Problem. Journal of the ACM\u00a030(1), 80\u201394 (1983)","journal-title":"Journal of the ACM"},{"key":"34_CR9","unstructured":"Gonnet, G.: Interpolation and Interpolation-Hash Searching. PhD Thesis. Waterloo: University of Waterloo (1977)"},{"key":"34_CR10","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF00288534","volume":"13","author":"G. Gonnet","year":"1980","unstructured":"Gonnet, G., Rogers, L., George, J.: An Algorithmic and Complexity Analysis of Interpolation Search. Acta Informatica\u00a013, 39\u201352 (1980)","journal-title":"Acta Informatica"},{"key":"34_CR11","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"Huddleston, S., Mehlhorn, K.: A new data structure for representing sorted lists. Acta Informatica\u00a017, 157\u2013184 (1982)","journal-title":"Acta Informatica"},{"key":"34_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/3-540-10843-2_34","volume-title":"Automata, Languages and Programming","author":"A. Itai","year":"1981","unstructured":"Itai, A., Konheim, A., Rodeh, M.: A Sparse Table Implementation of Priority Queues. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol.\u00a0115, pp. 417\u2013431. Springer, Heidelberg (1981)"},{"key":"34_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-540-39658-1_31","volume-title":"Algorithms - ESA 2003","author":"A.C. Kaporis","year":"2003","unstructured":"Kaporis, A.C., Makris, C., Sioutas, S., Tsakalidis, A., Tsichlas, K., Zaroliagis, C.: Improved bounds for finger search on a RAM. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 325\u2013336. Springer, Heidelberg (2003)"},{"key":"34_CR14","doi-asserted-by":"crossref","unstructured":"Kaporis, A.C., Makris, C., Sioutas, S., Tsakalidis, A., Tsichlas, K., Zaroliagis, C.: Dynamic Interpolation Search Revisited. Computer Technology Institute Tech.\u00a0Report TR 2006\/04\/02 (April 2006)","DOI":"10.1007\/11786986_34"},{"key":"34_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8590-3","volume-title":"Advanced Database Indexing","author":"Y. Manolopoulos","year":"2000","unstructured":"Manolopoulos, Y., Theodoridis, Y., Tsotras, V.: Advanced Database Indexing. Kluwer Academic Publishers, Dordrecht (2000)"},{"issue":"3","key":"34_CR16","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1145\/174130.174139","volume":"40","author":"K. Mehlhorn","year":"1993","unstructured":"Mehlhorn, K., Tsakalidis, A.: Dynamic Interpolation Search. Journal of the ACM\u00a040(3), 621\u2013634 (1993)","journal-title":"Journal of the ACM"},{"issue":"2","key":"34_CR17","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1080\/15427951.2004.10129088","volume":"1","author":"M. Mitzenmacher","year":"2004","unstructured":"Mitzenmacher, M.: A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics\u00a01(2), 226\u2013251 (2004)","journal-title":"Internet Mathematics"},{"issue":"4","key":"34_CR18","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1109\/12.135562","volume":"41","author":"Y. Perl","year":"1992","unstructured":"Perl, Y., Gabriel, L.: Arithmetic Interpolation Search for Alphabet Tables. IEEE Transactions on Computers\u00a041(4), 493\u2013499 (1992)","journal-title":"IEEE Transactions on Computers"},{"issue":"7","key":"34_CR19","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1145\/359545.359557","volume":"21","author":"Y. Perl","year":"1978","unstructured":"Perl, Y., Itai, A., Avni, H.: Interpolation Search \u2013 A loglogN Search. Communications of the ACM\u00a021(7), 550\u2013554 (1978)","journal-title":"Communications of the ACM"},{"issue":"6","key":"34_CR20","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(77)90072-2","volume":"6","author":"Y. Perl","year":"1977","unstructured":"Perl, Y., Reingold, E.M.: Understanding the Complexity of the Interpolation Search. Information Processing Letters\u00a06(6), 219\u2013222 (1977)","journal-title":"Information Processing Letters"},{"issue":"4","key":"34_CR21","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1147\/rd.12.0130","volume":"1","author":"W.W. Peterson","year":"1957","unstructured":"Peterson, W.W.: Addressing for Random Storage. IBM Journal of Research and Development\u00a01(4), 130\u2013146 (1957)","journal-title":"IBM Journal of Research and Development"},{"key":"34_CR22","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0020-0190(85)90046-8","volume":"20","author":"N. Santorno","year":"1985","unstructured":"Santorno, N., Sidney, J.B.: Interpolation binary search. Information Processing Letters\u00a020, 179\u2013181 (1985)","journal-title":"Information Processing Letters"},{"key":"34_CR23","doi-asserted-by":"crossref","unstructured":"Spencer, J.: Ten Lectures on The Probabilistic Method, 2nd edn. Society for Industrial and Applied Mathematics (1994)","DOI":"10.1137\/1.9781611970074"},{"key":"34_CR24","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters\u00a06, 80\u201382 (1977)","journal-title":"Information Processing Letters"},{"key":"34_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Mathematical Systems Theory\u00a010, 99\u2013127 (1977)","journal-title":"Mathematical Systems Theory"},{"issue":"4","key":"34_CR26","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1137\/0214071","volume":"14","author":"D.E. Willard","year":"1985","unstructured":"Willard, D.E.: Searching Unindexed and Nonuniformly Generated Files in loglogN Time. SIAM Journal of Computing\u00a014(4), 1013\u20131029 (1985)","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"34_CR27","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/S0097539797322425","volume":"29","author":"D.E. Willard","year":"2000","unstructured":"Willard, D.E.: Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree. SIAM Journal on Computing\u00a029(3), 1030\u20131049 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR28","first-page":"173","volume":"1976","author":"A.C. Yao","year":"1976","unstructured":"Yao, A.C., Yao, F.F.: The Complexity of Searching an Ordered Random Table. Proc.\u00a017th IEEE Symp.\u00a0on Foundations of Computer Science \u2013 FOCS 1976\u00a01976, 173\u2013177 (1976)","journal-title":"Proc.\u00a017th IEEE Symp.\u00a0on Foundations of Computer Science \u2013 FOCS 1976"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T23:32:16Z","timestamp":1558308736000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/11786986_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}