D(k)-index: an adaptive structural summary for graph-structured data
D(k)-index: an adaptive structural summary for graph-structured data
复制标题
DOI：
10.1145/872757.872776
复制
发表时间：
2003-06
期刊：
影响因子：
--
通讯作者：
Chen Qun;A. Lim;Kian Win Ong
中科院分区：
文献类型：
--
作者：
Chen Qun;A. Lim;Kian Win Ong
为了方便对半结构化数据的查询，已经提出了各种结构化摘要。结构化摘要直接从数据中派生出来，并用作评估半结构化或XML数据上的路径表达式的索引。我们介绍了D(K)索引，它是一种适用于一般图结构文档的自适应结构摘要。在1-指标和A(K)指标的基础上，D(K)-指标也是基于互相似的概念。然而，作为1索引和A(K)索引的推广，D(K)索引具有根据当前查询负载调整其结构的自适应能力。这种活力还有助于高效的更新算法，这对结构指数的实际应用至关重要，但在以前的指数提案中没有得到充分的处理。实验表明，由于D(K)索引对查询负载的敏感性，它是一种比以往静态索引更有效的结构化摘要。此外，在D(K)索引上的更新操作可以比在其前身上更高效地执行。
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.