Document Open Access Logo

New Binary Search Tree Bounds via Geometric Inversions

Authors Parinya Chalermsook, Wanchote Po Jiamjitrak

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.28.pdf
  • Filesize: 0.88 MB
  • 16 pages

Document Identifiers

Author Details

Parinya Chalermsook
  • Aalto University, Finland
Wanchote Po Jiamjitrak
  • Aalto University, Finland

Funding

  • Chalermsook, Parinya: Part of this work was done while Parinya was visiting the Simons Institute for the Theory of Computing. It was partially supported by the DIMACS/Simons Collaboration on Bridging Continuous and Discrete Optimization through NSF grant #CCF-1740425. This project has received funding from European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 759557). Parinya is also funded by Academy of Finland Research Fellowship, under grant number 310415.

Acknowledgements

We would like to thank Thatchaphol Saranurak for his contributions in the early stage of this paper and for many insightful discussions. We also thank anonymous reviewers for many detailed comments and suggestions.

Cite AsGet BibTex

Parinya Chalermsook and Wanchote Po Jiamjitrak. New Binary Search Tree Bounds via Geometric Inversions. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.28

Abstract

The long-standing dynamic optimality conjecture postulates the existence of a dynamic binary search tree (BST) that is O(1)-competitive to all other dynamic BSTs. Despite attempts from many groups of researchers, we believe the conjecture is still far-fetched. One of the main reasons is the lack of the "right" potential functions for the problem: existing results that prove various consequences of dynamic optimality rely on very different potential function techniques, while proving dynamic optimality requires a single potential function that can be used to derive all these consequences. In this paper, we propose a new potential function, that we call extended (geometric) inversion. Inversion is arguably the most natural potential function principle that has been used in competitive analysis but has never been used in the context of BSTs. We use our potential function to derive new results, as well as streamlining/strengthening existing results. First, we show that a broad class of BST algorithms (including Greedy and Splay) are O(1)-competitive to Move-to-Root algorithm and therefore have simulation embedding property - a new BST property that was recently introduced and studied by Levy and Tarjan (SODA 2019). This result, besides substantially expanding the list of BST algorithms having this property, gives the first potential function proof of the simulation embedding property for BSTs (thus unifying apparently different kinds of results). Moreover, our analysis is the first where the costs of two dynamic binary search trees are compared against each other directly and systematically. Secondly, we use our new potential function to unify and strengthen known BST bounds, e.g., showing that Greedy satisfies the weighted dynamic finger property within a multiplicative factor of (5+o(1)).

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • Binary Search Tree
  • Potential Function
  • Inversion
  • Data Structures
  • Online Algorithms

Metrics

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

References

  1. Susanne Albers. Improved randomized on-line algorithms for the list update problem. SIAM Journal on Computing, 27(3):682-693, 1998. Google Scholar
  2. Susanne Albers. Online algorithms: a survey. Mathematical Programming, 97(1-2):3-26, 2003. Google Scholar
  3. Presenjit Bose, Karim Douïeb, John Iacono, and Stefan Langerman. The power and limitations of static binary search trees with lazy finger. In International Symposium on Algorithms and Computation, pages 181-192. Springer, 2014. Google Scholar
  4. Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak. Pinning down the strong wilber 1 bound for binary search trees. APPROX, 2020. Google Scholar
  5. Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Pattern-avoiding access in binary search trees. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 410-423. IEEE, 2015. Google Scholar
  6. Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Self-adjusting binary search trees: What makes them tick? In Algorithms-ESA 2015, pages 300-312. Springer, 2015. Google Scholar
  7. Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. The landscape of bounds for binary search trees. arXiv preprint, 2016. URL: http://arxiv.org/abs/1603.04892.
  8. Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Multi-finger binary search trees. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  9. Marek Chrobak and Lawrence L. Larmore. An optimal on-line algorithm for k-servers on trees. SIAM J. Comput., 20(1):144-148, 1991. URL: https://doi.org/10.1137/0220008.
  10. Richard Cole. On the dynamic finger conjecture for splay trees. part ii: The proof. SIAM Journal on Computing, 30(1):44-85, 2000. Google Scholar
  11. 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 Journal on Computing, 30(1):1-43, 2000. Google Scholar
  12. Erik D Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Patraşcu. The geometry of binary search trees. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 496-505. SIAM, 2009. Google Scholar
  13. Erik D Demaine, Dion Harmon, John Iacono, and Mihai Patraşcu. Dynamic optimality—almost. SIAM Journal on Computing, 37(1):240-251, 2007. Google Scholar
  14. John Iacono and Stefan Langerman. Weighted dynamic finger in binary search trees. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 672-691. SIAM, 2016. Google Scholar
  15. 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.
  16. Caleb Levy and Robert Tarjan. A new path from splay to dynamic optimality. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1311-1330. Society for Industrial and Applied Mathematics, 2019. Google Scholar
  17. Joan Marie Lucas. Canonical forms for competitive binary search tree algorithms. Rutgers University, Department of Computer Science, Laboratory for Computer …, 1988. Google Scholar
  18. J Ian Munro. On the competitiveness of linear search. In European Symposium on Algorithms, pages 338-345. Springer, 2000. Google Scholar
  19. Seth Pettie. Splay trees, davenport-schinzel sequences, and the deque conjecture. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1115-1124. Society for Industrial and Applied Mathematics, 2008. Google Scholar
  20. Seth Pettie. Applications of forbidden 0-1 matrices to search tree and path compression-based data structures. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms, pages 1457-1467. SIAM, 2010. Google Scholar
  21. Luís MS Russo. A study on splay trees. Theoretical Computer Science, 2018. Google Scholar
  22. Daniel D Sleator and Robert E Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, 1985. Google Scholar
  23. Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652-686, 1985. Google Scholar
  24. Robert Wilber. Lower bounds for accessing binary search trees with rotations. SIAM journal on Computing, 18(1):56-67, 1989. Google Scholar
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 Imprint Privacy Contact