• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Database Systems for Advanced Applications >TwigBuffer: Avoiding Useless Intermediate Solutions Completely in Twig Joins
【24h】

TwigBuffer: Avoiding Useless Intermediate Solutions Completely in Twig Joins

机译：TwigBuffer：在Twig连接中完全避免无用的中间解决方案

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Twig pattern matching plays a crucial role in XML data processing. TwigStack [2] is a holistic twig join algorithm that solves the problem in two steps: (1) finding potentially useful intermediate path solutions, (2) merging the intermediate solutions. The algorithm is optimal when the twig pattern has only //-edges, in the sense that no useless partial solutions are generated in the first step (thus expediting the second step and boosting the overall performance). However, when /-edges are present, a large set of useless partial solutions may be produced, which directly downgrades the overall performance. Recently, some improved versions of the algorithm (e.g., TwigStackList and iTwigJoin) have been proposed in an attempt to reduce the number of useless partial solutions when /-edges are involved. However, none of the algorithms can avoid useless partial solutions completely. In this paper, we propose a new algorithm, TwigBuffer, that is guaranteed to completely avoid the useless partial solutions. Our algorithm is based on a novel strategy to buffer and manipulate elements in stacks and lists. Experiments show that TwigBuffer significantly outperforms previous algorithms when arbitrary /-edges are present.
机译：Twig模式匹配在XML数据处理中起着至关重要的作用。 TwigStack [2]是一种整体的小枝连接算法，它分两步解决该问题：（1）查找潜在有用的中间路径解决方案，（2）合并中间解决方案。当枝条图案仅具有//-边缘时，该算法是最佳的，因为在第一步中不会生成无用的部分解（从而加快了第二步并提高了整体性能）。但是，当存在/ -edges时，可能会产生大量无用的部分解决方案，这直接降低了整体性能。最近，已经提出了该算法的一些改进版本（例如，TwigStackList和iTwigJoin），以试图减少当涉及到-边缘时无用的部分解的数量。但是，没有一种算法可以完全避免无用的部分解决方案。在本文中，我们提出了一种新算法TwigBuffer，该算法可确保完全避免无用的部分解决方案。我们的算法基于一种新颖的策略来缓存和操作堆栈和列表中的元素。实验表明，当存在任意/-边时，TwigBuffer明显优于以前的算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号