The Experts below are selected from a list of 6459 Experts worldwide ranked by ideXlab platform
Eran Yahav - One of the best experts on this subject based on the ideXlab platform.
-
practical concurrent Binary Search Trees via logical ordering
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2014Co-Authors: Dana Drachsler, Martin Vechev, Eran YahavAbstract:We present practical, concurrent Binary Search Tree (BST) algorithms that explicitly maintain logical ordering information in the data structure, permitting clean separation from its physical Tree layout. We capture logical ordering using intervals, with the property that an item belongs to the Tree if and only if the item is an endpoint of some interval. We are thus able to construct efficient, synchronization-free and intuitive lookup operations. We present (i) a concurrent non-balanced BST with a lock-free lookup, and (ii) a concurrent AVL Tree with a lock-free lookup that requires no synchronization with any mutating operations, including balancing operations. Our algorithms apply on-time deletion; that is, every request for removal of a node, results in its immediate removal from the Tree. This new feature did not exist in previous concurrent internal Tree algorithms.We implemented our concurrent BST algorithms and evaluated them against several state-of-the-art concurrent Tree algorithms. Our experimental results show that our algorithms with lock-free contains and on-time deletion are practical and often comparable to the state-of-the-art.
Mihai Patrascu - One of the best experts on this subject based on the ideXlab platform.
-
the geometry of Binary Search Trees
Symposium on Discrete Algorithms, 2009Co-Authors: Erik D Demaine, Dion Harmon, John Iacono, Daniel M Kane, Mihai PatrascuAbstract:We present a novel connection between Binary Search Trees (BSTs) and points in the plane satisfying a simple property. Using this correspondence, we achieve the following results:1. A surprisingly clean restatement in geometric terms of many results and conjectures relating to BSTs and dynamic optimality.2. A new lower bound for Searching in the BST model, which subsumes the previous two known bounds of Wilber [FOCS'86].3. The first proposal for dynamic optimality not based on splay Trees. A natural greedy but offline algorithm was presented by Lucas [1988], and independently by Munro [2000], and was conjectured to be an (additive) approximation of the best Binary Search Tree. We show that there exists an equal-cost online algorithm, transforming the conjecture of Lucas and Munro into the conjecture that the greedy algorithm is dynamically optimal.
Zakhar Kabluchko - One of the best experts on this subject based on the ideXlab platform.
-
a functional central limit theorem for branching random walks almost sure weak convergence and applications to random Trees
Annals of Applied Probability, 2016Co-Authors: Rudolf Grubel, Zakhar KabluchkoAbstract:Let $W_{\infty}(\beta)$ be the limit of the Biggins martingale $W_{n}(\beta)$ associated to a supercritical branching random walk with mean number of offspring $m$. We prove a functional central limit theorem stating that as $n\to\infty$ the process \[D_{n}(u):=m^{\frac{1}{2}n}(W_{\infty}(\frac{u}{\sqrt{n}})-W_{n}(\frac{u}{\sqrt{n}}))\] converges weakly, on a suitable space of analytic functions, to a Gaussian random analytic function with random variance. Using this result, we prove central limit theorems for the total path length of random Trees. In the setting of Binary Search Trees, we recover a recent result of R. Neininger [Random Structures Algorithms46 (2015) 346–361], but we also prove a similar theorem for uniform random recursive Trees. Moreover, we replace weak convergence in Neininger’s theorem by the almost sure weak (a.s.w.) convergence of probability transition kernels. In the case of Binary Search Trees, our result states that \[\mathcal{L}\{\sqrt{\frac{n}{2\log n}}(\operatorname{EPL}_{\infty}-\frac{\operatorname{EPL}_{n}-2n\log n}{n})\Big |\mathcal{G}_{n}\}\overset{\mathrm{a.s.w.}}{\underset{n\to\infty}\longrightarrow}\{\omega \mapsto\mathcal{N}_{0,1}\},\] where $\operatorname{EPL}_{n}$ is the external path length of a Binary Search Tree $X_{n}$ with $n$ vertices, $\operatorname{EPL}_{\infty}$ is the limit of the Regnier martingale and $\mathcal{L}\{\cdot |\mathcal{G}_{n}\}$ denotes the conditional distribution w.r.t. the $\sigma$-algebra $\mathcal{G}_{n}$ generated by $X_{1},\ldots,X_{n}$. Almost sure weak convergence is stronger than weak and even stable convergence. We prove several basic properties of the a.s.w. convergence and study a number of further examples in which the a.s.w. convergence appears naturally. These include the classical central limit theorem for Galton–Watson processes and the Polya urn.
-
a functional central limit theorem for branching random walks almost sure weak convergence and applications to random Trees
arXiv: Probability, 2014Co-Authors: Rudolf Grubel, Zakhar KabluchkoAbstract:Let $W_{\infty}(\beta)$ be the limit of the Biggins martingale $W_n(\beta)$ associated to a supercritical branching random walk with mean number of offspring $m$. We prove a functional central limit theorem stating that as $n\to\infty$ the process $$ D_n(u):= m^{\frac 12 n} \left(W_{\infty}\left(\frac{u}{\sqrt n}\right) - W_{n}\left(\frac{u}{\sqrt n}\right) \right) $$ converges weakly, on a suitable space of analytic functions, to a Gaussian random analytic function with random variance. Using this result we prove central limit theorems for the total path length of random Trees. In the setting of Binary Search Trees, we recover a recent result of R. Neininger [Refined Quicksort Asymptotics, Rand. Struct. and Alg., to appear], but we also prove a similar theorem for uniform random recursive Trees. Moreover, we replace weak convergence in Neininger's theorem by the almost sure weak (a.s.w.) convergence of probability transition kernels. In the case of Binary Search Trees, our result states that $$ L\left\{\sqrt{\frac{n}{2\log n}} \left(EPL_{\infty} - \frac{EPL_n-2n\log n}{n}\right)\Bigg | G_{n}\right\} \to \{\omega\mapsto N_{0,1}\}, \quad \text{a.s.w.},$$ where $EPL_n$ is the external path length of a Binary Search Tree $X_n$ with $n$ vertices, $EPL_{\infty}$ is the limit of the R\'egnier martingale, and $L(\,\cdot\, |G_n)$ denotes the conditional distribution w.r.t. the $\sigma$-algebra $G_n$ generated by $X_1,\ldots,X_n$. A.s.w. convergence is stronger than weak and even stable convergence. We prove several basic properties of the a.s.w. convergence and study a number of further examples in which the a.s.w. convergence appears naturally. These include the classical central limit theorem for Galton-Watson processes and the P\'olya urn.
Michel Raynal - One of the best experts on this subject based on the ideXlab platform.
-
a contention friendly Binary Search Tree
International Conference on Parallel Processing, 2013Co-Authors: Tyler Crain, Vincent Gramoli, Michel RaynalAbstract:This paper proposes a new lock-based concurrent Binary Tree using a methodology for writing concurrent data structures. This methodology limits the high contention induced by today's multicore environments to come up with efficient alternatives to the most widely used Search structures. Data structures are generally constrained to guarantee a big-oh step complexity even in the presence of concurrency. By contrast our methodology guarantees the big-oh complexity only in the absence of contention and limits the contention when concurrency appears. The key concept lies in dividing update operations within an eager abstract access that returns rapidly for efficiency reason and a lazy structural adaptation that may be postponed to diminish contention. Our evaluation clearly shows that our lock-based Tree is up to 2.2× faster than the most recent lock-based Tree algorithm we are aware of.
-
A Speculation-Friendly Binary Search Tree
2011Co-Authors: Tyler Crain, Vincent Gramoli, Michel RaynalAbstract:We introduce the first Binary Search Tree algorithm designed for speculative executions. Prior to this work, Tree structures were mainly designed for their pessimistic (non-speculative) accesses to have a bounded complexity. ReSearchers tried to evaluate transactional memory using such Tree structures whose prominent example is the red-black Tree library developed by Oracle Labs that is part of multiple benchmark distributions. Although well-engineered, such structures remain badly suited for speculative accesses, whose step complexity might raise dramatically with contention. We show that our speculation-friendly Tree outperforms the existing transaction-based version of the AVL and the red-black Trees. Its key novelty stems from the decoupling of update operations: they are split into one transaction that modifies the abstraction state and multiple ones that restructure its Tree implementation in the background. In particular, the speculation-friendly Tree is shown correct, reusable and it speeds up a transaction-based travel reservation application by up to 3:5 .
Kunle Olukotun - One of the best experts on this subject based on the ideXlab platform.
-
a practical concurrent Binary Search Tree
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2010Co-Authors: Nathan G Bronson, Jared Casper, Hassan Chafi, Kunle OlukotunAbstract:We propose a concurrent relaxed balance AVL Tree algorithm that is fast, scales well, and tolerates contention. It is based on optimistic techniques adapted from software transactional memory, but takes advantage of specific knowledge of the the algorithm to reduce overheads and avoid unnecessary retries. We extend our algorithm with a fast linearizable clone operation, which can be used for consistent iteration of the Tree. Experimental evidence shows that our algorithm outperforms a highly tuned concurrent skip list for many access patterns, with an average of 39% higher single-threaded throughput and 32% higher multi-threaded throughput over a range of contention levels and operation mixes.