Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Multi-finger binary search trees
Show others and affiliations
2018 (English)In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2018, p. 55:1-55:26Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2018. p. 55:1-55:26
Keywords [en]
Binary search trees, Dynamic optimality, Finger search, K-server, Forestry, K-server problem, Locality of reference, On-line algorithms, Query sequence, Binary trees
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-252246DOI: 10.4230/LIPIcs.ISAAC.2018.55Scopus ID: 2-s2.0-85063659218ISBN: 9783959770941 (print)OAI: oai:DiVA.org:kth-252246DiVA, id: diva2:1323375
Conference
29th International Symposium on Algorithms and Computation, ISAAC 2018, 16 December 2018 through 19 December 2018
Note

QC20190612

Available from: 2019-06-12 Created: 2019-06-12 Last updated: 2019-06-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopushttp://isaac2018.ie.nthu.edu.tw/

Authority records BETA

Saranurak, Thatchaphol

Search in DiVA

By author/editor
Saranurak, Thatchaphol
By organisation
Theoretical Computer Science, TCS
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 71 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf