Concurrent Trees Supporting Complex Queries

Abstract

Augmenting an existing sequential data structure with extra information to support greater functionality is a widely used technique. For example, search trees are augmented to build sequential data structures like order-statistic trees, interval trees, tango trees, link/cut trees and many others. We study how to design concurrent augmented tree data structures. We present a new, general technique that can augment a lock-free tree to add any new fields to each tree node, provided the new fields’ values can be computed from information in the node and its children. This enables the design of lock-free, linearizable analogues of a wide variety of classical augmented data structures.

We apply our technique to a lock-free binary search tree (BST). Our augmented BST supports order statistic queries in O(h) steps on a tree of height h. The augmentation does not affect the asymptotic running time of the updates. We give an alternative augmentation to improve searches and order-statistic queries to run in O(log |S|) steps, where |S| is the size of the impleemented set (with a small increase in step complexity of updates). As an added bonus, our technique supports arbitrary multi-point queries (such as range queries) with the same time complexity as they would have in the corresponding sequential data structure.

Speaker Bio

P. Fatourou is a Professor of Computer Science at the University of Crete and the Foundation for Research and Technology - Hellas (FORTH). She has worked as a Marie-Curie Individual Fellow at Université Paris Cité (UPC), as a visiting Professor at École Polytechnique Fédérale de Lausanne (EPFL), and as a visiting researcher at the University of York, the University of Toronto, and the University of Cyprus. She has been a postdoc at Max-Planck Institut für Informatik (MPII) and at the University of Toronto (UoT), and a visiting postdoc at the University of Brown. Her research interests focuses on all aspects of parallel and distributed computing. 

P. Fatourou is currently serving as the Steering Committee chair of the ACM Symposium on Principles of Distributed Computing (PODC). She has served as the chair (July 2019 – June 2021) and the past chair (July 2021 – June 2023) of the ACM Europe Council. She has been the editor of the Distributed Computing Column of the Bulletin of the European Association for Theoretical Computer Science (BEATCS), the PC chair of the 20th International Conference on Principles of Distributed Systems (OPODIS) and of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). She has served as the general chair of PODC, as an ACM Distinguished Speaker and as a Featured ACM Member. She is currently the chair of the Evaluation Committee of the ACM Grace Murray Hopper Award. She is at the editorial board of the Communications of ACM (Regional Special Section) and of IEEE Transactions on Parallel and Distributed Systems. She has received many distinctions for her research achievements, including two best paper awards in top conferences of her field (PPoPP 2022 and DISC 2024). 

Ms. Fatourou has attracted significant funding from national and international sources. She has significant activity in supporting diversity and equity in science, including establishing and acting as the first chair of the Greek ACM-W chapter.