{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:35Z","timestamp":1787340575563,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,11]]},"abstract":"<jats:p>The first algorithm that searches unindexed and nonuniformly distributed ordered files in $\\log \\log N$ expected time is presented in this paper. Our analysis rests on a synthesis of concepts from the literature on interpolation search and on the method of regula falsi in numerical analysis.<\/jats:p>","DOI":"10.1137\/0214071","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"1013-1029","source":"Crossref","is-referenced-by-count":29,"title":["Searching Unindexed and Nonuniformly Generated Files in $\\log \\log N$ Time"],"prefix":"10.1137","volume":"14","author":[{"given":"Dan E.","family":"Willard","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RAFK-83","doi-asserted-by":"crossref","unstructured":"M. Atjai, M. Fredman, J. Komlos,  Hash functions for priority queues,  Proc. 24th IEEE Symposium on Foundations of Computer Science,  1983,  299\u2013303","DOI":"10.1109\/SFCS.1983.24"},{"key":"RDE-79","unstructured":"L. Devroye,  Average time behavior of distributive sorting algorithms, Tech. Rep., SOCS 79.4,  1979"},{"key":"RES-74","unstructured":"P. Erdos, J. Spencer, Probabilistic methods in combinatorics, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974, 106\u201352:2895"},{"key":"RFE-68","volume-title":"An introduction to probability theory and its applications. Vol. I","author":"Feller William","year":"1968"},{"key":"RFKS-82","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.39"},{"key":"RFR-79","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90060-7"},{"key":"RGRG-80","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288534"},{"key":"RHKW-85","doi-asserted-by":"publisher","DOI":"10.1137\/0216069"},{"key":"RIKR-80","doi-asserted-by":"crossref","unstructured":"A. Itai, A. Konheim, M. Rodeh,  A sparse table implementation of priority queues, IBM Tech. Rep., RC 8550 (#37269),  1980, Nov., Extended abstract appeared at ICALP-1981","DOI":"10.1007\/3-540-10843-2_34"},{"key":"RJO-81","doi-asserted-by":"crossref","unstructured":"D. Johnson,  A priority queue in which initialization and queue operations take  O(loglogD) time, Rept., CS 81-13, Pennsylvania State Univ., University Park, PA,  1981","DOI":"10.1007\/BF01786986"},{"key":"RKN-73","volume-title":"The art of computer programming. Volume 3","author":"Knuth D.","year":"1973"},{"key":"RKS-77","volume-title":"The advanced theory of statistics. Vol. 1","author":"Kendall Maurice","year":"1977"},{"key":"RMT-84","unstructured":"K. Mehlhorn, A. Tsakalidis,  Dynamic interpolation search, 84-05, Univ. des Saarlandes,  1984"},{"key":"RMG-80","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90132-5"},{"key":"RPIA-78","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359557"},{"key":"RPR-77","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90072-2"},{"key":"RRR-78","unstructured":"Anthony Ralston, Philip Rabinowitz, A first course in numerical analysis, McGraw-Hill Book Co., New York, 1978, 338\u2013344, Second ed.58:135990408.65001"},{"key":"RRW-84","unstructured":"J. Reif, D. Willard,  Parallel interpolation search, Inform. and Control, submitted for publication"},{"key":"RTY-79","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359175"},{"key":"RVA-75","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.26"},{"key":"RVA-77","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"RVKZ-77","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683268"},{"key":"RWI-81","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5798-1_1"},{"key":"RWI-82","doi-asserted-by":"crossref","unstructured":"D. Willard,  Maintaining dense sequential files in a dynamic environment,  extended abstract at the 14th ACM Symposium on Theory of Computing,  114\u2013122, full-length version invited paper to appear in Inform. and Control","DOI":"10.1145\/800070.802183"},{"key":"RWI-83A","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90075-3"},{"key":"RWI-83B","first-page":"656","volume-title":"Twenty-first annual Allerton conference on communication, control, and computing (Monticello, Ill., 1983)","author":"Willard D.","year":"1983"},{"key":"RWI-84A","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90020-5"},{"key":"RWI-84B","doi-asserted-by":"crossref","unstructured":"D. Willard,  Log-logarithmic protocols for ethernet and semaphore-like problems,  Proc.16th ACM Symposium on Theory of Computing,  1984,  512\u2013521","DOI":"10.1145\/800057.808721"},{"key":"RWI-84C","doi-asserted-by":"crossref","unstructured":"D. Willard,  Sampling algorithms for differentiable batch retrieval problems,  Proc. 11th International Conference on Automata, Languages and Programming (ICALP),  1984,  514\u2013526","DOI":"10.1007\/3-540-13345-3_48"},{"key":"RYA-82","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"},{"key":"RYY-76","doi-asserted-by":"crossref","unstructured":"Andrew C. Yao, F. Frances Yao,  The complexity of searching an ordered random table (extended abstract),  17th Annual Symposium on Foundations of Computer Science (Houston, Tex., 1976), IEEE Comput. Soc., Long Beach, Calif.,  1976,  173\u2013177 56:7323","DOI":"10.1109\/SFCS.1976.32"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214071","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:11Z","timestamp":1787337611000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,11]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1985,11]]}},"alternative-id":["10.1137\/0214071"],"URL":"https:\/\/doi.org\/10.1137\/0214071","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,11]]}}}