• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Proof of Designed Reliability >BOXes: efficient maintenance of order-based labeling for dynamic XML data
【24h】

BOXes: efficient maintenance of order-based labeling for dynamic XML data

机译：框：有效维护基于订单的动态XML数据标签

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

摘要

Order-based element labeling for tree-structured XML data is an important technique in XML processing. It lies at the core of many fundamental XML operations such as containment join and twig matching. While labeling for static XML documents is well understood, less is known about how to maintain accurate labeling for dynamic XML documents, when elements and subtrees are inserted and deleted. Most existing approaches do not work well for arbitrary update patterns; they either produce unacceptably long labels or incur enormous relabeling costs. We present two novel I/O-efficient data structures, W-BOX and B-BOX that efficiently maintain labeling for large, dynamic XML documents. We show analytically and experimentally that both, despite consuming minimal amounts of storage, gracefully handle arbitrary update patterns without sacrificing lookup efficiency. The two structures together provide a nice tradeoff between update and lookup costs: W-BOX has logarithmic amortized update cost and constant worst-case lookup cost, while B-BOX has constant amortized update cost and logarithmic worst-case lookup cost. We further propose techniques to eliminate the lookup cost for read-heavy workloads.
机译：树状XML数据的基于顺序的元素标记是XML处理中的一项重要技术。它位于许多基本XML操作的核心，例如包含连接和枝条匹配。尽管对静态XML文档的标签已广为人知，但在插入和删除元素和子树时，如何为动态XML文档保持准确的标签知之甚少。大多数现有方法不适用于任意更新模式。它们要么产生不可接受的长标签，要么招致巨大的重新贴标签成本。我们介绍了两种新颖的I / O高效数据结构，即W-BOX和B-BOX，它们可以有效地维护大型动态XML文档的标签。我们通过分析和实验表明，这两者尽管消耗了最少的存储量，但都能在不牺牲查找效率的前提下优雅地处理任意更新模式。这两个结构一起提供了更新和查找成本之间的良好折衷：W-BOX具有对数摊销的更新成本和恒定的最坏情况查找成本，而B-BOX具有恒定的摊销的更新成本和对数最坏情况查找成本。我们进一步提出了消除大量读取工作负载的查找成本的技术。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号