随着无线通讯技术、全球定位系统和地理信息系统的快速发展,大量如智能手机、平板电脑、车载GPS、动物遥测跟踪设备等具有定位功能的移动设备得以兴起并普及。这些用户在移动过程中产生的大量位置信息为基于位置的服务(Location Based Services,LBS)提供了所需的空间信息,使得LBS在越来越多的领域内都展现出了广泛的应用前景。近邻相关查询是LBS应用中最广泛的查询类型,有大量的文献对面向确定数据的查询技术进行研究。然而受到数据采集设备技术限制、移动物体延迟更新以及隐私保护等方面的原因,不确定数据普遍存在于近邻相关查询的应用中,一方面基于确定数据的近邻相关查询在不确定环境下仍然有许多应用场景,另一方面基于确定数据的近邻查询技术无法直接应用到不确定环境下的查询,因此研究基于不确定数据的近邻相关查询技术不仅具有重要的理论意义,而且具有广泛的实际应用价值。基于不确定数据的近邻查询,返回的结果不仅包含数据对象本身,还包含其能够成为近邻查询结果的非零概率值,因此也称“概率近邻查询”。在查询中,为了计算出各个数据对象能够成为结果的概率,可能需要执行一些代价较高的积分运算或是指数级的枚举操作。而在多数应用下,发起查询的用户往往并不关心这些数据对象能成为结果的概率值,而更想知道有哪些对象有足够大的概率可以成为结果。因此,“概率阈值近邻查询”的概念被提出,即在查询时用户给定一个概率阈值,查询返回能够成为近邻结果的概率大于该阈值的所有对象。目前,针对概率阈值近邻查询的研究已经取得了一些成果,但为了在更多的应用场景能够快速得到查询结果,还需要设计更多更高效的查询算法。本文基于离散模型的不确定数据,分析了现有研究成果的不足,提出了概率阈值反近邻查询和概率阈值组近邻查询的查询算法,并以概率阈值近邻和反近邻查询为例,提出了解决概率阈值查询中阈值设定问题的通用框架。本文的主要内容包括以下几个方面：(1)针对现有概率阂值反最近邻查询算法无法高效地支持概率阈值反舾邻查询(k>1)的情况,提出了基于空间距离关系和角度关系的空间剪枝算法,和基于对象概率分布的概率剪枝算法。空间剪枝算法使用多个角度区间来定义剪枝区域,从而对成为结果概率为零的对象进行过滤,减少了诸如求垂直平分线、求线段或曲线的相交等空间几何的计算,因此能够很好地支持任意k值的概率阈值反k近邻查询。概率剪枝算法利用了空间剪枝过程中产生的中间结果,先得到能够影响候选对象成为反k近邻查询结果概率的对象集合,再利用公式计算出该概率的上界值,通过与概率阈值不断进行比较来进行剪枝,进而得到更小的候选集合。(2)针对现有的概率阈值组最近邻查询算法在数据对象的不确定区域是不规则图形、用户指定的概率阈值较小或较大以及查询集合点的分布较稀疏时,效率低下韵问题,提出了不易受以上因素影响的空间剪枝和概率剪枝策略来解决概率阈值组最近邻问题,并为不确定对象设计了新型的局部索引来加快概率剪枝速度。基于增量搜索的空间剪枝算法为查询集合中的每个查询点依次找到可能的近邻结果,再通过合并中间结果来对不确定对象进行过滤。基于质心的空间剪枝算法使用点集的质心来代替查询集合,从而减少了距离的计算量,并利用提出的最大-/最小距离剪枝准则对不确定对象进行过滤。概率剪枝阶段则通过对数据对象不确定区域的分割来得到若干个子区域,进而计算出对象能够成为查询集合点的组最近邻查询结果的概率上界和下界,再进行过滤和确认。最后,将所提出的剪枝算法扩展至解决概率阈值组k近邻查询(k>1)的问题。(3)现有的与概率阈值查询有关的研究工作,大多集中在如何设计高效的剪枝算法来提高查询效率,但阈值的设定问题是概率阈值查询算法中一个重要却被忽视的阶段。阈值设置得过小,可能会导致返回结果过多；而阈值设置得过大,又可能会使返回的结果集为空。针对概率阈值查询中普遍存在的阈值设定的问题,提出了新的基于极限学习机进行阈值分类的概率阈值查询处理通用框架。该框架允许用户直接输入想得到的结果数目区间,使用阈值分类的方法将这个数目区间转变成合理的阈值,再利用原有的概率阂值查询算法执行查询过程。该框架适用于各个类型的概率阈值查询算法,除了设定阈值的方式不同,其余阶段都可以与现有的概率阈值查询算法相兼容。此外,还以概率阈值近邻和反近邻查询为例,研究了影响对象成为查询结果概率值的因素,并为两种查询类型分别选取了有用的特征,最后利用该框架解决了相应的查询处理问题。在分类过程中,还提出了多数投票方法、阈值调整算法以及基于滑动窗口的动态策略等来提高分类的速度和精度。综上所述,针对不确定数据环境下的近邻查询问题所面临的挑战,本文分别提出了不确定数据的概率反近邻和组近邻查询算法以及概率近邻和反近邻的查询处理优化算法。实验结果表明,本文所提出算法的查询性能优于现有算法。