Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Path Based Storage and Metadata Guided XPath Evaluation
Speaker:Prof. Sreenivasa Kumar
coming from:IIT Madras
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, SWS
We use this to send out email in the morning.
Level:Expert Audience
Date, Time and Location
Date:Wednesday, 21 June 2006
Duration:60 Minutes
Building:E1 4
As XML is gaining prevalence for representation and exchange

of data, efficient evaluation of queries on XML data
is a major research issue. Structural join based techniques
are well known for XPath evaluation. For the long path expressions,join techniques are not efficient as they increase
the number of joins and disk I/O cost. Whereas, path based
techniques try to reduce the number of joins. In this talk,
we propose a metadata guided query evaluation technique
which uses path based storage. We propose a new way of
organizing the node data of an XML file. We use interval encoding
for the nodes. In addition, we use Strong DataGuide
to assign integer path labels to distinct paths in the data
tree. An element list is maintained for each distinct path
consisting of nodes that can be reached by that path. The
Element-Map gives the one-to-many mapping between element
names (or tag names) to element lists with nodes
having that tag-name. The Path-Map gives the root-to-leaf
path for a given path label. Using these structures, we find
that we can combine top-down path matching and bottom-up
node selections to efficiently perform linear path expression
evaluation. For twig queries, we perform structural
joins at branch points. Through experimental evaluation on
standard data sets, we show that our approach outperforms
the existing path-index based approaches which in turn outperform
structural join methods.

Name(s):Thomas Neumann
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Petra Schaaf, 06/19/2006 09:13 AM
  • Petra Schaaf, 06/19/2006 09:12 AM -- Created document.