Concurrent Self-Adjusting Data Structures - Challenges and Solutions

Explore the challenges and possibilities of making self-adjusting data structures concurrent in this 48-minute Google TechTalk presented by Vitaly Aksenov. Delve into various aspects of self-adjusting data structures, which are designed to answer frequent queries faster. Learn about the SplayTree, a famous example that rotates accessed nodes to the root, and understand why this approach poses challenges for concurrency. Discover the CBTree, the first concurrent self-adjusting data structure, and its limitations. Examine alternative approaches, including the Splay-List, a self-adjusting concurrent SkipList, and explore how lazy rebuilding can be used to create self-adjusting multi-way data structures like B-trees and Interpolation Search Trees (IST). Gain insights into the potential for efficient concurrent implementations of these structures. This talk is accessible to listeners with an interest in data structures and requires minimal prior knowledge.