Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMulti-finger binary search trees
76
0
0.0
(
0
)
Added by
L\\'aszl\\'o Kozma
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
In this paper we present t
Motivated by recent developments in optical switching and reconfigurable network design, we study dynamic binary search trees (BSTs) in the matching model. In the classical dynamic BST model, the cost of both link traversal and basic reconfiguration (rotation) is $O(1)$. However, in the matching model, the BST is defined by two optical switches (that represent two matchings in an abstract way), and each switch (or matching) reconfiguration cost is $alpha$ while a link traversal cost is still $O(1)$. In this work, we propose Arithmetic BST (A-BST), a simple dynamic BST algorithm that is based on dynamic Shannon-Fano-Elias coding, and show that A-BST is statically optimal for sequences of length $Omega(n alpha log alpha)$ where $n$ is the number of nodes (keys) in the tree.
We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online $O(log log n)$-competitive search tree data structure in this model, matching the best known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one which we call Steiner-closed search trees, which may be of independent interest. Moreover our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees, and secondly from these trees into paths.
The dynamic optimality conjecture, postulating the existence of an $O(1)$-competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems in dynamic data structures. Despite extensive work and some notable progress, including, for example, the Tango Trees (Demaine et al., FOCS 2004), that give the best currently known $O(log log n)$-competitive algorithm, the conjecture remains widely open. One of the main hurdles towards settling the conjecture is that we currently do not have approximation algorithms achieving better than an $O(log log n)$-approximation, even in the offline setting. All known non-trivial algorithms for BSTs so far rely on comparing the algorithms cost with the so-called Wilbers first bound (WB-1). Therefore, establishing the worst-case relationship between this bound and the optimal solution cost appears crucial for further progress, and it is an interesting open question in its own right. Our contribution is two-fold. First, we show that the gap between the WB-1 bound and the optimal solution value can be as large as $Omega(log log n/ log log log n)$; in fact, the gap holds even for several stronger variants of the bound. Second, we provide a simple algorithm, that, given an integer $D>0$, obtains an $O(D)$-approximation in time $expleft(Oleft (n^{1/2^{Omega(D)}}log nright )right )$. In particular, this gives a constant-factor approximation sub-exponential time algorithm. Moreover, we obtain a simpler and cleaner efficient $O(log log n)$-approximation algorithm that can be used in an online setting. Finally, we suggest a new bound, that we call {em Guillotine Bound}, that is stronger than WB, while maintaining its algorithm-friendly nature, that we hope will lead to better algorithms. All our results use the geometric interpretation of the problem, leading to cleaner and simpler analysis.
In the classical Steiner tree problem, given an undirected, connected graph $G=(V,E)$ with non-negative edge costs and a set of emph{terminals} $Tsubseteq V$, the objective is to find a minimum-cost tree $E subseteq E$ that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of $rho = ln(4)+varepsilon < 1.39$. In this paper, we study a natural generalization, the emph{multi-level Steiner tree} (MLST) problem: given a nested sequence of terminals $T_{ell} subset dots subset T_1 subseteq V$, compute nested trees $E_{ell}subseteq dots subseteq E_1subseteq E$ that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names including Multi-level Network Design, Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two simple $O(ell)$-approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most $2ell$ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present various integer linear programming (ILP) formulations for the MLST problem, and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to $ell=100$ levels, which is sufficient for most applications such as network visualization or designing multi-level infrastructure.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
