Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Predecessor Queries on Dynamic Subsets of an Ordered List, with Applications
event speaker icon
Tsvi Kopelowitz (Weizmann Institute of Science)
event date icon
Wednesday, 14.11.2012, 12:30
event location icon
Taub 201
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.