不确定数据的世系管理和相似性查询

论文摘要

不确定性数据在很多应用中广泛出现,例如经济、军事、物流、金融、电信等,其表现形式多种多样,包括关系型数据、半结构化数据、图数据、流数据、移动对象数据以及无结构化的Web数据等。目前,根据应用的特点与数据形式的多样性,已经出现了多种不确定数据模型,这些模型的核心思想都源自可能世界模型。该模型从一个不确定的数据源演化出诸多确定性的可能世界实例,所有实例的概率之和等于1。尽管可以针对各个实例单独进行查询处理,合并中间结果并获取最终结果,但是可能世界实例的数量远大于不确定数据库的规模,从而导致可能世界模型在实践应用中并不可行。因此必须采用排序、剪枝等启发式技术进行优化处理以提高查询处理效率。针对不确定数据管理的挑战,本文主要考察不确定数据查询处理的优化。主要工作分为两部分：不确定数据世系管理和相似性查询。具体的,针对数据的不确定性,研究如何通过不确定数据的世系追踪数据不确定性的来源和大小,以及对不确定性集合数据进行相似度评价,最后提出了不确定数据流上ER-topk查询的精确算法。本文的主要贡献如下：●首先研究了如何利用数据世系追踪数据不确定性的来源和大小。基于PHP-tree数据结构,近似描述不确定数据的How世系,避免了追踪数据演化的中间结果,同时也避免了运用可能世界模型对不确定性数据进行建模；基于PHP-tree,可以追踪日标数据的不确定性来源,以及对目标数据的不确定性大小进行评价。·针对不确定集合,定义了不确定性集合的期望相似度算子,提出了不确定集合期望相似度的精确和近似算法。具体的,运用动态规划方法在多项式时间内给出不确定集合期望相似度的精确算法,而不必扩展可能世界实例；考虑到精确算法需要耗费大量的时间和空间,为克服可扩展性差的缺点,我们运用Monte-Carlo方法在线性时间内近似计算不确定集合的期望相似度。●考虑到不确定集合相似度的多样性,又评价了不确定性集合的概率阈值相似度。给出了不确定集合的概率阈值相似度算子的定义,以及精确和近似算法。运用动态规划方法在多项式时间内给出不确定集合概率阈值相似度的精确计算过程；同时考虑到概率阈值相似度的计算结果是一个概率值,当用户给定相似度的阈值,利用尾概率不等式提出了一个线性时间内的剪枝规则,大大加快了精确解的计算过程；考虑到没有被剪枝的不确定集合的精确算法需要耗费大量的时间和空间,我们运用Monte-Carlo方法近似计算不确定集合的概率阈值相似度。●基于界标模型提出了不确定数据流响应ER-topk查询的精确算法,该方案将所有不断到来的元组分成两组,一组包含ER-topk查询的候选结果,剩下的元组包含在另外一组中,我们分别用数据结构domGraph和probTree来维护这两类元组；基于期望的线性性,我们避免了扩展所有可能世界实例,在次线性时间内给出查询的结果。本文研究了不确定数据的查询处理,主要工作包括不确定数据世系管理和不确定数据的相似性查询,通过大量的实验验证了提出算法的效率和可扩展性等。

论文目录

• 目录
• 图目录
• 表目录
• 摘要
• Abstract
• 第一章 绪论
• 1.1 不确定数据的典型应用
• 1.1.1 传感器网络
• 1.1.2 射频识别技术
• 1.1.3 Web应用
• 1.1.4 移动对象数据管理
• 1.2 不确定数据的产生原因
• 1.3 不确定数据的管理框架及面临挑战
• 1.3.1 框架
• 1.3.2 挑战
• 1.4 本文内容和主要贡献
• 1.5 本文组织结构
• 第二章 预备知识和相关工作
• 2.1 不确定数据模型
• 2.1.1 可能世界模型
• 2.1.2 关系模型
• 2.1.3 XML数据模型
• 2.1.4 图数据模型
• 2.1.5 流数据模型
• 2.2 典型查询
• 2.2.1 关系数据查询
• 2.2.2 XML查询
• 2.2.3 图数据查询
• 2.3 相似性查询
• 2.3.1 相似性连接查询
• 2.3.2 Top-k查询
• 2.3.3 范围查询和KNN查询
• 2.3.4 Skyline查询
• 2.4 数据世系的管理
• 2.4.1 不确定性数据世系应用举例
• 2.4.2 实例数据的世系
• 2.4.3 不确定性数据的世系
• 2.5 不确定数据管理原型系统
• 第三章 不确定数据的How世系管理
• 3.1 背景
• 3.2 预备知识
• 3.2.1 How世系
• 3.2.2 概率数据库上的How世系
• 3.2.3 概率数据库上How世系的性质
• 3.3 概率评价
• 3.3.1 PHP-tree结构
• 3.3.2 评价概率
• 3.4 实验分析
• 3.4.1 实验环境和相关参数
• 3.4.2 PHP-tree的构建效率
• 3.5 本章小结
• 第四章 不确定集合的期望相似度
• 4.1 问题定义和数据预处理
• 4.1.1 不确定集合相似度算子定义
• 4.1.2 数据预处理和重要符号说明
• 4.2 精确算法
• 4.2.1 ESS-Jaccard相似度
• 4.2.2 ESS-Dice相似度
• 4.2.3 ESS-Cosine相似度
• 4.2.4 性能分析和优化
• 4.2.5 基于包语义不确定集合的期望相似度
• 4.3 近似算法
• 4.3.1 算法描述
• 4.3.2 响应其他模型
• 4.3.3 性能分析
• 4.4 实验分析
• 4.4.1 实验环境和相关参数
• 4.4.2 精确算法的有效性
• 4.4.3 近似算法的性能分析
• 4.4.4 近似算法在其他模型上的性能
• 4.5 本章小结
• 第五章 不确定集合的概率阈值相似度
• 5.1 问题定义和数据预处理
• 5.1.1 不确定集合概率阈值相似度算子的定义
• 5.1.2 数据预处理和重要符号说明
• 5.2 精确算法
• 5.2.1 PTSS-Jaccard相似度
• 5.2.2 PTSS-Dice相似度
• 5.2.3 PTSS-Cosine相似度
• 5.3 PTSQ的剪枝算法
• 5.3.1 剪枝规则
• 5.3.2 剪枝算法描述
• 5.3.3 包语义不确定集合的剪枝规则
• 5.4 近似算法
• 5.5 实验分析
• 5.5.1 实验环境和相关参数
• 5.5.2 精确算法的有效性
• 5.5.3 剪枝效率的比较
• 5.5.4 近似算法的性能分析
• 5.6 本章小结
• 第六章 不确定数据流上的ER-topk查询
• 6.1 背景
• 6.2 数据模型和查询定义
• 6.3 解决方案
• 6.3.1 domGraph
• 6.3.2 probTree
• 6.3.3 响应查询需求
• 6.4 实验分析
• 6.4.1 实验环境和相关参数
• 6.4.2 空间效率
• 6.4.3 时间效率
• 6.5 本章小结
• 第七章 总结与展望
• 7.1 本文工作的总结
• 7.2 未来工作的展望
• 参考文献
• 攻读博士期间发表或完成的论文
• 致谢