Abstract | ||
---|---|---|
Ctrie is a scalable concurrent non-blocking dictionary data structure, with good cache locality, and non-blocking linearizable iterators. However, operations on most existing concurrent hash tries run in O(log n) time. In this technical report, we extend the standard concurrent hash-tries with an auxiliary data structure called a cache. The cache is essentially an array that stores pointers to a specific level of the hash trie. We analyze the performance implications of adding a cache, and prove that the running time of the basic operations becomes O(1). |
Year | Venue | Field |
---|---|---|
2017 | arXiv: Data Structures and Algorithms | Data structure,Pointer (computer programming),Discrete mathematics,Ctrie,Non-blocking algorithm,Cache,Parallel computing,Hash function,Mathematics,Hash trie,Scalability |
DocType | Volume | Citations |
Journal | abs/1712.09636 | 0 |
PageRank | References | Authors |
0.34 | 1 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Aleksandar Prokopec | 1 | 163 | 13.56 |