Exploiting local similarity for indexing paths in graph-structured data

By Raghav Kaushik, Pradeep Shenoy, Philip Bohannon, Ehud Gudes. Proceedings / International Conference on Data Engineering, 2002

296 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/1f1331994fcd8eeac19d0a77fcc08378c1168379

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Graph indexing: a frequent structure-based approach (2004, methodology): “Various indexing methods [6, 12, 5, 9 , 4, 14, 3] have been developed to process XML queries.”
Graph summarization with bounded error (2008, background): “As a result, the path-index construction schemes of [25, 18, 23] will not coalesce any of the nodes, and will output a final graph summary that is identical to”
Efficient Structural Joins on Indexed XML Documents (2002, background): “We first discuss proposals that do not facilitate a numbering scheme [18] [17] [22] [27] [28] [12].”