Name
Abstract | ||
|---|---|---|
In this paper, we present a concurrent multiway tree algorithm using the lazy locking mechanism introduced in the lazy-list algorithm for concurrent linked lists. The multiway tree is represented in a left-child right-sibling tree, in which the keys are defined to represent the containing or ordering relationship among the nodes. We enhance the lazy locking mechanism by applying it to a concurrent left-child right-sibling tree algorithm, which deals with more complicated scenarios than linked lists. Our algorithm also optimized the lazy locking mechanism by simplifying the validation process and allowing threads to traverse fewer nodes to locate the target node when validation failed. The experimental results show that our optimization improves the throughput slightly over the Lazy-tree algorithm which uses the lazy locking mechanism in updating of the LCRS tree without our optimization, and both the Optimized and Lazy-tree algorithms significantly overtake the Global-rwLock approach, which uses a single reader-writer lock to ensure concurrent manipulation of the multiway tree. |
Year | Venue | Field |
|---|---|---|
2016 | CASCON | Tree traversal,Computer science,Tree (data structure),Algorithm,Left-child right-sibling binary tree,Concurrent data structure,Fractal tree index,Search tree,Interval tree,Incremental decision tree |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bing Yang | 1 | 1 | 1.73 |
| Kenneth B. Kent | 2 | 458 | 54.42 |
| Eric Aubanel | 3 | 57 | 9.75 |
| Tobi Ajila | 4 | 0 | 0.34 |
| Angela Lin | 5 | 193 | 11.38 |