Biased predecessor search

DOI10.1007/s00453-016-0146-7zbMath1352.68071arXiv1707.01182OpenAlexW2335338794MaRDI QIDQ727976

Prosenjit Bose, Rolf Fagerberg, Pat Morin, John Howat

Publication date: 21 December 2016

Published in: Algorithmica, LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

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

zbMATH Keywords

entropydata structurespredecessor searchbiased search trees

Mathematics Subject Classification ID

Searching and sorting (68P10) Data structures (68P05)

Cites Work

• Fast local searches and updates in bounded universes
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• Nearly optimal binary search trees
• Preserving order in a forest in less than logarithmic time and linear space
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Optimal solutions for the temporal precedence problem
• Optimal bounds for the predecessor problem and related problems
• A unified access bound on comparison-based dynamic dictionaries
• Optimum binary search trees
• Time-space trade-offs for predecessor search
• A Distribution-Sensitive Dictionary with Low Space Overhead
• Dynamic ordered sets with exponential search trees
• A priority queue in which initialization and queue operations takeO(loglogD) time
• Biased Search Trees
• Self-adjusting binary search trees
• Algorithms - ESA 2003