ColloquiaTalk by Reghav Kaushik on Wed. February 12, 2003

[Margery Ishmael]

------------------------------------------------------
DEPARTMENT OF COMPUTER SCIENCE - TALK

Wednesday, February 12, 2003 at 2:30 pm in Ryerson 251
-------------------------------------------------------

Speaker: RAGHAV KAUSHIK
From: University of Wisconsin-Madison
http://www.cs.wisc.edu/~raghav/

Title: "Graph Summarization for Path Indexing"

Abstract: Evaluating path expressions efficiently is an important
component of XML data management.  Graph summaries have been proposed that
can be used as a path index. The idea is to substitute graph traversal
over the data with traversal over a much smaller summary. In this talk, I
will describe what are the requirements for a generic path index. Based on
this, we obtain an index specification scheme whereby we can tradeoff the
index size with its generality -- thus, we can specify a smaller index
that covers only a subset of path expressions but does so more
efficiently.

In the second part of the talk, I will discuss how these path indexes can
be combined with inverted lists -- an important component of XML data
management systems. For the class of queries that return only the top k
results, we obtain an instance-optimal way of pushing down the top k
computation (instance optimality is a stronger notion of optimality than
worst-case and average-case optimality).

Host: Prof. Anne Rogers

*Refreshments will follow the talk in Ryerson 255*
People in need of assistance should call 773-834-8977 in advance.