论文部分内容阅读
在移动对象数据库(MOD)、基于位置的服务(LBS)和地理信息系统(GIS)等领域中,受定位设备精度、更新策略和具体应用(如位置隐私保护等)的影响,位置不确定性广泛存在且不可避免。这使得在移动对象数据管理中必须考虑位置的不确定性。本文主要对不确定移动对象数据管理中几类查询的处理技术进行了研究,并给出了相应研究成果。论文主要在以下几个方面取得了进展。(1)定义了不确定数据库环境下的移动对象概率距离范围(PUDR)查询问题,提出了基于范围的查询扩展、结点扩展和基于距离的剪枝策略及算法,有效地用于查询处理。首先针对搜索范围由距离阈值和查询发出者的不确定域共同决定的特点,将不确定目标对象和不确定搜索区域之间的拓扑关系分成6类,推导出每一类情况下的概率计算方法。然后利用对象不确定域的几何形状及概率特性设计了一系列查询处理算法。在各种参数设置下,通过实验对算法的性能进行了验证,结果表明:提出的概率计算方法在时间代价和精度上,均优于现有研究工作中普遍采用的Monte-Carlo方法;3种算法中基于距离的算法性能最优,能够有效地处理PUDR查询问题。(2)指出了不确定性和模糊性在语义上的区别,将两者同时引入到移动对象的查询处理中,提出并研究了两类新型的查询,即模糊距离范围(FDR)查询和模糊时空范围(FSTR)查询,分别设计了基于时间区间和基于距离的剪枝策略及相应的算法,有效地用于查询处理。首先用概率密度函数表示对象位置的不确定性,用模糊集表示查询条件中模糊的空间和时间谓词。给出了对象关于查询条件匹配度的计算方法。针对两类问题,利用模糊距离阈值的-截集设计了通过时间区间和距离剪枝的查询处理算法。通过实验验证并分析了对象的不确定性、模糊的空间谓词和时间谓词等因素对算法性能的影响,结果表明所提出的算法具有良好的效率和可扩展性。(3)在不确定数据库环境下,提出并研究了单数据集上的相互最近邻查询问题,根据相互最近邻是最近邻的子集这一特点设计了查询处理算法。首先给出了不确定相互最近邻(UMNN)的性质和概率计算方法。然后设计了基于最小最远距离界限(MinFDB)规则的剪枝策略用于查询处理。针对概率计算中对象的重复采样问题,提出了基于采样列表的优化策略。在合成数据集上对算法的性能进行了验证,实验结果表明数据分布、数据集大小、不确定性域大小等因素对UMNN查询结果及算法性能均有影响,此外采样优化策略可以提高查询处理的效率。(4)提出了道路网环境下查询和目标位置均不确定的距离范围查询问题,设计了基于路网的不确定对象和不确定查询范围分析(NU2RA)方法,用于解决各类对象的概率计算问题。该方法首先建立了不确定对象在道路网中的距离模型,然后根据查询范围对路网进行划分,用分布码表示目标的可能分布情况,得到不确定目标与不确定查询范围之间的22类拓扑关系,最后推导出了目标在不确定查询范围内的概率计算方法。该方法不依赖于具体的不确定移动对象模型,只要对象的可能位置范围表现为路网中的简单路段即可,对不确定历史轨迹和不确定的近期将来运动趋势同样适用。