| 41. |
- Chatterjee, Bapi, 1982, et al.
(författare)
-
Concurrent Linearizable Nearest Neighbour Search in LockFree-kD-tree
- 2015
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The Nearest neighbour search (NNS) is an important problem in a large number of application domains dealing with multidimensional data. In concurrent settings, where dynamic modi?cations are allowed, a linearizable implementation of NNS is highly desirable to discover the latest nearest neighbour of a given target data-point. In this paper, we introduce the LockFree-kD-tree (LFkD-tree): a lock-free concurrent kD-tree, which implements an abstract data type (ADT) that provides the operations Add, Remove, Contains, and NNS. Our implementation is linearizable. The operations in the LFkD-tree use single-word read and compare-and-swap (CAS) atomic primitives, which are readily supported on commonly available multi-core processors. We experimentally evaluate the LFkD-tree using several benchmarks comprising real-world and synthetic datasets. The experiments show that the presented design is scalable and achieves significant speed-up compared to the implementations of an existing sequential kD-tree and a recently proposed multidimensional indexingstructure, PH-tree.
|
|
| 42. |
- Chatterjee, Bapi, 1982, et al.
(författare)
-
Concurrent linearizable nearest neighbour search in lockfree-kd-Tree
- 2018
-
Ingår i: ACM International Conference Proceeding Series. - New York, NY, USA : ACM. ; Part F133180
-
Konferensbidrag (refereegranskat)abstract
- The Nearest neighbour search (NNS) is a fundamental problem in many application domains dealing with multidimensional data. In a concurrent setting, where dynamic modi-fications are allowed, a linearizable implementation of NNS is highly desirable. This paper introduces the LockFree-kD-Tree (LFkD-Tree): A lock-free concurrent kD-Tree, which implements an abstract data type (ADT) that provides the operations Add, Remove, Contains, and NNS. Our implementation is linearizable. The operations in the LFkD-Tree use single-word read and compare-And-swap (CAS) atomic primitives, which are readily supported on available multi-core processors. We experimentally evaluate the LFkD-Tree using several benchmarks comprising real-world and synthetic datasets. The experiments show that the presented design is scalable and achieves signi cant speed-up compared to the implementations of an existing sequential kD-Tree and a recently proposed multidimensional indexing structure, PH-Tree. © 2018 Copyright held by the owner/author(s).
|
|
| 43. |
- Chatterjee, Bapi, 1982, et al.
(författare)
-
Concurrent linearizable nearest neighbour search in LockFree-kD-tree
- 2021
-
Ingår i: Theoretical Computer Science. - : Elsevier BV. - 0304-3975. ; 886, s. 27-48
-
Tidskriftsartikel (refereegranskat)abstract
- The Nearest neighbour search (NNS) is a fundamental problem in many application domains dealing with multidimensional data. In a concurrent setting, where dynamic modifications are allowed, a linearizable implementation of the NNS is highly desirable. This paper introduces the LockFree-kD-tree (LFkD-tree ): a lock-free concurrent kD-tree, which implements an abstract data type (ADT) that provides the operations Add, Remove, Contains, and NNS. Our implementation is linearizable. The operations in the LFkD-tree use single-word read and compare-and-swap ([Formula presented] ) atomic primitives, which are readily supported on available multi-core processors. We experimentally evaluate the LFkD-tree using several benchmarks comprising real-world and synthetic datasets. The experiments show that the presented design is scalable and achieves significant speed-up compared to the implementations of an existing sequential kD-tree and a recently proposed multidimensional indexing structure, PH-tree.
|
|
| 44. |
- Chatterjee, Bapi, 1982, et al.
(författare)
-
Efficient lock-free binary search trees
- 2014
-
Ingår i: 2014 ACM Symposium on Principles of Distributed Computing, PODC 2014; Paris; France; 15 July 2014 through 18 July 2014. - New York, NY, USA : ACM. - 9781450329446 ; , s. 322-331
-
Konferensbidrag (refereegranskat)abstract
- In this paper we present a novel algorithm for concurrent lock-free internal binary search trees (BST) and implement a Set abstract data type (ADT) based on that. We show that in the presented lock-free BST algorithm the amortized step complexity of each set operation - ADD, REMOVE and CONTAINS - is O(H(n) + c), where H(n) is the height of the BST with n number of nodes and c is the contention during the execution. Our algorithm adapts to contention measures according to read-write load. If the situation is read-heavy, the operations avoid helping the concurrent REMOVE operations during traversal, and adapt to interval contention. However, for the write-heavy situations we let an operation help a concurrent REMOVE, even though it is not obstructed. In that case, an operation adapts to point contention. It uses single-word compare-and-swap (CAS) operations. We show that our algorithm has improved disjoint-access-parallelism compared to similar existing algorithms. We prove that the presented algorithm is linearizable. To the best of our knowledge, this is the first algorithm for any concurrent tree datastructure in which the modify operations are performed with an additive term of contention measure.
|
|
| 45. |
- Chatterjee, Bapi, 1982, et al.
(författare)
-
Help-optimal and Language-portable Lock-free Concurrent Data Structures
- 2016
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Helping is the most common mechanism to guarantee lock-freedom in many concurrent data structures. An optimized helping strategy improves the overall performance of a lock-free algorithm. In this paper, we propose help-optimality, which essentially implies that no operationstep is accounted for exclusive helping in the lock-free synchronization of concurrent operations. To describe the concept, we revisit the designs of a lock-free linked-list and a lock-free binary search tree and present improved algorithms. Our algorithms employ atomic single-word compare-and-swap (CAS) primitives and are linearizable.Additionally, we do not use a language/platform speci?c mechanism to modulate helping, speci?cally, we use neither bit-stealing from a pointer nor runtime type introspection of objects, making the algorithms language-portable. Further, to optimize the amortized numberof steps per operation, if a CAS execution to modify a shared pointer fails, we obtain a fresh set of thread-local variables without restarting an operation from scratch.We use several micro-benchmarks in both C/C++ and Java to validate the e?ciency of our algorithms against existing state-of-the-art. The experiments show that the algorithms are scalable. Our implementations perform on a par with highly optimized ones and in manycases yield 10%-50% higher throughput.
|
|
| 46. |
- Chatterjee, Bapi, 1982, et al.
(författare)
-
Help-Optimal and Language-Portable Lock-Free Concurrent Data Structures
- 2016
-
Ingår i: 45th International Conference on Parallel Processing (ICPP), 2016. - 0190-3918. - 9781509028238 ; 2016 september, s. 360-369
-
Konferensbidrag (refereegranskat)abstract
- Helping is a widely used technique to guarantee lock-freedom in many concurrent data structures. An optimized helping strategy improves the overall performance of a lock-free algorithm. In this paper, we propose help-optimality, which essentially implies that no operation step is accounted for exclusive helping in the lock-free synchronization of concurrent operations. To describe the concept, we revisit the designs of a lock-free linked-list and a lock-free binary search tree and present improved algorithms. Our algorithms employ atomic single-word compare-and-swap (CAS) primitives and are linearizable. We design the algorithms without using any language/platformspecific mechanism. Specifically, we use neither bit-stealing froma pointer nor runtime type introspection of objects. Thus, our algorithms are language-portable. Further, to optimize the amortized number of steps per operation, if a CAS execution tomodify a shared pointer fails, we obtain a fresh set of thread-local variables without restarting an operation from scratch. We use several micro-benchmarks in both C/C++ and Java to validate the efficiency of our algorithms against existing state-of-the-art. The experiments show that the algorithms are scalable. Our implementations perform on a par with highly optimizedones and in many cases yield 10%-50% higher throughput.
|
|
| 47. |
|
|
| 48. |
- Damaschke, Peter, 1963, et al.
(författare)
-
Competitive Freshness Algorithms for Wait-free Data Objects
- 2005
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Wait-free concurrent data objects are widely used in multiprocessor systems and real-time systems. Their popularity results from the fact that they avoid locking and that concurrent operations on such data objects are guaranteed to finish in a bounded number of steps regardless of the other operations interference. The data objects allow high access parallelism and guarantee correctness of the concurrent access with respect to its semantics. In such a highly-concurrent environment, where write-operations update the object state concurrently with read-operations, the age/freshness of the state returned by a read-operation is a significant measure of the object quality.In this paper, we first propose a freshness measure for wait-free concurrent data objects. Subsequently, we model the freshness problem as an online problem and present two algorithms for the problem. The first one is an optimal deterministic algorithm with freshness competitive ratio $\sqrt{\alpha}$, where $\alpha$ is a function of execution-time upper-bound of wait-free operations. The second one is a competitive randomized algorithm with freshness competitive ratio $\frac{\ln \alpha}{1 + \ln 2 - \frac{2}{\sqrt{\alpha}}}$.
|
|
| 49. |
- Damaschke, Peter, 1963, et al.
(författare)
-
One-Way Trading with Time-Varying Exchange Rate Bounds
- 2005
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- One-way trading is a basic online problem in finance. Since its optimal solution is given by a simple formula (however with difficult analysis), the problem is attractive as a target to which other practical online problems can betransformed. However, there are still natural online problems that do not fit in the known variants of one-way trading. We present some new models where the bounds of exchange rates are not constant but vary with time in certain ways. The first model, where the (logarithmic) exchange rate has limited decay speed, arises from an issue in distributed data structures, namely to maximize the(appropriately defined) freshness of values in concurrent objects. For this model we prove a lower bound on the competitive ratio which is nearly optimal, i.e., upto a small constant factor. Clearly, the lower bound holds also against stronger adversaries. Then, we give an optimal algorithm in a model where only the maximal allowed exchange rate decreases with time, but the actual exchange rates may jump arbitrarily within this frame. We have chosen this more powerful adversary model afterwards because some applications does not make use of the limited decay speed. In fact, we adapt the optimal threat-based algorithm of El-Yaniv et al. (2001) to our case. Our numerical experiments suggest that this algorithm is still not too far from the lower bound for the weaker adversary. This isexplained by the observation that slowly increasing exchange rates seem to be the worst case for the online player.
|
|
| 50. |
- Damaschke, Peter, 1963, et al.
(författare)
-
Online search with time-varying price bounds
- 2009
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 55:4, s. 619-642
-
Tidskriftsartikel (refereegranskat)abstract
- Online search is a basic online problem. The fact that its optimal deterministic/randomized solutions are given by simple formulas (however with difficult analysis) makes the problem attractive as a target to which other practical online problems can be transformed to find optimal solutions. However, since the upper/lower bounds of prices in available models are constant, natural online problems in which these bounds vary with time do not fit in the available models. We present two new models where the bounds of prices are not constant but vary with time in certain ways. The first model, where the upper and lower bounds of (logarithmic) prices have decay speed, arises from a problem in concurrent data structures, namely to maximize the (appropriately defined) freshness of data in concurrent objects. For this model we present an optimal deterministic algorithm and a nearly-optimal randomized algorithm. We also prove a lower bound of competitive ratios of randomized algorithms. The second model is inspired by the fact that some applications do not utilize the decay speed of the lower bound of prices in the first model. In the second model, only the upper bound decreases arbitrarily with time and the lower bound is constant. Clearly, the lower bound of competitive ratios proved for the first model holds also against the stronger adversary in the second model. For the second model, we present an optimal randomized algorithm. Our numerical experiments on the freshness problem show that this new algorithm achieves much better/smaller competitive ratios than previous algorithms do.
|
|
