Home   Contact Research:   Events   Seminars People:   Faculty members   Graduate students   Postdoctoral fellows   Alumni   Postdoctoral positions Prospective Students:   Admission   Life at Waterloo   International Students

Algorithms and Complexity Seminar     Date: Tuesday, August 5, 2008 Time: 1:30 PM Place: DC1304         Title: Pattern Matching with Springs: an Adaptive Analysis Speaker: Jeremy Barbay, Departamento de Ciencias de la Computacion, Universidad de Chile Abstract:   We propose an adaptive algorithm for context queries (queries expressed as preorder and ancestor- descendant relations on labeled nodes), which can be used to find patterns in XML documents. Our algorithm takes advantage of the correlation between terms of the query without any preprocessed information, and it runs in time (kd(lg lg min(n,s)+lg lg(r))) in the RAM model, where k is the number of terms in the query, d is the non-deterministic complexity of the query on the multi-labeled tree (i.e. the minimum number of operations required to check the answer to the query), n is the number of nodes in the tree, s is the number of relations between nodes and labels, and r is the maximal number of nodes matching a label on any rooted path in the tree.