Abstract:

A fundamental problem in data structures is maintaining a dynamic set of elements under the dictionary operations insert, delete, predecessor, and test membership. When the set of elements is drawn from a total order, one solves the problem classically with a balanced binary search tree like an AVL Tree or a Red-Black Tree. In this talk, we consider the problem when the set is partially-ordered.

The problem of searching in trees and partial orders has recently received considerable attention.  Motivating the research are practical problems in filesystem synchronization, software testing and information retrieval.  However, all of the previous work is on the static version of the problem.  In this case, the set S is fixed and a search tree for S does not support the insertion or deletion of elements. Our work is the first to consider the problem in the dynamic setting. We develop the Line-Leaf Tree, a dynamic search tree for tree-like partial orders that never performs more than O(log w) · OPT comparisons. Here OPT is the optimal number of comparisons for the corresponding static search tree and w is the width of the partial order—a natural obstacle when searching a partial order.

Joint work with M. Catalin Iordan (Stanford) and Louis Theran (FU Berlin).