首页> 正文

基于Bloom Filter的路径表达式查询处理

2020-11-23阅读(837)

基于Bloom Filter的路径表达式查询处理

论文摘要

近年来，XML语言已经成为了互联网上数据表示和交换事实上的标准。随着Web服务和个性化信息订阅等应用的蓬勃发展，越来越多的信息以XML的格式通过网络被发布和交换。在这些应用中，XML数据以数据流的形式不断地快速到达，而针对XML数据的查询是大量的路径表达式，传统的查询处理技术在性能上已经不能够满足应用的需求。在XML数据流上对大量的路径表达式进行查询处理是科研技术人员所面临的一个新的挑战。本文围绕XML数据流的查询处理问题展开研究工作，分别探讨了针对简单路径表达式和复杂路径表达式的查询处理技术，提出了新的处理方法，并通过实验验证了所提出方法的有效性和高效性。同时，本文就XML数据流处理引擎的设计进行了探讨，并实现了一个原型系统。论文的主要贡献可以总结为如下几点：·本文首先提出了将Bloom Filter结构应用于解决XML数据流过滤问题的方法，该方法可以有效地支持对简单路径表达式中的通配符“*”号和后代轴“／／”的处理。同时本文设计了前缀过滤的方法，用于减少解析过程中所生成候选路径的数量，提高过滤处理的性能。详尽的对比实验表明，本文提出的方法在创建路由表时的性能和所创建路由表的大小两个方面明显优于已有的处理方法。同时，在查询集很大并且XML文档深度相对较小的情况下，本文提出的方法在过滤性能上也要优于已有的方法。·本文提出了将包含有分支结构的复杂路径表达式分解成一组简单路径表达式，在对简单路径表达式进行过滤处理的基础上，实现对复杂路径表达式进行查询处理的方法。与已有的方法不同，本文所提出的方法以简单路径过滤引擎输出的查询字符串流作为输入，可以支持对元素内容约束的处理，同时可以以连续查询(Continuous Queries)的方式实现对复杂路径表达式的查询处理。本文通过实验将所提出的处理方法与已有方法进行了对比，证明该方法在对复杂路径表达式的查询处理上具有较好的性能。·本文在简单路径表达式和复杂路径表达式查询处理技术的研究基础之上，设计和实现了一个XML数据流处理引擎——XSTR(XML STReamProcessing Engine)原型系统，并对该系统的实现进行了介绍。XSTR系统可以被作为中间件应用于针对XML数据流进行处理的应用系统中。综上所述，本文就XML数据流的查询处理技术进行了深入的探讨和研究，提出了不同于已有方法的新的技术和方法，并通过实验对所提方法的有效性进行了验证。本文的研究工作，促进了XML查询处理技术的发展，具有现实的应用价值。

论文目录

  • 中文摘要
  • 英文摘要
  • 图目录
  • 1 绪论
  • 1.1 研究工作的背景
  • 1.2 本文的研究内容
  • 1.3 论文的主要贡献
  • 1.4 章节安排
  • 2 背景知识和相关工作
  • 2.1 可扩展标记语言（XML）
  • 2.1.1 XML文档基本结构
  • 2.1.2 XML文档的树模型
  • 2.1.3 XML文档的解析
  • 2.2 XML查询语言
  • 2.2.1 XPath语言和路径表达式
  • 2.2.2 本文所处理的路径表达式
  • 2.2.3 路径表达式的计算
  • 2.3 XML查询处理技术
  • 2.3.1 XML文档数据库查询
  • 2.3.2 XML数据流查询
  • 2.4 XML数据流处理原型系统
  • 2.4.1 华盛顿大学的XMLTK系统
  • 2.4.2 加州大学伯克利分校的YFilter系统
  • 2.5 本章小结
  • 3 针对简单路径表达式的过滤处理
  • 3.1 Bloom Filter结构
  • 3.2 XML文档过滤问题定义
  • 3.3 基于Bloom Filter的简单路径过滤
  • 3.3.1 XML文档路由器
  • 3.3.2 候选路径
  • 3.3.3 XML文档的过滤
  • 3.4 前缀过滤方法
  • 3.5 实验与分析
  • 3.5.1 数据集和查询
  • 3.5.2 前缀过滤的性能
  • 3.5.3 路由表的创建与大小
  • 3.5.4 XML文档过滤的性能
  • 3.6 本章小结
  • 4 复杂路径表达式的查询处理
  • 4.1 节点内容约束的处理
  • 4.2 复杂路径表达式的分解
  • 4.3 复杂路径表达式的查询处理
  • 4.3.1 复杂路径表达式的表示
  • 4.3.2 基于路径流的处理方法
  • 4.3.3 复杂路径表达式查询处理示例
  • 4.3.4 基于路径存储的处理方法
  • 4.4 实验与分析
  • 4.4.1 实验设置
  • 4.4.2 对不同数量通配符和后代轴的处理性能对比
  • 4.4.3 对不同大小XML文档的处理性能对比
  • 4.4.4 对不同大小查询集的处理性能对比
  • 4.5 本章小结
  • 5 XML数据流处理引擎
  • 5.1 XML数据流引擎的应用
  • 5.2 XSTR系统的架构
  • 5.3 XSTR系统的实现
  • 5.4 本章小结
  • 6 总结与展望
  • 参考文献
  • 攻读博士期间发表论文
  • 致谢

    • 相关论文文献

    • [1].基于Bloom Filter的硬件字符串匹配设计与验证[J]. 电子科技 2009(12)
    • [2].基于改进型Bloom Filter的网络流抽样算法[J]. 电子设计工程 2015(24)
    • [3].位置大数据中一种基于Bloom Filter的匿名保护方法[J]. 计算机科学 2017(06)
    • [4].基于Bloom filter降低云数据库网络延时的影响[J]. 软件导刊 2018(10)
    • [5].基于Bloom filter的高效正则表达式匹配算法[J]. 计算机应用研究 2012(03)
    • [6].Bloom Filter在手机垃圾短信过滤中的应用[J]. 安庆师范学院学报(自然科学版) 2014(03)
    • [7].计数型Bloom Filter及其在机器人导航中的应用[J]. 微计算机信息 2008(35)
    • [8].基于Bloom filter的RFID中间件数据过滤算法研究[J]. 计算机应用研究 2015(05)
    • [9].基于Bloom Filter的混合云存储安全去重方案[J]. 计算机工程与应用 2018(10)
    • [10].基于Bloom Filter的去重方法研究[J]. 计算技术与自动化 2016(01)
    • [11].基于Bloom filter的远程对称差规模估算法[J]. 计算技术与自动化 2013(04)
    • [12].基于BLOOM FILTER过滤算法的重复数据删除技术的研究与改进[J]. 电脑知识与技术 2014(21)
    • [13].一种高效低成本的RFID认证协议[J]. 微计算机信息 2012(06)
    • [14].基于Bloom Filter的网页去重算法[J]. 微型电脑应用 2011(03)
    • [15].Bloom Filter研究进展[J]. 电信科学 2010(02)
    • [16].4种计数型Bloom Filter的性能分析与比较[J]. 软件学报 2010(05)
    • [17].Bloom Filter在重复数据删除技术中应用的研究[J]. 计算机技术与发展 2016(08)
    • [18].基于Bloom Filter的网络爬虫URL消重算法研究[J]. 产业与科技论坛 2011(18)
    • [19].一种基于Bloom filter的加强队列公平性改进算法[J]. 计算机应用研究 2010(08)
    • [20].一种基于Bloom Filter的正则表达式集合快速搜索算法[J]. 华南理工大学学报(自然科学版) 2009(04)
    • [21].基于多特征匹配和Bloom filter的重复数据删除算法[J]. 深圳大学学报(理工版) 2016(05)
    • [22].Bloom Filter及其在网络中的应用综述[J]. 计算机应用与软件 2013(09)
    • [23].Bloom filter的硬件字符串匹配设计研究[J]. 信息通信 2012(02)
    • [24].Bloom filter在网络取证中的应用研究[J]. 计算机工程与应用 2010(14)
    • [25].信源定位方案中基于Bloom Filter存储的概率日志记录方法研究[J]. 电子与信息学报 2009(11)
    • [26].K分组合型Bloom Filter方法的设计[J]. 计算机研究与发展 2008(S1)
    • [27].一种基于计数型Bloom Filter的报文分类算法[J]. 信息工程大学学报 2015(05)
    • [28].基于查询内容Bloom Filter的P2P网络路由机制[J]. 信息工程大学学报 2008(04)
    • [29].浅析Bloom Filter[J]. 科技资讯 2013(10)
    • [30].标记多重嵌套Bloom Filter算法[J]. 闽江学院学报 2008(02)

    标签：;  ;  ;  ;  

    基于Bloom Filter的路径表达式查询处理
    下载Doc文档

    猜你喜欢

    © 2024 毕速过 版权所有 鄂ICP备12018319号-5