Name
Abstract | ||
|---|---|---|
We present a new lock-free algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. It combines ideas from two recently proposed lock-free algorithms: one of them provides good performance for a read-dominated workload and the other one for a write-dominated workload. Specifically, it uses internal representation of a search tree (as in the first one) and is based on marking edges instead of nodes (as in the second one). Our experiments indicate that our new lock-free algorithm outperforms other lock-free algorithms in most cases providing up to 35% improvement in some cases over the next best algorithm. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2684464.2684472 | ICDCN |
Keywords | Field | DocType |
binary,language constructs and features,concurrent data structure,concurrent programming,lock-free algorithm,search tree | AVL tree,Tree traversal,Search algorithm,Computer science,Self-balancing binary search tree,Optimal binary search tree,Theoretical computer science,Dichotomic search,Ternary search tree,Distributed computing,Interval tree | Conference |
Citations | PageRank | References |
4 | 0.41 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arunmoezhi Ramachandran | 1 | 10 | 2.26 |
| Neeraj Mittal | 2 | 444 | 37.04 |