The Taub Faculty of Computer Science Events and Talks

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

Bio:
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.