不确定数据近邻搜索算法的设计与实现

《不确定数据近邻搜索算法的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号⋯⋯⋯⋯⋯⋯．UDC密级⋯公⋯五⋯。Z秀庐夕擎硕士研究生学位论文不确定数据近邻搜索算法的设计与实现申请人：学号：培养单位：学科专业：研究方向：指导教师：完成日期：阚斌2121430计算机科学技术学院计算机技术不确定数据库朱敬华副教授2014年4月中文摘要l愀嬲数据的不确定性在许多领域中的具体应用中普遍存在，不确定数据受到越来越多的关注。引起数据不确定性的原因多种多样。原始数据不准确或者使用粗粒度集合都会导致数据的不确定性，此外，出于隐私保护等特殊目的以及处理缺失值都可能成为数据不确定性的原因。如何管理好不确定性数据成为近年来数据库领域

2、中研究的热点问题。不确定数据查询是不确定数据管理的重要组成部分。本文研究不确定数据近邻搜索算法，针对不确定数据如何进行有效的近邻查询，在分析总结国内外相关研究的基础上，提出了不确定数据上的组反k近邻查询和预测近邻查询的解决方案。反k近邻查询在基于位置的服务中应用广泛，如智能导航、决策支持等。目前反k近邻查询大多针对单一查询点进行处理。本文把针对单一查询点扩展到了针对一组查询点，提出了概率阈值组反k近邻查询算法PT-GRkNN。算法利用R木一tree索引结构，使用过滤提纯框架，逐步缩减查询搜索空间，降低计算开销。实验表明，PT．GRkNN算法

3、可以有效地过滤非结果集对象，提高查询结果的精确度。时空数据上的预测近邻查询在许多基于位置的服务中受到重视。由于像RFID、传感器以及GPS等数据采集设备不够精准等原因的限制，数据只能在离散的时间点被采集。在这些离散的时间实例之间，被追踪的移动对象的位置是不确定的。本文利用过滤提纯框架来解决不确定时空数据上的预测最近邻查询。在过滤阶段，利用半马尔科夫过程模型来描述对象在空间网格之间的移动，过滤掉零概率成为查询结果的对象。在提纯阶段使用马尔科夫链模型来描述不同空间点之间移动对象的移动性，并对此时数量不多的候选对象计算最近邻概率。实验表明该方法以

4、数量级优于已有的基于索引的方法。关键词：不确定性数据；可能世界；组反k近邻；概率最近邻黑龙江大学硕士学位论文AbstractDatauncertaintyisprevalentandexistsinapplicationsofmanyfields．Uncertaindatahasreceivedincreasingauention．Thereasonswhyuncertaindataareproducedarevarious．Rawdata’imprecisionorusinggroupgranularitywillleadtouncert

5、aintyinthedatacollection．Inaddition，aspecialpurposeforprivacyprotectionandhandlingmissingdatavaluesmaybethereasonsfortheuncertainty．Howtodealwithuncertaintiesinthedatareallybecomeahotissueinrecentyearsinthefieldofdatabaseresearch．Inthispaper，westudythenearestneighborquerie

6、sprocessingalgorithmsfortheuncertaindata．TheintroductionofdatauncertaintyleadstOtheimproperoftraditionalmethods．Sotraditionalmethodsisnotdirectlyapplicabletoqueryprocessingonuncertaindata．Andthispapergivesthesolutionsofgroupreverseknearestneighborqueryandpredictivenearestn

7、eighborqueryonuncertaindata．Reverseknearestneighborqueryplaysanimportantroleinlocation-basedservicestoevaluatetheinfluenceofobjects．Currently，mostofmethodsforthereverseknearestneighborqueryonlyconsiderthesinglequerypoint．Therefore，inthispaper，weproposetheprobabilisticthres

8、holdgroupreverseknearestneighborqueryprocessingalgorithm(PT-GRkNN)foruncertaindatatOevalu