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

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

1、硕士学位论文题目:不确定数据的组最近邻查询方法研究研究生王伟阁专业计算机技术指导教师徐建教授完成日期2016年3月杭州电子科技大学硕士学位论文不确定数据的组最近邻查询方法研究研究生：王伟阁指导教师：徐建教授2016年3月DissertationSubmittedtoHangzhouDianziUniversityfortheDegreeofMasterTheResearchonMethodsforGroupNearestNeighborsQueryonUncertainDataCandidate:We

2、igeWangSupervisor:Prof.JianXuMarch,2016抗州电子科技大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明；所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体己经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中明确方式标明。一申请学位论文与资料若有不实之处，本人承担切相关责任。＊＾论文作者签名；足日期：１６年多月日＾学位论

3、文使用授权说明本人完全了解杭州电子科技大学关于保留和使用学位论文的规定，即；研究生在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可公布论文、缩印或其它复制手段保存论文。（的全部或部分内容，可允许采用影印保密论文在解密后遵守此规定）４论文作者签名：寺争呵曰親Ｗ占年＾月曰３指导教师签名：日期：年＾月曰）摘要移动设备的普及使

4、得基于位置的查询成为当前的一个热门研究。然而由于数据采集时的误差、测量设备的精确度、更新时的延迟以及隐私保护等原因,在各种基于位置查询的应用中产生了大量的不确定数据。目前对于确定数据上的各类查询问题已得到了相对成熟的研究，而对于不确定数据上的查询，处理方法还不够完善。因此，本文针对不确定数据的组最近邻查询，进行了研究。不确定数据的组最近邻查询即概率组最近邻（PGNN）查询。PGNN查询检索的是成为查询点集的最近邻的概率值大于等于用户指定阈值的所有不确定数据对象。目前对于PGNN查询的研究主要集中在欧式

5、空间，现有的PGNN查询算法ISPR存在数据检索的范围大和距离计算量大的问题。本文针对这些存在的不足，提出了一种基于Voronoi图的PGNN查询算法VPGNN。该算法使用Voronoi图的预计算技术和邻接性，可以在不计算距离的情况下，大大缩小候选集的选取范围。算法第一步结合不确定数据对象的Voronoi图和查询点集的凸包构建出一个影响区域，来确定查询结果的候选集。第二步使用空间剪枝来缩小上一步得出的候选集，以此来减少参与概率计算的目标对象的个数。第三步给出不确定数据对象成为组最近邻的概率值的计算公式

6、，并将其作用在那些少量的无法被空间剪枝算法修剪掉的目标对象上。同时在大数量查询点的情况下，为了进一步提高算法的响应速度，本文又提出了一种基于不确定Voronoi图的快速PGNN查询算法UVPGNN。该算法通过引入一种Voronoi图的变体结构不确定Voronoi图来处理PGNN查询，利用不确定Voronoi图的性质可以进一步缩小候选集的选取范围。其第一步通过对查询点进行分组，选出组内的代表查询点，以此来减少参与计算的查询点数量。第二步是根据不确定Voronoi图和查询点凸包的相交区域来确定查询候选集。

7、第三步对查询候选集进行距离修剪并提纯。本文针对以上所提出的两种算法分别进行了理论分析和实验证明。对比实验使用合成的数据集在几组不同参数值下进行，其结果表明基于Voronoi图的PGNN查询算法VPGNN在查询时间上优于现有的PGNN查询算法。基于不确定Voronoi图的快速PGNN查询算法UVPGNN在查询精确度降低不明显的情况下，其查询效率明显优于算法VPGNN。关键词：不确定数据，Voronoi图，概率组最近查询，不确定Voronoi图IABSTRACTThepopularityofmobiled

8、evicesmakesthequeryserviceofthespatiallocationhavegraduallygonedeepintopeople’slives.Meanwhileattractalargenumberofresearcherstostudytheissue.Whilebecauseoftheerrorofdatacollectionandmeasuringequipment,delayeddataupdateorprivacyp