• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Very Large Data Bases(VLDB 2004); 20040831-0903; Toronto(CA) >Bloom Histogram: Path Selectivity Estimation for XML Data with Updates
【24h】

Bloom Histogram: Path Selectivity Estimation for XML Data with Updates

机译：Bloom直方图：具有更新的XML数据的路径选择性估计

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

摘要

Cost-based XML query optimization calls for accurate estimation of the selectivity of path expressions. Some other interactive and internet applications can also benefit from such estimations. While there are a number of estimation techniques proposed in the literature, almost none of them has any guarantee on the estimation accuracy within a given space limit. In addition, most of them assume that the XML data are more or less static, i.e., with few updates. In this paper, we present a framework for XML path selectivity estimation in a dynamic context. Specifically, we propose a novel data structure, bloom histogram, to approximate XML path frequency distribution within a small space budget and to estimate the path selectivity accurately with the bloom histogram. We obtain the upper bound of its estimation error and discuss the trade-offs between the accuracy and the space limit. To support updates of bloom histograms efficiently when underlying XML data change, a dynamic summary layer is used to keep exact or more detailed XML path information. We demonstrate through our extensive experiments that the new solution can achieve significantly higher accuracy with an even smaller space than the previous methods in both static and dynamic environments.
机译：基于成本的XML查询优化要求准确估计路径表达式的选择性。其他一些交互式和Internet应用程序也可以从这种估计中受益。尽管文献中提出了许多估计技术，但是几乎没有一种技术可以保证给定空间限制内的估计精度。另外，它们中的大多数都假定XML数据或多或少是静态的，即几乎没有更新。在本文中，我们提出了动态上下文中XML路径选择性估计的框架。具体来说，我们提出了一种新颖的数据结构，布隆直方图，以在较小的空间预算内近似XML路径频率分布，并使用布隆直方图准确估算路径选择性。我们获得其估计误差的上限，并讨论精度与空间限制之间的权衡。为了在基础XML数据发生更改时有效地支持布鲁姆直方图的更新，动态摘要层用于保留准确的或更详细的XML路径信息。通过广泛的实验，我们证明了在静态和动态环境中，新解决方案都可以以比以前的方法更小的空间显着提高精度。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号