Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSelectable Heaps and Optimal Lazy Search Trees
102
0
0.0
(
0
)
Added by
Bryce Sandlund
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We show the $O(log n)$ time extract minimum function of efficient priority queues can be generalized to the extraction of the $k$ smallest elements in $O(k log(n/k))$ time, where we define $log(x)$ as $max(log_2(x), 1)$. We first show heap-ordered tree selection (Kaplan et al., SOSA 19) can be applied on the heap-ordered trees of the classic Fibonacci heap to support the extraction in $O(k log(n/k))$ amortized time. We then show selection is possible in a priority queue with optimal worst-case guarantees by applying heap-ordered tree selection on Brodal queues (SODA 96), supporting the operation in $O(k log(n/k))$ worst-case time. Via a reduction from the multiple selection problem, $Omega(k log(n/k))$ time is necessary if insertion is supported in $o(log n)$ time. We then apply the result to lazy search trees (Sandlund & Wild, FOCS 20), creating a new interval data structure based on selectable heaps. This gives optimal $O(B+n)$ time lazy search tree performance, lowering insertion complexity into a gap $Delta_i$ to $O(log(n/|Delta_i|))$ time. An $O(1)$ time merge operation is also made possible when used as a priority queue, among other situations. If Brodal queues are used, runtimes of the lazy search tree can be made worst-case in the general case of two-sided gaps. The presented data structure makes fundamental use of soft heaps (Chazelle, J. ACM 00), biased search trees, and efficient priority queues, approaching the theoretically-best data structure for ordered data.
rate research
Read More
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.
We give a new algorithm to construct optimal alphabetic ternary trees, where every internal node has at most three children. This algorithm generalizes the classic Hu-Tucker algorithm, though the overall computational complexity has yet to be determined.
In this paper we present a new data structure for double ended priority queue, called min-max fine heap, which combines the techniques used in fine heap and traditional min-max heap. The standard operations on this proposed structure are also presented, and their analysis indicates that the new structure outperforms the traditional one.
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.
We prove a separation between offline and online algorithms for finger-based tournament heaps undergoing key modifications. These heaps are implemented by binary trees with keys stored on leaves, and intermediate nodes tracking the min of their respective subtrees. They represent a natural starting point for studying self-adjusting heaps due to the need to access the root-to-leaf path upon modifications. We combine previous studies on the competitive ratios of unordered binary search trees by [Fredman WADS2011] and on order-by-next request by [Martinez-Roura TCS2000] and [Munro ESA2000] to show that for any number of fingers, tournament heaps cannot handle a sequence of modify-key operations with competitive ratio in $o(sqrt{log{n}})$. Critical to this analysis is the characterization of the modifications that a heap can undergo upon an access. There are $exp(Theta(n log{n}))$ valid heaps on $n$ keys, but only $exp(Theta(n))$ binary search trees. We parameterize the modification power through the well-studied concept of fingers: additional pointers the data structure can manipulate arbitrarily. Here we demonstrate that fingers can be significantly more powerful than servers moving on a static tree by showing that access to $k$ fingers allow an offline algorithm to handle any access sequence with amortized cost $O(log_{k}(n) + 2^{lg^{*}n})$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
