ComputingComputer ScienceData StructuresDatabasesInformation RetrievalData SummarizationQuery ProcessingText SummarizationGraph IndexingGraph SummarizationGraph-based SummarizationIndexesIndexingIndexing Data StructuresIndexing StructuresUpdate Mechanisms
Structural summaries derived from semi‑structured data serve as indices for evaluating path expressions, and prior work such as the 1‑index and A(k) index rely on bisimilarity. This paper introduces the D(k) index, an adaptive structural summary designed for general graph‑structured documents. The D(k) index generalizes earlier indices by dynamically adjusting its structure to current query load, thereby enabling efficient update algorithms that previous proposals lacked. Experiments demonstrate that the D(k) index outperforms static summaries in effectiveness and supports faster update operations than its predecessors.
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.
19
Three Partition Refinement Algorithms
Robert Paige, Robert E. Tarjan · SIAM Journal on Computing · 1987 · 1.2K citations
The Lorel query language for semistructured data
Serge Abiteboul, Dallan Quass, Jason McHugh et al. · International Journal on Digital Libraries · 1997 · 1.1K citations
On supporting containment queries in relational database management systems
Chun Zhang, Jeffrey F. Naughton, David J. DeWitt et al. · 2001 · 785 citations
Indexing and Querying XML Data for Regular Path Expressions
Quanzhong Li, Bongki Moon · 2001 · 761 citations