A history of distribution-sensitive data structures

DOI10.1007/978-3-642-40273-9_10zbMATH Open1394.68090OpenAlexW29684811MaRDI QIDQ2848972FDOQ2848972

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

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
• Biased predecessor search

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• 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)
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Improved bounds for finger search on a RAM
• Optimal solutions for the temporal precedence problem
• Lower Bounds for Accessing Binary Search Trees with Rotations
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• Biased range trees
• Layered working-set trees
• Title not available (Why is that?)
• A static optimality transformation with applications to planar point location

Cited In (2)

• Canonical density control
• 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)