דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

ceClub: CBTree: A Practical Concurrent Self-Adjusting Search Tree
event speaker icon
אדם מוריסון (אונ' ת"א)
event date icon
יום רביעי, 21.11.2012, 11:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
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.
[בחזרה לאינדקס האירועים]