A History of Distribution-Sensitive Data Structures

DOI10.1007/978-3-642-40273-9_10zbMath1394.68090OpenAlexW29684811MaRDI 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

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (1)

Belga B-trees

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

This page was built for publication: A History of Distribution-Sensitive Data Structures