A history of distribution-sensitive data structures

DOI10.1007/978-3-642-40273-9_10MaRDI QIDQ2848972zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, John Howat, Pat Morin

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)

Recommendations

• A Distribution-Sensitive Dictionary with Low Space Overhead
• A distribution-sensitive dictionary with low space overhead
• Distribution-sensitive algorithms
• scientific article; zbMATH DE number 1383711

Cites work

• scientific article; zbMATH DE number 1617246 (Why is no real title available?)
• scientific article; zbMATH DE number 5764827 (Why is no real title available?)
• scientific article; zbMATH DE number 5764838 (Why is no real title available?)
• scientific article; zbMATH DE number 3607502 (Why is no real title available?)
• scientific article; zbMATH DE number 6321467 (Why is no real title available?)
• O(log log n)-competitive dynamic binary search trees
• A Best Possible Bound for The Weighted Path Length of Binary Search Trees
• A Mathematical Theory of Communication
• A PRIORITY QUEUE WITH THE WORKING-SET PROPERTY
• A constant update time finger search tree
• A priority queue in which initialization and queue operations takeO(loglogD) time
• A static optimality transformation with applications to planar point location
• A unified access bound on comparison-based dynamic dictionaries
• A unifying property for distribution-sensitive priority queues
• An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times
• Biased Search Trees
• Biased range trees
• Biased skip lists
• Dynamic Optimality—Almost
• Dynamic ordered sets with exponential search trees
• Improved bounds for finger search on a RAM
• Key-independent optimality
• Layered working-set trees
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Lower Bounds for Accessing Binary Search Trees with Rotations
• Nearly optimal 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
• Optimal Expected-Case Planar Point Location
• Optimal bounds for the predecessor problem and related problems
• Optimal finger search trees in the pointer machine
• Optimal solutions for the temporal precedence problem
• Optimum binary search trees
• Proximate planar point location
• Proximate point searching
• Queaps
• Randomized search trees
• Self-adjusting binary search trees
• Sequential access in splay trees takes linear time
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model

Cited in

(6)

• A distribution-sensitive dictionary with low space overhead
• Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
• Canonical density control
• Belga B-trees
• Fast and simple sorting using partial information
• On the hierarchy of distribution-sensitive properties for data structures

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)