A unified access bound on comparison-based dynamic dictionaries

No abstract is available for this paper.

• Publication year

  2007

• Venue

  Theoretical Computer Science

• Publication date

  2007-08-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.tcs.2007.03.002
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A simplified and dynamic unified structure

  2004cited by this paper
• On the sequential access theorem and deque conjecture for splay trees

  2004cited by this paper
• Distribution-sensitive data structures

  2001cited by this paper
• Alternatives to splay trees with O(log n) worst-case access times

  2001cited by this paper
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof

  2000cited by this paper
• On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences

  1995cited by this paper
• On the deque conjecture for the splay algorithm

  1992cited by this paper
• Amortized Complexity of Data Structures

  1991cited by this paper
• Sequential access in splay trees takes linear time

  1985cited by this paper
• Self-adjusting binary search trees

  1985cited by this paper
• Design and Analysis of a Data Structure for Representing Sorted Lists

  1978cited by this paper
• A new representation for linear lists

  1977cited by this paper
• Organization and maintenance of large ordered indexes

  1972cited by this paper
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes

  1971cited by this paper
• Optimum binary search trees

  1971cited by this paper

• The Group Access Bounds for Binary Search Trees

  2023cites this paper
• Universal Optimality of Dijkstra Via Beyond-Worst-Case Heaps

  2023cites this paper
• On the Power of Learning-Augmented Search Trees

  2022cites this paper
• Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition

  2022cites this paper
• On the Power of Learning-Augmented BSTs

  2022cites this paper
• What Does Dynamic Optimality Mean in External Memory?

  2022cites this paper
• The Geometry of Tree-Based Sorting

  2021cites this paper
• The Log-Interleave Bound: Towards the Unification of Sorting and the BST Model

  2021influential citation
• Lazy Search Trees

  2020cites this paper
• Belga B-Trees

  2019cites this paper
• Multi-finger binary search trees

  2018cites this paper
• High Performance Self Organizing Dynamic Dictionaries

  2016influential citation
• Heterogeneous (CPU+GPU) Working-set Hash Tables

  2016cites this paper
• The landscape of bounds for binary search trees

  2016cites this paper
• A Hybrid CPU+GPU Working-Set Dictionary

  2016cites this paper
• Praktické datové struktury

  2015cites this paper
• A Study on Splay Trees

  2015cites this paper
• Pattern-Avoiding Access in Binary Search Trees

  2015cites this paper
• Top-Down Skiplists

  2014cites this paper
• Data Mechanics and Coupling Geometry on Binary Bipartite Networks

  2014cites this paper
• Dynamic Data Structures: The Interplay of Invariants and Algorithm Design

  2013cites this paper
• In Pursuit of the Dynamic Optimality Conjecture

  2013cites this paper
• A History of Distribution-Sensitive Data Structures

  2013cites this paper
• On the hierarchy of distribution-sensitive properties for data structures

  2013cites this paper
• The Fresh-Finger Property

  2013cites this paper
• A Self-adjusting Data Structure for Multidimensional Point Sets

  2012cites this paper
• Dynamizing Succinct Tree Representations

  2012cites this paper
• A priority queue with the time-finger property

  2012cites this paper
• Steps on Multi-Target Prediction and Adaptability to Dynamic Input

  2012cites this paper
• Exploiting non-uniform query distributions in data structuring problems

  2012influential citation
• De-amortizing Binary Search Trees

  2011cites this paper
• A Unifying Property for Distribution-Sensitive Priority Queues

  2011cites this paper
• Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property

  2011cites this paper
• Biased Predecessor Search

  2011cites this paper
• A Cache-Oblivious Implicit Dictionary with the Working Set Property

  2010cites this paper
• Priority Queues with Multiple Time Fingers

  2010cites this paper
• Rank-Sensitive Priority Queues

  2009cites this paper
• Adaptive Binary Search Trees Jonathan Carlyle Derryberry

  2009cites this paper
• Heterogeneous decomposition of degree-balanced search trees and its applications

  2009cites this paper
• Skip-Splay: Toward Achieving the Unified Bound in the BST Model

  2009cites this paper
• The geometry of binary search trees

  2009cites this paper
• Adaptive binary search trees

  2009influential citation
• Layered Working-Set Trees

  2009cites this paper
• A Distribution-Sensitive Dictionary with Low Space Overhead

  2009cites this paper
• Uniquely represented data structures with applications to privacy

  2008cites this paper
• Dynamic optimality for skip lists and B-trees

  2008cites this paper
• Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors

  2008cites this paper
• The Geometry of Binary Search Trees ∗

  2008cites this paper