基于概率图地概率反向近邻查询研究

《基于概率图地概率反向近邻查询研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江大学硕士学位论文摘要空间数据查询处理技术是数据管理的关键技术，一直受到学术界和工业界的大量关注。作为空间数据的一类重要查询，反向最近邻查询(RNN)及其变种在决策支持、资源分配等重要领域拥有广泛的应用场景。已有的反向最近邻查询工作主要集中于基于欧氏空间或确定图模型的RNN查询，而并没有关注概率图模型的RNN查询。然而，在许多现实应用场景中，由于设备误差、道路拥堵状况、网络延时等因素造成图模型中的数据具有不确定性。通常，这些场景可以采用边权重不确定的概率图进行建模。本文主要研究基于概率图的概率反向近邻查询(PRNN)：给定一个查询点g和一个概率阈值了，PRNN查询返回以查询点作为概率最近邻(

2、PNN)的所有数据点。实现基于概率图的概率反向近邻查询具有极大的技术挑战，其原因在于(1)概率图模型中的距离度量方式不同于欧式空间以及确定图模型中的距离度量方式；(2)不同于确定图模型，概率图中的路径不满足最优子结构。本文首先形式化定义了PRNN查询。基于基本剪枝策略，本文提出了基于深度优先搜索的PRNN查询处理算法。其次，为了更高效地处理PRNN查询，本文进一步提出了三种优化方案：(1)联合使用基本剪枝策略和扩展剪枝策略的PRNN查询处理算法；(2)可加速PRNN查询处理的预计算物化方法；(3)具有较低误差率的高效近似PRNN查询算法。最后，本文通过大量实验验证了PRNN查询处理算法的高效性

3、。关键词：不确定性，概率图，概率反向最近邻，概率反向k近邻，查询优化浙江大学硕士学位论文AbstractInrecentyears，awidevarietyofspatialquerieshavegainedsignificantresearchandindustrialinterest．Oneimportanttypeofspatialqueriesisthereversenearestneighbor①Ⅻ叼query,whichhasgivenbirthtovariouspracticalapplicationsincludingdecisionsupport,resourcealloca

4、tion,etc．RNNqueryhasbeenstudiedquiteextensivelyintheEuclideanspaceaswellasthedeterministicgraphspace．However,alargeportionofreal—lifedataisessentiallyuncertainbecauseoftheequipmenterror,roadcongestionandnetworklatency,etc．ThesekindsofdataCanbemodeledasaprobabilisticgraphwi也uncertainlyweightededges．W

5、estudytheprobabilisticreversenearestneighborfiRNN)queryinthispaper．GivenaquerypointqandaprobabilitythresholdLaPRNNqueryretrievesallthedatapointsthathaveqastheirprobabilisticnearestneighborfINN)．ExistingmethodsareinapplicabletoPRNNquery,themainreasonsare：(1)ThedistancemeasureisdifferentbetweentheEucl

6、ideanspacebasedRNNqueryandtheprobabilisticgraphbasedPRNNquery；(2)ComparedtOdeterministicgraphs，pathsinprobabilisticgraphdonotsatisfythesub-optimalitystructure，whichposesnewchallengesonansweringPRNNqueries．Inthispaper,wepresentandformallydefinePRNNqueryforthefirsttime，andproposedadepth—firstbasedPRNN

7、processingalgorithm．Furthermore，wepresentthreeoptimizationstOspeedupPRNNqueryprocessing：(1)First,wecombinethebasicandextendedpruningstrategiesasanoptimizationofthePRNNalgorithm；(2)Weproposeamaterializ