不确定数据上的最近邻查询方法研究

论文摘要

不确定数据的查询处理已成为数据库领域近年来的一个新的热点研究课题。由于目前已有的不确定数据的查询处理方法还不完善，有些查询处理还未被研究到，因此，本文提出并研究了不确定数据上的最近邻查询和范围受限的最近邻查询问题。首先，由于目前已有的不确定数据上的最近邻查询方法，对于取样点分布比较密集的数据集，不能进行集中处理，提出了一种改进的不确定数据上的最近邻查询方法。用K均值聚类的方法，将每个不确定数据的取样点集合划分成几个点簇的形式，用R树将点簇表示的数据集存储起来。通过对R树的遍历，形成符合特定条件的有序列表，有序列表的每一项可以是取样点、点簇，或者不确定数据。在有序列表的展开过程中，根据取代关系，逐步画出取代关系图，通过对取代关系图的裁剪和校验找出最终的结果集。其次，由于确定数据上的范围受限的最近邻查询算法，不能直接应用到不确定数据上，提出了不确定数据上的范围受限的最近邻查询问题。为解决该问题，提出了范围受限的最近邻核心集的概念和核心集的查找算法。首先找到范围受限的最近邻候选集的有序列表，在对候选集的有序列表的逐步展开过程中，画出范围受限的取代关系图，通过对取代关系图的逐步裁剪和校验，最后取得范围受限的最近邻核心集。在计算范围受限的最近邻候选集的过程中，还提出了三种裁剪策略。最后，对以上提出的两种查询方法，采用均匀分布和正态分布的两种不确定数据集进行了实验测试，测试结果验证了两种查询算法的有效性和实用性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.2.1 不确定数据上的最近邻查询研究现状
• 1.2.2 不确定数据上的范围查询研究现状
• 1.3 研究内容
• 1.4 论文结构
• 第2章 基础知识
• 2.1 引言
• 2.2 不确定数据
• 2.2.1 不确定数据的定义
• 2.2.2 不确定数据的模型
• 2.2.3 不确定数据产生的原因
• 2.3 不确定数据的索引技术
• 2.3.1 概率域值索引技术
• 2.3.2 U-Tree 索引技术
• 2.4 不确定数据上的最近邻查询
• 2.4.1 概率最近邻查询
• 2.4.2 取代最近邻查询
• 2.5 本章小结
• 第3章 不确定数据上的最近邻查询算法
• 3.1 引言
• 3.2 问题定义
• 3.3 算法
• 3.3.1 索引结构
• 3.3.2 算法描述
• 3.4 本章小结
• 第4章 不确定数据上范围受限的最近邻查询算法
• 4.1 引言
• 4.2 问题定义
• 4.3 算法
• 4.3.1 范围受限的最近邻候选集的有序列表
• 4.3.2 范围受限的最近邻查询算法
• 4.4 本章小结
• 第5章 实验结果与分析
• 5.1 实验环境设置
• 5.2 最近邻查询算法实验
• 5.2.1 实验内容
• 5.2.2 实验结果与分析
• 5.3 范围受限的最近邻查询算法实验
• 5.3.1 实验内容
• 5.3.2 实验结果与分析
• 5.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间承担的科研任务与主要成果
• 致谢
• 作者简介