多数据类型的数据流查询处理及优化

多数据类型的数据流查询处理及优化

论文摘要

数据流作为一种新型的数据模型,在许多应用,如:网络流量管理、金融数据分析、电子商务、交通治理、网站信息的发布和订阅、版权保护以及环境和工业监控中扮演着重要的角色。基于数据流模型的查询处理以及优化技术也得到了广泛的研究。数据流无限、快速的特性和数据流应用系统资源有限、要求快速响应的特点打破了传统查询处理技术的很多假设,需要我们重新研究基础的数据库查询处理技术。由于数据流是动态的,数据流上的查询通常是连续、大量的。而系统只能处理或者保存与查询相关的数据。因此对查询的特性进行统计分析并设计有效的索引结构来将查询组织起来,是查询优化的关键所在。同时,众多应用所面向的数据类型是多种多样的。而在数据流系统查询处理及优化的研究中,大多面向结构化和半结构化的数据对象。因此,本文针对各种数据类型(结构化数据集中和分布式、多媒体数据以及RDF图数据)上的连续查询问题设计新颖的系统框架和有效的优化算法。同时,本文还对每个所提出的技术及其相关工作进行大量、深入的实验分析,实验结果都充分证明了这些技术的有效性和高效性。本文主要贡献如下:1.设计了有效且准确的集中式结构化数据κ-NN监控方案:有效的处理数据流上连续的κ最近邻(k-NN)查询在许多应用领域都是一个重要的问题。通常并非数据流上所有数据都可以存放在内存中。因此,大多数己存在的解决方案仅把有代表性的数据放入索引中,而丢弃一些数据。这些解决方案都是近似的。在本文中,通过对查询而非流数据建立索引结构,将与查询相关的数据存放在Skyline数据结构中以及有效的延迟技术来处理结构化数据准确的κ-NN查询。2.提出一个新颖的基于划分的连接操作模式PMJoin,以优化分布式结构化数据的连接查询计划、减少传输代价:数据流的应用中,数据源通常分散在不同地方。因此,处理多条不同数据源数据流连接操作查询的时候,不可避免的产生巨大的数据传输代价。对于连续的连接查询来说,如果不进行查询优化处理,宝贵的带宽资源会被大量浪费。本文提出一个启发式的算法来合理安排多数据流连续查询计划,使得系统总体传输代价最小化。3.设计了基于数据流算法的多媒体数据流上拷贝检测查询处理和优化算法:数字视频被越来越广泛的应用在众多的多媒体应用中,并通常以视频流的形式被广播和传送。为了从内容上来进行版权管理,连续监控高速、持续的视频流上的视频拷贝问题得到越来越多的关注。有效的数据流算法是处理大量连续拷贝检测查询所必需的。本章首先定义了在视频被改动后仍然有效的视频序列的相似性。同时采用基于哈希的视频梗概(Sketch)来有效的计算视频序列的相似性。然后,设计了巧妙的位向量签名(Signature)来达到CPU和内存两方面优化的目标。最后,为了同时处理多个连续查询,设计了一个索引结构来组织查询序列。4.基于图特性的语义网上静态和流式RDF图数据查询处理:有效的RDF查询处理正在成为一个把语义网技术(Semantic Web)应用到真实世界的重要因素。正因为如此,许多研究工作致力于怎样用特殊的模式在关系数据库中进行存储和查询。本文提出一个在三元组方式下存储、索引和查询RDF数据的新颖模式。该模式优化两部分查询处理:对于静态数据的即时查询和对流式RDF数据的连续查询。主要创新点在于把RDF数据的图形特性考虑进来,有助于减少在垂直数据库里面连接操作的代价。在静态查询优化算法的基础上再提出RDF流上连续查询优化策略:(1)根据连续查询的特征,对流进系统的RDF三元组进行分组。(2)每个查询维护相关的记录列表。(3)每个连续查询定期的在相关数据组中进行查询处理,进而提高了查询效率并节省存储空间。本文通过巧妙的设计查询优化算法和连续查询索引结构,并且将数据流技术和不同数据类型的特点相结合,使得原来无法处理的查询变成可行、原来只能得到近似结果的查询变成准确、原来效率低下的查询效率提高3到4个数量级。这些技术不仅可以在上述具体应用中发挥重要的作用,而且可以扩展应用在更多数据类型上的连续查询中。

论文目录

  • 中文摘要
  • 英文摘要
  • 图目录
  • 表目录
  • 第一章 绪论
  • 1.1 数据流模型
  • 1.1.1 数据特点
  • 1.1.2 数据流上的查询
  • 1.1.3 数据流上的几个应用的例子
  • 1.2 数据流管理系统DSMS
  • 1.3 面临的挑战
  • 1.4 本文主要贡献
  • 1.5 本文组织结构
  • 第二章 基本概念和相关技术
  • 2.1 本文相关查询
  • 2.1.1 连接查询
  • 2.1.2 相似查询
  • 2.1.3 多媒体数据流上拷贝检测查询
  • 2.1.4 RDF数据、RDF数据流及其查询
  • 2.2 相关技术
  • 2.2.1 数据流查询处理常用技术
  • 2.2.2 其他技术
  • 2.3 本章小结
  • 第三章 数据流上高效的连续k-NN查询优化
  • 3.1 引言
  • 3.2 相关工作
  • 3.3 基于Skyline结构的对象维护
  • 3.4 对象延迟技术
  • 3.5 查询索引
  • 3.6 返回结果
  • 3.7 k-最近邻查询
  • 3.8 实验分析
  • 3.8.1 查询索引
  • 3.8.2 缓冲器大小
  • 3.8.3 可测性
  • 3.9 本章小结
  • 第四章 数据流连接操作的查询优化
  • 4.1 背景介绍
  • 4.2 相关工作
  • 4.3 问题公式化
  • 4.3.1 系统模型
  • 4.3.2 问题描述
  • 4.4 分布式多路连接查询的优化
  • 4.4.1 基于流的连接
  • 4.4.2 基于划分的连接
  • 4.5 实验分析
  • 4.5.1 基于整条流的连接操作
  • 4.5.2 基于分割的模式
  • 4.5.3 不同属性的连接查询
  • 4.6 本章小结以及未来工作展望
  • 第五章 视频搜索中的数据流查询优化算法
  • 5.1 引言
  • 5.2 相关工作
  • 5.3 数据流视频拷贝检测
  • 5.3.1 帧的指纹(Fingerprint)
  • 5.3.2 相似性度量
  • 5.4 视频序列的梗概(Sketch)
  • 5.4.1 视频数据流序列的比较
  • 5.4.2 代价分析
  • 5.5 优化梗概比较操作
  • 5.5.1 位向量签名
  • 5.5.2 剪枝策略
  • 5.5.3 索引查询序列
  • 5.6 实验分析
  • 5.6.1 系统实现
  • 5.6.2 实验设置
  • 5.6.3 空间划分的影响
  • 5.6.4 不同的哈希函数的个数
  • 5.6.5 查询索引的影响
  • 5.6.6 内存消耗
  • 5.6.7 与已有方法的比较
  • 5.7 本章小结
  • 第六章 高效的RDF查询优化
  • 6.1 引言
  • 6.2 相关工作
  • 6.3 图的分割和存储
  • 6.4 基于签名树的索引结构
  • 6.4.1 图的签名
  • 6.4.2 索引结构
  • 6.5 静态存储方式下的查询处理
  • 6.6 数据流上连续RDF查询处理
  • 6.6.1 连续查询的索引结构
  • 6.6.2 查询处理
  • 6.7 实验分析
  • 6.7.1 参数调试
  • 6.7.2 索引结构的影响
  • 6.7.3 不同分组数目(子图数目)的影响
  • 6.7.4 查询性能
  • 6.7.5 可测性
  • 6.7.6 连续查询优化策略的性能
  • 6.8 总结
  • 第七章 总结与展望
  • 7.1 本文工作的总结
  • 7.2 未来工作的展望
  • 参考文献
  • 攻读博士期间发表论文
  • 致谢
  • 相关论文文献

    标签:;  ;  ;  ;  ;  

    多数据类型的数据流查询处理及优化
    下载Doc文档

    猜你喜欢