TagsArticle Source
Is it possible to make self-adjusting data structures concurrent?
- A Google TechTalk, presented by Vitaly Aksenov, 2024-06-25
- Google Algorithms Seminar.
ABSTRACT
In this talk, we cover several aspects of self-adjusting data structures. These data structures answer more frequent queries faster. The most famous example is the SplayTree, which rotates the accessed node to the root, leading to a lower depth for frequently accessed nodes. Obviously, such an approach is averse to concurrency, as there is a very high contention on the root. The first concurrent self-adjusting data structure is a binary tree CBTree, which was presented in 2012, but like the concurrent AVL tree it is based on, it does not have much scalability due to the hand-over-hand validation traversals.
We decided to look at the problem from a different direction. As was clear a long time ago, a SkipList is much easier to make concurrent than any balanced binary tree. Thus, we designed a self-adjusting concurrent SkipList named Splay-List and proved its complexity. Then, we found work on a concurrent Interpolation Search Tree (IST) that is built on efficient lazy rebuilding. Thus, we discuss how to make self-adjusting multi-way data structures quite easily using lazy rebuilding, with examples of B-tree and IST, providing a possibility for efficient concurrent implementations.
This talk almost does not require any prior knowledge and relies on the interest in data structures by the listeners.
ABOUT THE SPEAKER
Vitaly Aksenov is currently an Assistant Professor at City, University of London. His research focuses on self-adjusting systems and practice and theory of parallel and concurrent data structures. Before joining City, University of London, Vitaly was an Assistant Professor at ITMO University for a while and prior to that, he was a post-doc in IST Austria under the guidance of professor Dan Alistarh. He received his PhD from Paris 7 Diderot and ITMO University under the guidance of professor Petr Kuznetsov.