-------------------------------------------------------------------------
                              DATABASE SEMINAR
-------------------------------------------------------------------------
                             Denilson Barbosa
                    University of Alberta, Edmonton, Canada
-------------------------------------------------------------------------
                       Top-k Approximate Subtree Matching
-------------------------------------------------------------------------
                       Monday July 5, 2010 -- h 15:00
                              **** Aula N7 ****
                    Dipartimento di Informatica e Automazione
                            Universita' Roma Tre
                             Via Vasca Navale, 79
                                  piano terra
--------------------------------------------------------------------------
                                    ABSTRACT
We consider the top-k Approximate Subtree Matching (TASM) problem:
finding the k best matches of a small query tree, e.g., a DBLP article
with 15 nodes, in a large document tree, e.g., DBLP with 26M nodes,
using the canonical tree edit distance as a similarity measure between
subtrees. Evaluating the tree edit distance for large XML trees is
difficult: the best known algorithms have cubic runtime and quadratic
space complexity, and, thus, do not scale. Our solution is
TASM-postorder, a memory-efficient and scalable TASM algorithm. We
prove an upper-bound for the maximum subtree size for which the tree
edit distance needs to be evaluated. The upper bound depends on the
query and is independent of the document size and structure. A core
problem is to efficiently prune subtrees that are above this size
threshold. We develop an algorithm based on the prefix ring buffer that
allows us to prune all subtrees above the threshold in a single
postorder scan of the document. The size of the prefix ring buffer is
linear in the threshold. As a result, the space complexity of
TASM-postorder depends only on k and the query size, and the runtime of
TASM-postorder is linear in the size of the document. Our experimental
evaluation on large synthetic and real XML documents confirms our
analytic results.

Bio:

Denilson Barbosa is a faculty member at the University of Alberta, in
Edmonton, Canada. He received a PhD from the University of Toronto in 2005.
His research interests are in databases and the Web, and he has worked on the
storage, update, and consistency checking of XML data, as well as in mappings
between disparate data formats. Denilson is the recipient of the Alberta
Ingenuity Fund New Faculty Award, and an IBM faculty award.

-----------------------------------------------------------------------------