Document Open Access Logo

Multi-Finger Binary Search Trees

Authors Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.55.pdf
  • Filesize: 0.61 MB
  • 26 pages

Document Identifiers

Author Details

Parinya Chalermsook
  • Aalto University, Finland
Mayank Goswami
  • Queens College, City University of New York, USA
László Kozma
  • TU Eindhoven, The Netherlands
Kurt Mehlhorn
  • MPI für Informatik, Saarbrücken, Germany
Thatchaphol Saranurak
  • KTH Royal Institute of Technology, Sweden

Funding

  • Chalermsook, Parinya: Parinya Chalermsook is 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.
  • Kozma, László: László Kozma is supperted through ERC consolidator grant No. 617951.
  • Saranurak, Thatchaphol: Thatchaphol Saranurak is supported by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 715672, and by the Swedish Research Council (Reg. No. 2015-04659).

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 55:1-55:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.55

Abstract

We study multi-finger binary search trees (BSTs), a far-reaching extension of the classical BST model, with connections to the well-studied k-server problem. Finger search is a popular technique for speeding up BST operations when a query sequence has locality of reference. BSTs with multiple fingers can exploit more general regularities in the input. In this paper we consider the cost of serving a sequence of queries in an optimal (offline) BST with k fingers, a powerful benchmark against which other algorithms can be measured. We show that the k-finger optimum can be matched by a standard dynamic BST (having a single root-finger) with an O(log{k}) factor overhead. This result is tight for all k, improving the O(k) factor implicit in earlier work. Furthermore, we describe new online BSTs that match this bound up to a (log{k})^{O(1)} factor. Previously only the "one-finger" special case was known to hold for an online BST (Iacono, Langerman, 2016; Cole et al., 2000). Splay trees, assuming their conjectured optimality (Sleator and Tarjan, 1983), would have to match our bounds for all k. Our online algorithms are randomized and combine techniques developed for the k-server problem with a multiplicative-weights scheme for learning tree metrics. To our knowledge, this is the first time when tools developed for the k-server problem are used in BSTs. As an application of our k-finger results, we show that BSTs can efficiently serve queries that are close to some recently accessed item. This is a (restricted) form of the unified property (Iacono, 2001) that was previously not known to hold for any BST algorithm, online or offline.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Data structures design and analysis
Keywords
  • binary search trees
  • dynamic optimality
  • finger search
  • k-server

Metrics

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

References

  1. Sanjeev Arora, Elad Hazan, and Satyen Kale. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing, 8(1):121-164, 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a006.
  2. Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A Polylogarithmic-Competitive Algorithm for the k-Server Problem. J. ACM, 62(5):40:1-40:49, 2015. URL: http://dx.doi.org/10.1145/2783434.
  3. Yair Bartal and Eddie Grove. The harmonic k-server algorithm is competitive. J. ACM, 47(1):1-15, 2000. URL: http://dx.doi.org/10.1145/331605.331606.
  4. Avrim Blum and Carl Burch. On-line Learning and the Metrical Task System Problem. In Proceedings of the Tenth Annual Conference on Computational Learning Theory, COLT 1997, Nashville, Tennessee, USA, July 6-9, 1997., pages 45-53, 1997. URL: http://dx.doi.org/10.1145/267460.267475.
  5. Avrim Blum, Shuchi Chawla, and Adam Kalai. Static Optimality and Dynamic Search-Optimality in Lists and Trees. Algorithmica, 36(3):249-260, 2003. URL: http://dx.doi.org/10.1007/s00453-003-1015-8.
  6. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
  7. Prosenjit Bose, Jonathan F Buss, and Anna Lubiw. Pattern matching for permutations. Information Processing Letters, 65(5):277-283, 1998. Google Scholar
  8. Prosenjit Bose, Karim Douïeb, John Iacono, and Stefan Langerman. The Power and Limitations of Static Binary Search Trees with Lazy Finger. In ISAAC, pages 181-192, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13075-0_15.
  9. Gerth Stølting Brodal. Finger Search Trees. In Handbook of Data Structures and Applications. Chapman and Hall/CRC, 2004. URL: http://dx.doi.org/10.1201/9781420035179.ch11.
  10. Mark R. Brown and Robert Endre Tarjan. Design and Analysis of a Data Structure for Representing Sorted Lists. SIAM J. Comput., 9(3):594-614, 1980. URL: http://dx.doi.org/10.1137/0209045.
  11. Mihai Bădoiu, Richard Cole, Erik D. Demaine, and John Iacono. A Unified Access Bound on Comparison-Based Dynamic Dictionaries. Theoretical Computer Science, 382(2):86-96, August 2007. Google Scholar
  12. Sébastien Bubeck, Michael B. Cohen, James R. Lee, Yin Tat Lee, and Aleksander Madry. k-server via multiscale entropic regularization. In STOC, 2018. Google Scholar
  13. Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Pattern-Avoiding Access in Binary Search Trees. In FOCS, pages 410-423, 2015. Google Scholar
  14. 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: http://dx.doi.org/10.1137/0220008.
  15. R. Cole. On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof. SIAM Journal on Computing, 30(1):44-85, 2000. URL: http://dx.doi.org/10.1137/S009753979732699X.
  16. 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: http://dx.doi.org/10.1137/S0097539797326988.
  17. 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.
  18. Erik D. Demaine, John Iacono, Stefan Langerman, and Özgür Özkan. Combining Binary Search Trees. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 388-399, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_33.
  19. Erik D. Demaine, Stefan Langerman, and Eric Price. Confluently Persistent Tries for Efficient Version Control. Algorithmica, 57(3):462-483, 2010. URL: http://dx.doi.org/10.1007/s00453-008-9274-z.
  20. Jonathan Derryberry and Daniel Dominic Sleator. Skip-Splay: Toward Achieving the Unified Bound in the BST Model. In WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings, pages 194-205, 2009. Google Scholar
  21. Amos Fiat, Yuval Rabani, and Yiftach Ravid. Competitive k-Server Algorithms. J. Comput. Syst. Sci., 48(3):410-428, 1994. URL: http://dx.doi.org/10.1016/S0022-0000(05)80060-1.
  22. Navin Goyal and Manoj Gupta. On Dynamic Optimality for Binary Search Trees. CoRR, abs/1102.4523, 2011. URL: http://arxiv.org/abs/1102.4523.
  23. Leonidas J. Guibas, Edward M. McCreight, Michael F. Plass, and Janet R. Roberts. A New Representation for Linear Lists. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, pages 49-60, 1977. URL: http://dx.doi.org/10.1145/800105.803395.
  24. John Howat, John Iacono, and Pat Morin. The Fresh-Finger Property. CoRR, abs/1302.6914, 2013. URL: http://arxiv.org/abs/1302.6914.
  25. Scott Huddleston and Kurt Mehlhorn. A New Data Structure for Representing Sorted Lists. Acta Inf., 17:157-184, 1982. URL: http://dx.doi.org/10.1007/BF00288968.
  26. John Iacono. Alternatives to splay trees with O(log n) worst-case access times. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA., pages 516-522, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365522.
  27. 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: http://dx.doi.org/10.1007/978-3-642-40273-9_16.
  28. 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, 2016. Google Scholar
  29. Adam Tauman Kalai and Santosh Vempala. Efficient algorithms for online decision problems. J. Comput. Syst. Sci., 71(3):291-307, 2005. URL: http://dx.doi.org/10.1016/j.jcss.2004.10.016.
  30. Haim Kaplan and Robert Endre Tarjan. Purely Functional Representations of Catenable Sorted Lists. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 202-211, 1996. URL: http://dx.doi.org/10.1145/237814.237865.
  31. Donald E. Knuth. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998. Google Scholar
  32. S. Rao Kosaraju. Localized Search in Sorted Lists. In Proceedings of the 13th Annual ACM Symposium on Theory of Computing, May 11-13, 1981, Milwaukee, Wisconsin, USA, pages 62-69, 1981. URL: http://dx.doi.org/10.1145/800076.802458.
  33. Elias Koutsoupias. The k-server problem. Computer Science Review, 3(2):105-118, 2009. URL: http://dx.doi.org/10.1016/j.cosrev.2009.04.002.
  34. Elias Koutsoupias and Christos H. Papadimitriou. On the k-Server Conjecture. J. ACM, 42(5):971-983, 1995. URL: http://dx.doi.org/10.1145/210118.210128.
  35. James R. Lee. Fusible HSTs and the randomized k-server conjecture. CoRR, abs/1711.01789, 2017. URL: http://arxiv.org/abs/1711.01789.
  36. Christos Levcopoulos and Ola Petersson. Sorting Shuffled Monotone Sequences. Inf. Comput., 112(1):37-50, 1994. URL: http://dx.doi.org/10.1006/inco.1994.1050.
  37. Joan M. Lucas. Canonical forms for competitive binary search tree algorithms. Tech. Rep. DCS-TR-250, Rutgers University, 1988. Google Scholar
  38. Mark S. Manasse, Lyle A. McGeoch, and Daniel Dominic Sleator. Competitive Algorithms for Server Problems. J. Algorithms, 11(2):208-230, 1990. URL: http://dx.doi.org/10.1016/0196-6774(90)90003-W.
  39. K. Mehlhorn and P. Sanders. Algorithms and Data Structures: The Basic Toolbox. Springer, 2008. Google Scholar
  40. Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1 of EATCS Monographs on Theoretical Computer Science. Springer, 1984. URL: http://dx.doi.org/10.1007/978-3-642-69672-5.
  41. Alistair Moffat and Ola Petersson. An Overview of Adaptive Sorting. Australian Computer Journal, 24(2):70-77, 1992. Google Scholar
  42. J.Ian Munro. On the Competitiveness of Linear Search. In Mike S. Paterson, editor, Algorithms - ESA 2000, volume 1879 of Lecture Notes in Computer Science, pages 338-345. Springer Berlin Heidelberg, 2000. URL: http://dx.doi.org/10.1007/3-540-45253-2_31.
  43. William Pugh. Skip Lists: A Probabilistic Alternative to Balanced Trees. Commun. ACM, 33(6):668-676, 1990. URL: http://dx.doi.org/10.1145/78973.78977.
  44. Prabhakar Raghavan and Marc Snir. Memory versus randomization in on-line algorithms. IBM Journal of Research and Development, 38(6):683-708, 1994. URL: http://dx.doi.org/10.1147/rd.386.0683.
  45. Amitai Regev. Asymptotic values for degrees associated with strips of Young diagrams. Advances in Mathematics, 41(2):115-136, 1981. Google Scholar
  46. Raimund Seidel and Cecilia R. Aragon. Randomized Search Trees. Algorithmica, 16(4/5):464-497, 1996. URL: http://dx.doi.org/10.1007/BF01940876.
  47. Steven S. Seiden. A General Decomposition Theorem for the k-Server Problem. Inf. Comput., 174(2):193-202, 2002. URL: http://dx.doi.org/10.1006/inco.2002.3144.
  48. René Sitters. The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem. SIAM J. Comput., 43(1):96-125, 2014. URL: http://dx.doi.org/10.1137/120885309.
  49. Daniel Dominic Sleator and Robert Endre Tarjan. Self-Adjusting Binary Search Trees. J. ACM, 32(3):652-686, 1985. URL: http://dx.doi.org/10.1145/3828.3835.
  50. Robert Endre Tarjan and Christopher J. Van Wyk. An O(n log log n)-Time Algorithm for Triangulating a Simple Polygon. SIAM J. Comput., 17(1):143-178, 1988. URL: http://dx.doi.org/10.1137/0217010.
  51. Athanasios K. Tsakalidis. AVL-Trees for Localized Search. Information and Control, 67(1-3):173-194, 1985. URL: http://dx.doi.org/10.1016/S0019-9958(85)80034-6.
  52. R. Wilber. Lower Bounds for Accessing Binary Search Trees with Rotations. SIAM Journal on Computing, 18(1):56-67, 1989. URL: http://dx.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 Imprint Privacy Contact