不确定数据的概率近邻查询处理技术研究

《不确定数据的概率近邻查询处理技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文不确定数据的概率近邻查询处理技术研究作者姓名：李佳佳指导教师：王国仁教授申请学位级别：博士学科类别：工学学科专业名称：计算机系统结构论文提交日期：2014年09月04日论文答辩日期：2014年10月31日学位授予日期：答鹾委员会捕：张斌教授评阅人：杨晓春教授申德荣教授东北大学2014年10月万方数据ADissertationfortheDegreeofDoctorinComputerSystemandArchitectureStudiesonProbabilisticNearestNeighborQueriesoverU

2、ncertainDataJIUlIIIIIHIllllllllIJIIIY2989935byLIJiajiaSupervisor：WANGGuorenNortheasternUniversityOctober2014万方数据独创性声明本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其它人已经发表或撰写过的研究成果，也不包括本人为获得其它学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚的谢意。学位论文作者签名：磨f毛1々签字日期：立口f中．fO、弓f学位论

3、文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年峥／学位论文作者签名：彦彳毛i气导师签名：≥酬钞签字日期：9-o陟．p．弓I签字日期：讪I毕．，口、歹／万方数据一II—万方数据东北大学博士学位论文摘要不确定数据的概率近邻查询处理技术研究摘要随着无线通讯技术、全球定位系统和地理信息系统的快速发

4、展，大量如智能手机、平板电脑、车载GPS、动物遥测跟踪设备等具有定位功能的移动设备得以兴起并普及。这些用户在移动过程中产生的大量位置信息为基于位置的服务(LocationBasedServices，LBS)提供了所需的空间信息，使得LBS在越来越多的领域内都展现出了广泛的应用前景。近邻相关查询是LBS应用中最广泛的查询类型，有大量的文献对面向确定数据的查询技术进行研究。然而受到数据采集设备技术限制、移动物体延迟更新以及隐私保护等方面的原因，不确定数据普遍存在于近邻相关查询的应用中，一方面基于确定数据的近邻相关查询在不确定环境下仍然有许多应用场景，另一方

5、面基于确定数据的近邻查询技术无法直接应用到不确定环境下的查询，因此研究基于不确定数据的近邻相关查询技术不仅具有重要的理论意义，而且具有广泛的实际应用价值。基于不确定数据的近邻查询，返回的结果不仅包含数据对象本身，还包含其能够成为近邻查询结果的非零概率值，因此也称“概率近邻查询”。在查询中，为了计算出各个数据对象能够成为结果的概率，可能需要执行一些代价较高的积分运算或是指数级的枚举操作。而在多数应用下，发起查询的用户往往并不关心这些数据对象能成为结果的概率值，而更想知道有哪些对象有足够大的概率可以成为结果。因此，“概率阂值近邻查询”的概念被提出，即在查询

6、时用户给定一个概率阈值，查询返回能够成为近邻结果的概率大于该阈值的所有对象。目前，针对概率阈值近邻查询的研究已经取得了一些成果，但为了在更多的应用场景能够快速得到查询结果，还需要设计更多更高效的查询算法。本文基于离散模型的不确定数据，分析了现有研究成果的不足，提出了概率阈值反近邻查询和概率阈值组近邻查询的查询算法，并以概率阈值近邻和反近邻查询为例，提出了解决概率阈值查询中阈值设定问题的通用框架。本文的主要内容包括以下几个方面：(1)针对现有概率阈值反最近邻查询算法无法高效地支持概率阈值反．j}j丘邻查询(胗1)的情况，提出了基于空间距离关系和角度关系的

7、空间剪枝算法，和基于对象概率分布的概率剪枝算法。空间剪枝算法使用多个角度区间来定义剪枝区域，从而对成为结果概率为零的对象进行过滤，减少了诸如求垂直平分线、求线段或曲线的相交等空间几何的计算，因此能够很好地支持任意尼值的概率阈值反尼近邻查询。概率剪枝算法利用万方数据东北大学博士学位论文摘要了空间剪枝过程中产生的中间结果，先得到能够影响候选对象成为反逝邻查询结果概率的对象集合，再利用公式计算出该概率的上界值，通过与概率阈值不断进行比较来进行剪枝，进而得到更小的候选集合。(2)针对现有的概率阈值组最近邻查询算法在数据对象的不确定区域是不规则图形、用户指定的概

8、率阈值较小或较大以及查询集合点的分布较稀疏时，效率低下的问题，提出了不易受以上因素影响的空间剪