TY - GEN
T1 - CBTree
T2 - 26th International Symposium on Distributed Computing, DISC 2012
AU - Afek, Yehuda
AU - Kaplan, Haim
AU - Korenfeld, Boris
AU - Morrison, Adam
AU - Tarjan, Robert E.
PY - 2012
Y1 - 2012
N2 - We present the CBTree, a new counting-based self-adjusting binary search tree that, like splay trees, moves more frequently accessed nodes closer to the root. After m operations on n items, c of which access some item v, an operation on v traverses a path of length O(log m/c) while performing few if any rotations. In contrast to the traditional self-adjusting splay tree in which each accessed item is moved to the root through a sequence of tree rotations, the CBTree performs rotations infrequently (an amortized subconstant o(1) per operation if m ≫ n), mostly at the bottom of the tree. As a result, the CBTree scales with the amount of concurrency. We adapt the CBTree to a multicore setting and show experimentally that it improves performance compared to existing concurrent search trees on non-uniform access sequences derived from real workloads.
AB - We present the CBTree, a new counting-based self-adjusting binary search tree that, like splay trees, moves more frequently accessed nodes closer to the root. After m operations on n items, c of which access some item v, an operation on v traverses a path of length O(log m/c) while performing few if any rotations. In contrast to the traditional self-adjusting splay tree in which each accessed item is moved to the root through a sequence of tree rotations, the CBTree performs rotations infrequently (an amortized subconstant o(1) per operation if m ≫ n), mostly at the bottom of the tree. As a result, the CBTree scales with the amount of concurrency. We adapt the CBTree to a multicore setting and show experimentally that it improves performance compared to existing concurrent search trees on non-uniform access sequences derived from real workloads.
UR - http://www.scopus.com/inward/record.url?scp=84868341103&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84868341103&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-33651-5_1
DO - 10.1007/978-3-642-33651-5_1
M3 - Conference contribution
AN - SCOPUS:84868341103
SN - 9783642336508
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 15
BT - Distributed Computing - 26th International Symposium, DISC 2012, Proceedings
Y2 - 16 October 2012 through 18 October 2012
ER -