Paper Info
Title
D(k)-index: an adaptive structural summary for graph-structured data
Abstract
To facilitate queries over semi-structured data, various structural summaries have been proposed. Structural summaries are derived directly from the data and serve as indices for evaluating path expressions on semi-structured or XML data. We introduce the D(k) index, an adaptive structural summary for general graph structured documents. Building on previous work, 1-index and A(k) index, the D(k)-index is also based on the concept of bisimilarity. However, as a generalization of the 1-index and A(k)-index, the D(k) index possesses the adaptive ability to adjust its structure according to the current query load. This dynamism also facilitates efficient update algorithms, which are crucial to practical applications of structural indices, but have not been adequately addressed in previous index proposals. Our experiments show that the D(k) index is a more effective structural summary than previous static ones, as a result of its query load sensitivity. In addition, update operations on the D(k) index can be performed more efficiently than on its predecessors.
Year
DOI
Venue
2003
10.1145/872757.872776
SIGMOD Conference
Keywords
Field
DocType
graph-structured data,various structural summary,effective structural summary,adaptive structural summary,structural summary,semi-structured data,xml data,structural index,previous work,adaptive ability,previous index proposal,semi structured data,path expressions,indexation,structured data
Dynamism,Graph,Data mining,Computer science,Xml data,Path expression,Graph structured data,Database,K-index
Conference
ISBN
Citations 
PageRank 
1-58113-634-X
153
5.29
References 
Authors
18
3
Search Limit
100153
Name
Order
Citations
PageRank
Qun Chen11737.75
Andrew Lim237321.86
Kian Win Ong319911.72