A History of Distribution-Sensitive Data Structures
From MaRDI portal
Publication:2848972
DOI10.1007/978-3-642-40273-9_10zbMath1394.68090MaRDI QIDQ2848972
Prosenjit Bose, Pat Morin, John Howat
Publication date: 13 September 2013
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-40273-9_10
68P05: Data structures
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Mathematical Theory of Communication
- Proximate point searching
- Sequential access in splay trees takes linear time
- Nearly optimal binary search trees
- A constant update time finger search tree
- Key-independent optimality
- Biased skip lists
- Queaps
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Optimal solutions for the temporal precedence problem
- Optimal bounds for the predecessor problem and related problems
- Randomized search trees
- A unified access bound on comparison-based dynamic dictionaries
- Biased range trees
- Layered working-set trees
- Optimum binary search trees
- A Unifying Property for Distribution-Sensitive Priority Queues
- Skip-Splay: Toward Achieving the Unified Bound in the BST Model
- A PRIORITY QUEUE WITH THE WORKING-SET PROPERTY
- Dynamic ordered sets with exponential search trees
- An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times
- O(log log n)-competitive dynamic binary search trees
- A priority queue in which initialization and queue operations takeO(loglogD) time
- Biased Search Trees
- Self-adjusting binary search trees
- Lower Bounds for Accessing Binary Search Trees with Rotations
- A Best Possible Bound for The Weighted Path Length of Binary Search Trees
- On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences
- On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
- Proximate planar point location
- Optimal Expected-Case Planar Point Location
- A static optimality transformation with applications to planar point location
- Dynamic Optimality—Almost
- Algorithms - ESA 2003
- Optimal finger search trees in the pointer machine
