Layered working-set trees

DOI10.1007/S00453-011-9542-1MaRDI QIDQ2429341zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Karim Douïeb, John Howat, Vida Dujmović

Publication date 26 April 2012

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.2071

zbMATH Keywords

worst-case analysisbinary search treesdistribution sensitivityworking-set property

Mathematics Subject Classification ID

Trees (05C05) Data structures (68P05) Searching and sorting (68P10)

Abstract: The working-set bound [Sleator and Tarjan, J. ACM, 1985] roughly states that searching for an element is fast if the element was accessed recently. Binary search trees, such as splay trees, can achieve this property in the amortized sense, while data structures that are not binary search trees are known to have this property in the worst case. We close this gap and present a binary search tree called a layered working-set tree that guarantees the working-set property in the worst case. The unified bound [Badoiu et al., TCS, 2007] roughly states that searching for an element is fast if it is near (in terms of rank distance) to a recently accessed element. We show how layered working-set trees can be used to achieve the unified bound to within a small additive term in the amortized sense while maintaining in the worst case an access time that is both logarithmic and within a small multiplicative factor of the working-set bound.

Recommendations

• Layered working-set trees
• Combining binary search trees
• Alternatives to splay trees with \(O(\log n)\) worst-case access times
• A unified access bound on comparison-based dynamic dictionaries
• De-amortizing binary search trees

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• A unified access bound on comparison-based dynamic dictionaries
• Introduction to algorithms
• Lower Bounds for Accessing Binary Search Trees with Rotations
• 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
• Self-adjusting binary search trees
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model
• Symmetric binary B-trees: Data structure and maintenance algorithms

Cited in

(6)

• LATIN 2004: Theoretical Informatics
• A history of distribution-sensitive data structures
• A unified access bound on comparison-based dynamic dictionaries
• Layered working-set trees
• On the hierarchy of distribution-sensitive properties for data structures
• Alternatives to splay trees with \(O(\log n)\) worst-case access times

This page was built for publication: Layered working-set trees

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