Dynamic interpolation search revisited
From MaRDI portal
Publication:2288214
DOI10.1016/j.ic.2019.104465zbMath1436.68084OpenAlexW2972161255MaRDI QIDQ2288214
Athanasios K. Tsakalidis, Spyros Sioutas, Christos D. Zaroliagis, Kostas Tsichlas, Alexis C. Kaporis, Christos Makris
Publication date: 17 January 2020
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2019.104465
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A class of algorithms which require nonlinear time to maintain disjoint sets
- Improved behaviour of tries by adaptive branching
- Interpolation-binary search
- A balanced search tree O(1) worst-case update time
- Worst-case optimal insertion and deletion methods for decomposable searching problems
- A new data structure for representing sorted lists
- Preserving order in a forest in less than logarithmic time and linear space
- Understanding the complexity of interpolation search
- An algorithmic and complexity analysis of interpolation search
- Surpassing the information theoretic bound with fusion trees
- An experimental study of compression methods for dynamic tries
- Updating a balanced search tree in 0(1) rotations
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Special issue: Average-case analysis of algorithms
- Time bounded random access machines
- Optimal bounds for the predecessor problem and related problems
- Improved bounds for finger search on a RAM
- Time-space trade-offs for predecessor search
- Dynamic interpolation search
- Tight(er) worst-case bounds on dynamic searching and priority queues
- Dynamic ordered sets with exponential search trees
- Dynamic Interpolation Search Revisited
- Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time
- Implicit Data Structures for the Dictionary Problem
- Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
- Efficiency of a Good But Not Linear Set Union Algorithm
- Design and implementation of an efficient priority queue
- Interpolation search—a log log N search
- On RAM Priority Queues
- Dynamic interpolation search in o(log log n) time
- A Brief History of Generative Models for Power Law and Lognormal Distributions
- A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME
- Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
- The Ubiquitous Digital Tree
- Computability of Recursive Functions
- Algorithms - ESA 2003
