Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time

DOI10.1137/0214071zbMath0575.68061OpenAlexW2058379611MaRDI QIDQ3694705

Dan E. Willard

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0214071

zbMATH Keywords

priority queuestratified treebinary searchregula falsiinterpolation searchdense sequential filefast trienonuniformly distributed ordered filespadded listVan Emde Boas tree

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items

ISB-tree: A new indexing scheme with efficient expected behaviour, Improved bounds for finger search on a RAM, Dynamic interpolation search in o(log log n) time, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, Analysis of recursive batched interpolation search, Dynamic interpolation search revisited, Some Results for Elementary Operations, Batched interpolation searching on databases, Log-logarithmic worst-case range queries are possible in space theta(N), New trie data structures which support very fast search operations, Robust variations of interpolation search: An asymptotic analysis, Optimal bounds for the predecessor problem and related problems