Search: onr:"swepub:oai:DiVA.org:kth-252246" >
Multi-finger binary...
Multi-finger binary search trees
-
Chalermsook, P. (author)
-
Goswami, M. (author)
-
Kozma, L. (author)
-
show more...
-
Mehlhorn, K. (author)
-
- Saranurak, Thatchaphol (author)
- KTH,Teoretisk datalogi, TCS
-
show less...
-
(creator_code:org_t)
- Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018
- 2018
- English.
-
In: Leibniz International Proceedings in Informatics, LIPIcs. - : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. - 9783959770941 ; , s. 55:1-55:26
- Related links:
-
http://isaac2018.ie....
-
show more...
-
https://urn.kb.se/re...
-
https://doi.org/10.4...
-
show less...
Abstract
Subject headings
Close
- 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 headings
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
Keyword
- Binary search trees
- Dynamic optimality
- Finger search
- K-server
- Forestry
- K-server problem
- Locality of reference
- On-line algorithms
- Query sequence
- Binary trees
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
To the university's database