Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time
From MaRDI portal
Publication:3694705
DOI10.1137/0214071zbMath0575.68061MaRDI QIDQ3694705
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
priority queue; stratified tree; binary search; regula falsi; interpolation search; dense sequential file; fast trie; nonuniformly distributed ordered files; padded list; Van Emde Boas tree
68P10: Searching and sorting
Related Items
Analysis of recursive batched interpolation search, ISB-tree: A new indexing scheme with efficient expected behaviour, New trie data structures which support very fast search operations, Robust variations of interpolation search: An asymptotic analysis, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, Batched interpolation searching on databases, Log-logarithmic worst-case range queries are possible in space theta(N), Optimal bounds for the predecessor problem and related problems, Improved bounds for finger search on a RAM, Some Results for Elementary Operations