|
Published Articles >> Table of Contents >> Abstract
18th International Conference on Data Engineering (ICDE'02)
p. 0129
Exploiting Local Similarity for Indexing Paths in Graph-Structured Data
Raghav Kaushik, Univ. of Wisconsin-Madison
Pradeep Shenoy, Univ. of Washington-Seattle
Philip Bohannon, Bell Labs
Ehud Gudes, Ben-Gurion Univ.
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2002.994703
Send link to a friend
| Abstract |
|
XML and other semi-structured data may have partially specified or missing schema information, motivating the use of a structural summary which can be automatically computed from the data. These summaries also serve as indices for evaluating the complex path expressions common to XML and semi-structured query languages. However, to answer all path queries accurately, summaries must encode information about long, seldom-queried paths, leading to increased size and complexity with little added value. We introduce the A(k)-indices, a family of approximate structural summaries. They are based on the concept of k-bisimilarity, in which nodes are grouped based on local structure, i.e., the incoming paths of length up to k. The parameter k thus smoothly varies the level of detail (and accuracy) of the A(k)-index. For small values of k, the size of the index is substantially reduced. While smaller, the A(k) index is approximate, and we describe techniques for efficiently extracting exact answers to regular path queries. Our experiments show that, for moderate values of k, path evaluation using the A(k)-index ranges from being very efficient for simple queries to competitive for most complex queries, while using significantly less space than comparable structures.
|
 Additional Information
|
Citation:
Raghav Kaushik, Pradeep Shenoy, Philip Bohannon, Ehud Gudes,
"Exploiting Local Similarity for Indexing Paths in Graph-Structured Data,"
icde,
p. 0129,
18th International Conference on Data Engineering (ICDE'02),
2002
|
|
