Efficient processing of ordered XML twig pattern matching based on extended Dewey
Efficient processing of ordered XML twig pattern matching based on extended Dewey
复制标题
基于扩展Dewey的有序XML树枝模式匹配高效处理
DOI：
10.1631/jzus.a0920006
复制
发表时间：
2009-12
影响因子：
3.2
通讯作者：
C. Gang
中科院分区：
文献类型：
--
作者：
J. JIANG;C. Ke;S. Li-dan;L. Xiao-yan;C. Gang
查找所有出现的小枝模式是可扩展标记语言（XML）查询处理的核心操作。整体分支连接算法避免了大量的中间结果，代表了最先进的算法。然而，在文献中很少提到的有序XML树枝连接和以前的算法，试图解决有序树枝模式（OTP）匹配的问题有很差的性能。在本文中，我们首先提出了一种新的儿童链接栈编码方案来表示复杂的偏序树枝连接结果。基于这种编码方案和扩展的Dewey，我们设计了一种新的整体OTP匹配算法，称为OTJFast，它只需要访问叶子查询节点的标签。此外，我们提出了一个新的算法，名为OTJFaster，结合三个有效的优化规则，以避免不必要的计算。这在可用的索引（比如B+-tree）上工作得很好，跳过了无用的元素。因此，不仅大大减少了磁盘访问，而且避免了许多不必要的计算。最后，我们在真实的和合成数据集上的大量实验表明，我们的算法优于以前的方法上级。
Finding all occurrences of a twig pattern is a core operation of extensible markup language (XML) query processing. Holistic twig join algorithms, which avoid a large number of intermediate results, represent the state-of-the-art algorithms. However, ordered XML twig join is mentioned rarely in the literature and previous algorithms developed in attempts to solve the problem of ordered twig pattern (OTP) matching have poor performance. In this paper, we first propose a novel children linked stacks encoding scheme to represent compactly the partial ordered twig join results. Based on this encoding scheme and extended Dewey, we design a novel holistic OTP matching algorithm, called OTJFast, which needs only to access the labels of the leaf query nodes. Furthermore, we propose a new algorithm, named OTJFaster, incorporating three effective optimization rules to avoid unnecessary computations. This works well on available indices (such as B+-tree), skipping useless elements. Thus, not only is disk access reduced greatly, but also many unnecessary computations are avoided. Finally, our extensive experiments over both real and synthetic datasets indicate that our algorithms are superior to previous approaches.
登录
查看更多内容
DOI：
10.1145/1062745.1062919
发表时间：
2005-05
期刊：
--
影响因子：
--
作者：
Zografoula Vagena;Nick Koudas;D. Srivastava;V. Tsotras
通讯作者：
Zografoula Vagena;Nick Koudas;D. Srivastava;V. Tsotras
DOI：
10.1145/1183614.1183730
发表时间：
2006-11
期刊：
--
影响因子：
--
作者：
Zhewei Jiang;Cheng Luo;W. Hou
通讯作者：
Zhewei Jiang;Cheng Luo;W. Hou
DOI：
10.1109/waim.2008.54
发表时间：
2008-07
期刊：
2008 The Ninth International Conference on Web-Age Information Management
影响因子：
--
作者：
Jinqing Zhu;Wei Wang;Xiaofeng Meng
通讯作者：
Jinqing Zhu;Wei Wang;Xiaofeng Meng
DOI：
10.1145/1132863.1132871
发表时间：
2006-03
期刊：
ACM Trans. Database Syst.
影响因子：
--
作者：
P. Rao;Bongki Moon
通讯作者：
P. Rao;Bongki Moon
影响因子：
11.1
作者：
Scott Boag
通讯作者：
Scott Boag