分布式序敏感查询处理关键技术研究

论文摘要

近年来,随着信息技术的迅猛发展,信息资源极大丰富。如何从海量数据中快速提取少量的最有价值的信息成为了数据库领域面临的一个重大挑战。在此背景下,数据库领域在最近几年产生了两个新兴的查询分支:top-k查询和轮廓查询。Top-k查询是根据用户指定的聚集函数查找聚集值最高的前k个对象;而轮廓查询则是查找不被其它对象“支配”的对象集。这两种查询为海量数据的查询处理提供了全新的思想和方法,得到了广泛的研究与应用。由于top-k查询和轮廓查询都是关注含有排序信息的结果集,在本文中我们把top-k查询和轮廓查询统称为序敏感查询。传统的数据库查询处理技术只能处理存储在磁盘或内存等介质中的静态数据,而在许多应用中,数据往往以是流的形式动态产生并且不被保存。这种数据模型被称为数据流模型。数据流模型所具有的无限、连续、快速、实时等诸多特征使得传统的数据库管理技术无法用于数据流的管理。数据流管理技术也因此成为了近年来数据库领域研究热点之一。如何支持数据流上的序敏感查询处理也正在得到越来越多的关注。为了区分数据库系统中的快照式查询处理和数据流系统中的连续的查询处理,在本文中我们将数据库系统中的查询处理称为快照查询处理,将数据流系统中的查询处理称为监测查询处理。随着计算机网络技术的发展,越来越多的数据资源产生或存储于网络之中。如何实现分布式数据资源上高效的序敏感查询处理成为了数据库研究领域的一个重要问题。目前,分布式序敏感查询处理技术已经取得了一些有价值的探索性成果,但是总体上还处于发展初期,在许多方面尚未成熟。在此背景下,本文针对已有工作的某些不足,着重对分布式top-k快照查询处理、分布式top-k监测查询处理和分布式轮廓快照查询处理技术展开深入研究,主要工作包括:1.分布式top-k快照查询处理方面。网络延迟对分布式快照查询处理的查询响应有着严重的影响,而已有的top-k快照查询处理算法对这一方面的考虑不足。针对这一问题,提出了一种实现非阻塞top-k快照查询处理的方法。该方法将异步的数据访问和渐进式的结果输出相结合,以获得快速的查询响应。基于该方法提出了一种非阻塞top-k快照查询处理算法PR及其改进型算法APR。理论分析表明,APR算法的平均网络流量低于现有同类算法,最大网络流量与现有同类算法相同;实验结果表明,APR算法在响应时间、执行时间和网络流量方面均优于现有同类算法。2.分布式top-k监测查询处理方面。分布式top-k监测查询处理的核心问题是如何减少监测过程中的网络流量。针对这个问题,对分布式top-k监测查询处理的特性进行了深入的理论分析,证明了发生约束冲突的对象集是重新建立监测约束时所需要的最小集,并提出了一种基于最小约束重建集的约束重建方法。该方法在重建约束时传输的对象为最少。基于该方法提出了一种面向求和运算的分布式top-k监测查询处理算法MR。理论分析表明,MR算法通讯代价与k无关;实验结果表明,当k不小于10时,MR算法的网络流量只有已有同类算法的10%～50%左右。另外,由于MR算法和已有同类算法都只支持求和运算作为top-k监测查询处理的聚集函数,而在实际应用中,用户给定的聚集函数可能是任意的单调聚集函数,为此,我们进一步提出了基于最小约束重建集的通用的分布式top-k监测查询处理方法。基于该方法提出了一种支持任意的连续的严格单调函数的分布式top-k监测查询处理算法GMR。理论分析表明,GMR算法的通讯代价是独立于k值;实验结果表明,GMR算法的网络流量比朴素的同类方法低一个数量级以上。3.分布式轮廓快照查询处理方面。如何在节点数较大时减少查询时的网络流量是分布式轮廓快照查询处理面临的一个重要问题。针对这个问题,提出了分阶段数据访问来降低网络流量的方法,并由此提出了一种四阶段分布式轮廓快照查询处理算法FDSL。实验表明,FDSL算法在节点数超过4时在网络流量方面优于同类算法。4.基于上述关键技术的研究探索,以海量数据处理中间件StarTPMonitor为支撑平台,设计并实现了面向海量信息的、支持分布式序敏感查询处理的分析查询处理引擎StarAnalysis。测试表明,StarAnalysis能够有效的支持海量数据上的分布式分析查询处理。综上所述,本文针对分布式序敏感查询处理的几个关键问题提出了有效的解决方案,对提高分布式序敏感查询处理的效率和实用化程度具有重要的理论意义和实用价值。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 应用需求
• 1.1.2 序敏感查询的提出
• 1.1.3 数据流模型和数据流上的序敏感查询处理
• 1.1.4 分布式序敏感查询处理技术
• 1.2 相关工作
• 1.2.1 Top-k 快照查询处理
• 1.2.2 Top-k 监测查询处理
• 1.2.3 轮廓快照查询处理
• 1.2.4 轮廓监测查询处理
• 1.2.5 其它相关技术
• 1.2.6 相关工作总结
• 1.3 本文的工作
• 1.4 论文结构
• 第二章 非阻塞Top-k 快照查询处理
• 2.1 分布式Top-k 查询处理
• 2.1.1 分布式Top-k 查询处理基本概念
• 2.1.2 已有Top-k 查询处理算法分析
• 2.2 非阻塞Top-k 查询处理基本方法
• 2.3 PR：非阻塞Top-k 查询处理算法
• 2.3.1 基本思想
• 2.3.2 PR 算法
• 2.3.3 正确性证明
• 2.3.4 性能分析
• 2.4 APR：自适应非阻塞Top-k 查询处理算法
• 2.4.1 性能影响因素
• 2.4.2 APR 算法
• 2.4.3 正确性证明
• 2.4.4 性能分析
• 2.5 实验
• 2.5.1 实验设置
• 2.5.2 PR 算法中步长因子的取值策略
• 2.5.3 性能比较
• 2.6 小结
• 第三章 基于最小约束重建集的分布式Top-k 监测查询处理
• 3.1 分布式top-k 监测
• 3.1.1 分布式top-k 监测模型
• 3.1.2 Babcock & Olston 算法
• 3.2 基于最小约束重建集的分布式Top-k 监测方法
• 3.3 MR：面向求和运算的分布式Top-k 监测算法
• 3.3.1 MR 算法
• 3.3.2 正确性证明
• 3.3.3 性能分析
• 3.3.4 冲突集过大时的处理策略
• 3.3.5 实验
• 3.4 GMR：通用分布式Top-k 监测算法
• 3.4.1 通用分布式Top-k 监测方法
• 3.4.2 GMR 算法
• 3.4.3 正确性证明
• 3.4.4 性能分析
• 3.4.5 实验
• 3.5 小结
• 第四章 四阶段分布式轮廓快照查询处理
• 4.1 分布式轮廓查询处理
• 4.1.1 分布式轮廓查询处理基本概念
• 4.1.2 已有轮廓查询处理算法分析
• 4.2 FDSL：四阶段分布式轮廓查询处理算法
• 4.2.1 分阶段数据访问的轮廓查询处理方法
• 4.2.2 FDSL 算法
• 4.2.3 正确性证明
• 4.3 实验
• 4.3.1 实验设置
• 4.3.2 预取因子的取值策略
• 4.3.3 与同类算法的比较
• 4.4 小结
• 第五章 面向海量信息的分析查询处理引擎
• 5.1 面向海量信息处理的基础软件平台－StarTPMonitor
• 5.1.1 StarTPMonitor 总体结构
• 5.1.2 数据加载服务
• 5.1.3 查询处理服务
• 5.2 StarAnalysis 系统框架
• 5.3 核心功能的设计与实现
• 5.3.1 加载数据流的监测查询处理
• 5.3.2 定时统计
• 5.3.3 分析快照查询处理
• 5.4 性能评测
• 5.4.1 测试环境
• 5.4.2 测试结果
• 5.5 小结
• 结束语
• 致谢
• 参考文献
• 作者在学期间取得的学术成果