Document Open Access Logo

Pinning down the Strong Wilber 1 Bound for Binary Search Trees

Authors Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.33.pdf
  • Filesize: 0.71 MB
  • 21 pages

Document Identifiers

Author Details

Parinya Chalermsook
  • Aalto University, Finland
Julia Chuzhoy
  • Toyota Technological Institute at Chicago, IL, USA
Thatchaphol Saranurak
  • Toyota Technological Institute at Chicago, IL, USA

Funding

  • Chalermsook, Parinya: Supported by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 759557) and by Academy of Finland Research Fellows, under grant No. 310415.
  • Chuzhoy, Julia: Supported in part by NSF grant CCF-1616584. Part of the work was done while the second author was a Weston visiting professor at the Department of Computer Science and Applied Mathematics, Weizmann Institute of Science.

Cite As Get BibTex

Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak. Pinning down the Strong Wilber 1 Bound for Binary Search Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.33

Abstract

The dynamic optimality conjecture, postulating the existence of an O(1)-competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems in dynamic data structures. Despite extensive work and some notable progress, including, for example, the Tango Trees (Demaine et al., FOCS 2004), that give the best currently known O(log log n)-competitive algorithm, the conjecture remains widely open. One of the main hurdles towards settling the conjecture is that we currently do not have approximation algorithms achieving better than an O(log log n)-approximation, even in the offline setting. All known non-trivial algorithms for BST’s so far rely on comparing the algorithm’s cost with the so-called Wilber’s first bound (WB-1). Therefore, establishing the worst-case relationship between this bound and the optimal solution cost appears crucial for further progress, and it is an interesting open question in its own right.
Our contribution is two-fold. First, we show that the gap between the WB-1 bound and the optimal solution value can be as large as Ω(log log n/ log log log n); in fact, we show that the gap holds even for several stronger variants of the bound. Second, we provide a simple algorithm, that, given an integer D > 0, obtains an O(D)-approximation in time exp (O (n^{1/2^{Ω(D)}}log n)). In particular, this yields a constant-factor approximation algorithm with sub-exponential running time. Moreover, we obtain a simpler and cleaner efficient O(log log n)-approximation algorithm that can be used in an online setting. Finally, we suggest a new bound, that we call the Guillotine Bound, that is stronger than WB-1, while maintaining its algorithm-friendly nature, that we hope will lead to better algorithms. All our results use the geometric interpretation of the problem, leading to cleaner and simpler analysis.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • Binary search trees
  • Dynamic optimality
  • Wilber bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. G. M. Adelson-Velskiĭ and E. M. Landis. An algorithm for organization of information. Dokl. Akad. Nauk SSSR, 146:263-266, 1962. Google Scholar
  2. Rudolf Bayer. Symmetric binary b-trees: Data structure and maintenance algorithms. Acta Inf., 1:290-306, 1972. URL: https://doi.org/10.1007/BF00289509.
  3. Prosenjit Bose, Karim Douïeb, John Iacono, and Stefan Langerman. The power and limitations of static binary search trees with lazy finger. In Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, pages 181-192, 2014. URL: https://doi.org/10.1007/978-3-319-13075-0_15.
  4. P. Chalermsook, M. Goswami, L. Kozma, K. Mehlhorn, and T. Saranurak. Greedy is an almost optimal deque. WADS, 2015. Google Scholar
  5. Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Pattern-avoiding access in binary search trees. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 410-423, 2015. Google Scholar
  6. R. Chaudhuri and H. Höft. Splaying a search tree in preorder takes linear time. SIGACT News, 24(2):88-93, April 1993. URL: https://doi.org/10.1145/156063.156067.
  7. R. Cole. On the dynamic finger conjecture for splay trees. part ii: The proof. SIAM Journal on Computing, 30(1):44-85, 2000. URL: https://doi.org/10.1137/S009753979732699X.
  8. Richard Cole, Bud Mishra, Jeanette Schmidt, and Alan Siegel. On the dynamic finger conjecture for splay trees. part i: Splay sorting log n-block sequences. SIAM J. Comput., 30(1):1-43, April 2000. URL: https://doi.org/10.1137/S0097539797326988.
  9. Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, and Mihai Pǎtraşcu. The geometry of binary search trees. In SODA 2009, pages 496-505, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496825.
  10. Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pǎtraşcu. Dynamic optimality - almost. SIAM J. Comput., 37(1):240-251, 2007. Announced at FOCS'04. URL: https://doi.org/10.1137/S0097539705447347.
  11. Jonathan Derryberry, Daniel Dominic Sleator, and Chengwen Chris Wang. A lower bound framework for binary search trees with rotations, 2005. Google Scholar
  12. Jonathan C. Derryberry and Daniel D. Sleator. Skip-splay: Toward achieving the unified bound in the BST model. In Frank Dehne, Marina Gavrilova, Jörg-Rüdiger Sack, and CsabaD. Toth, editors, Algorithms and Data Structures, volume 5664 of Lecture Notes in Computer Science, pages 194-205. Springer Berlin Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-03367-4_18.
  13. Amr Elmasry. On the sequential access theorem and deque conjecture for splay trees. Theoretical Computer Science, 314(3):459-466, 2004. URL: https://doi.org/10.1016/j.tcs.2004.01.019.
  14. George F. Georgakopoulos. Chain-splay trees, or, how to achieve and prove loglogn-competitiveness by splaying. Inf. Process. Lett., 106(1):37-43, 2008. URL: https://doi.org/10.1016/j.ipl.2007.10.001.
  15. Dion Harmon. New Bounds on Optimal Binary Search Trees. PhD thesis, Massachusetts Institute of Technology, 2006. Google Scholar
  16. John Iacono. In pursuit of the dynamic optimality conjecture. In Space-Efficient Data Structures, Streams, and Algorithms, volume 8066 of Lecture Notes in Computer Science, pages 236-250. Springer Berlin Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-40273-9_16.
  17. László Kozma. Binary search trees, rectangles and patterns. PhD thesis, Saarland University, Saarbrücken, Germany, 2016. URL: http://scidok.sulb.uni-saarland.de/volltexte/2016/6646/.
  18. Victor Lecomte and Omri Weinstein. Settling the relationship between wilber’s bounds for dynamic optimality. arXiv preprint, 2019. URL: http://arxiv.org/abs/1912.02858.
  19. Joan M. Lucas. On the competitiveness of splay trees: Relations to the union-find problem. On-line Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 7:95-124, 1991. Google Scholar
  20. Seth Pettie. Splay trees, Davenport-Schinzel sequences, and the deque conjecture. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '08, pages 1115-1124, Philadelphia, PA, USA, 2008. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1347082.1347204.
  21. Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM, 32(3):652-686, 1985. Announced at STOC'83. URL: https://doi.org/10.1145/3828.3835.
  22. Rajamani Sundar. On the deque conjecture for the splay algorithm. Combinatorica, 12(1):95-124, 1992. URL: https://doi.org/10.1007/BF01191208.
  23. Robert Endre Tarjan. Sequential access in splay trees takes linear time. Combinatorica, 5(4):367-378, 1985. URL: https://doi.org/10.1007/BF02579253.
  24. Chengwen C. Wang, Jonathan C. Derryberry, and Daniel D. Sleator. O(log log n)-competitive dynamic binary search trees. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06, pages 374-383, Philadelphia, PA, USA, 2006. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1109557.1109600.
  25. R. Wilber. Lower bounds for accessing binary search trees with rotations. SIAM Journal on Computing, 18(1):56-67, 1989. Announced at FOCS'86. URL: https://doi.org/10.1137/0218004.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact