License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.55
URN: urn:nbn:de:0030-drops-100032
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10003/
Go to the corresponding LIPIcs Volume Portal

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

Multi-Finger Binary Search Trees

pdf-format:
LIPIcs-ISAAC-2018-55.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{chalermsook_et_al:LIPIcs:2018:10003,
  author =	{Parinya Chalermsook and Mayank Goswami and L{\'a}szl{\'o} Kozma and Kurt Mehlhorn and Thatchaphol Saranurak},
  title =	{{Multi-Finger Binary Search Trees}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{55:1--55:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10003},
  URN =		{urn:nbn:de:0030-drops-100032},
  doi =		{10.4230/LIPIcs.ISAAC.2018.55},
  annote =	{Keywords: binary search trees, dynamic optimality, finger search, k-server}
}

Keywords: binary search trees, dynamic optimality, finger search, k-server
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI