一种局部相关不确定数据库快照集合上的概率频繁最近邻算法

摘要：

局部相关空间不确定数据越来越受到许多实际应用的关注.提出了一种新颖的定义在不确定数据库的多个快照上的概率频繁近邻查询,目的是在多个快照数据上找到以一定概率频繁成为查询点最近邻的那些对象.应用现有的基于传统数据和基于不确定数据上的近邻查询算法直接处理这种查询会产生昂贵的开销.为了很好地解决这一问题,提出了一般的处理框架,其中包括相应的基于切尔诺夫界的过滤方法,以及对于概率质量函数的动态规划算法.给出了分别作用于两个阶段的两个过滤方法.在第1阶段,利用切尔诺夫界的上界推广形式可以过滤大量的候选目标,之后在第2阶段,利用切尔诺夫界的标准形式来进一步过滤候选目标.还讨论了用于处理扩展查询的动态规划算法以及相应的过滤条件.最后,在人工的和真实的数据上都进行了充分的实验,并验证了给出算法的有效性,为进一步的研究工作奠定了基础.

关键词：不确定数据库、快照、局部相关性、概率频繁、最近邻查询

所属期刊栏目：48

分类号：TP311.13(计算技术、计算机技术)

资助基金：国家自然科学基金项目60703012;国家自然科学基金重点项目60933001

在线出版日期：2012-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：1812-1822