A History of Distribution-Sensitive Data Structures

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
A Mathematical Theory of Communication
Self-adjusting binary search trees
Optimal Expected-Case Planar Point Location
Log-logarithmic worst-case range queries are possible in space theta(N)
A priority queue in which initialization and queue operations takeO(loglogD) time
Dynamic ordered sets with exponential search trees
Optimal bounds for the predecessor problem and related problems
Randomized search trees
Optimum binary search trees
Biased Search Trees
Queaps
A unified access bound on comparison-based dynamic dictionaries
Biased skip lists
Optimal finger search trees in the pointer machine
Nearly optimal binary search trees
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
Proximate point searching
A constant update time finger search tree
Algorithms - ESA 2003
Optimal solutions for the temporal precedence problem
Lower Bounds for Accessing Binary Search Trees with Rotations
Dynamic Optimality—Almost
O(log log n)-competitive dynamic binary search trees
Sequential access in splay trees takes linear time
An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times
Key-independent optimality
A Unifying Property for Distribution-Sensitive Priority Queues
A PRIORITY QUEUE WITH THE WORKING-SET PROPERTY
Skip-Splay: Toward Achieving the Unified Bound in the BST Model
Biased range trees
Layered working-set trees
A static optimality transformation with applications to planar point location

Cited In (1)

Belga B-trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848972)