Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

ceClub: CBTree: A Practical Concurrent Self-Adjusting Search Tree
event speaker icon
Adam Morrison (CS, Tel Aviv University)
event date icon
Wednesday, 21.11.2012, 11:30
event location icon
Room 337-8 Taub Bld.
We present the CBTree, a new counting-based self-adjusting sequential search tree that, like splay trees, moves more frequently accessed nodes closer to the root: After M operations on N items, Q of which access some item V, an operation on V traverses a path of length O(log M/Q) 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. Therefore, CBTree gracefully supports concurrency.

Joint work with: Yehuda Afek, Haim Kaplan, Boris Korenfeld, Robert E. Tarjan

Adam Morrison is a Computer Science PhD student at Tel Aviv University, under the supervision of Prof. Yehuda Afek. He works on fast and scalable algorithms for multicore systems. He received his MSc and BSc in Computer Science Cum Laude from Tel Aviv University. He is the recipient an IBM PhD Fellowship.