Dynamic interpolation search in o(log log n) time

DOI10.1007/3-540-56939-1_58zbMath1418.68071OpenAlexW1552004844WikidataQ56096170 ScholiaQ56096170MaRDI QIDQ4630245

No author found.

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_58

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05)

Related Items

ISB-tree: A new indexing scheme with efficient expected behaviour ⋮ Dynamic 3-sided planar range queries with expected doubly-logarithmic time ⋮ Adaptive search over sorted sets ⋮ Dynamic interpolation search revisited

Cites Work

• Unnamed Item
• The design of dynamic data structures
• A balanced search tree O(1) worst-case update time
• Understanding the complexity of interpolation search
• Dynamic interpolation search
• Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time
• Implicit Data Structures for the Dictionary Problem