Talks & Seminars
Graph Summarization for Path Indexing
Raghav Kaushik, Univ. Wisconsin Madison
Date & Time: March 10, 2003 11:30
Venue: CSE Seminar Hall
Evaluating path expressions efficiently is an important component of XML data management. Graph summaries based on the notion of graph bisimilarity have been proposed as candidate path indexes. 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).
Speaker Profile:
Raghav Kaushik, Univ. Wisconsin Madison
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback