November 21st, Wednesday 14:15, Room 303, Jacobs Building

Title: Predecessor Queries on Dynamic Subsets of an Ordered List, with Applications

Lecturer: Tsvi Kopelowitz

Lecturer homepage : http://www.wisdom.weizmann.ac.il/~kopelot/

Affiliation : Faculty of Mathematics and Computer Science in the Weizmann Institute of Science

In the famous order maintenance problem, one wishes to maintain a dynamic list L of size n under insertions, deletions, and order queries. In an order query, one is given two nodes from L and must determine which node precedes the other in L. In an extension to this problem, named the Predecessor search on Dynamic Subsets of an Ordered Dynamic List problem (POLP for short), it is also necessary to maintain dynamic subsets S_1... S_k \subset L, such that given some u in L it will be possible to quickly locate the predecessor of u in any S_i.

The POLP has some interesting applications such as the fastest algorithm for on-line text indexing (suffix tree construction), and improvements on maintaining fully persistent arrays. The talk will focus on both the applications and on an efficient solution for the POLP. In addition, as part of the solution for the POLP, a new and simple solution is provided for the order maintenance problem as opposed to the previously highly complex and incomplete solutions that were previously known.