随着无线通信技术的发展和智能终端的不断普及，基于位置的服务（Location-Based Services:LBS）迎来了新的发展契机，LBS市场呈现爆发式增长。作为LBS的核心技术之一，位置相关查询也随之成为学术界和工业界共同关注的热点问题。在众多的位置相关查询中，最近邻查询和反向最近邻查询被认为是最基础和应用最广泛的查询类型。最近邻查询既可以单独作为LBS服务来提供，比如查找最近的餐馆、酒店等，也可以作为基础技术为其他查询（如反向最近邻查询、窗口查询等）提供支持。反向最近邻查询在涉及到一个对象对其他对象的“影响范围”和“影响程度”时有很好的应用，比如在新建商场、医院等基础设施时的选址问题和现在很热门的针对性广告（targeted advertising）。　　现代社会路网（公路、铁路等）发达，人们的很多活动都发生在路网空间，比如导航、旅行等。同时，路网的发达也使得欧氏距离不再适用于估计对象间的距离，尤其是在路网密集的城市地区。因此，研究适用于路网的最近邻查询算法很有必要。另外，由于定位不精准、传输带宽限制、隐私保护等原因，不确定性在LBS中广泛存在。而简单的用点数据来代表位置不确定对象的做法通常会导致查询结果不够准确甚至出错。因此，很有必要研究路网中的基于位置不确定对象的最近邻查询。　　Voronoi图由于天然保存了最近邻信息，因此常常被用于处理最近邻和反向最近邻查询。虽然已有算法可以计算欧氏空间中基于不确定对象的Voronoi图和路网中基于确定对象的Voronoi图，但还没有算法用于构造路网空间中基于不确定对象的Voronoi图（Network Uncertain Voronoi Diagram:UNVD）。为了更深入、系统地研究UNVD，文中按照所划分空间的不同将UNVD分成node-UNVD、link-UNVD和area-UNVD三种类型，分别对应路网节点空间、路网边空间和由路网及路网所在平面构成的组合空间。并且，针对每一种类型的UNVD，首次提出了构造方法。算法MarkV用来构造node-UNVD，通过对每个路网节点赋予标签来记录当前的可能最近对象及其与路网节点间的距离范围，只需遍历一次路网便可求出所有路网节点的可能最近对象集合。相比基于最短路径的直观算法，MarkV可以减少80％的时间开销。在node-UNVD的基础上，对路网边进一步划分，使得每条子边上的点的可能最近对象相同，便得到link-UNVD。以link-UNVD中的Voronoi单元为生成对象来构造欧氏空间的线段Voronoi图即得到area-UNVD。　　本文首次给出路网空间中的概率最近邻（Network Probabilistic Nearest Neighbor:NPNN）查询处理方法。该方法利用预计算的link-UNVD来处理NPNN查询。首先，给出了公式用于计算结果对象成为最近邻的概率。然后，提出了四叉树结构的索引gIndex和哈希表索引qIndex来对link-UNVD的边、边的可能最近对象和该对象成为最近邻的概率进行索引。最后，基于提出的索引结构，分别给出了快照和连续的NPNN查询处理方法。实验结果显示，gIndex和qIndex在NPNN查询过程中的I/O性能和时间性能均优于其他索引技术。　　对于反向最近邻，介绍了一种新的查询类型，排序反向最近邻（Ordered Reverse k Nearest Neighbor:ORkNN）查询。与普通的反向最近邻相比，ORkNN查询的内容额外包括了“影响程度大小”信息，因此，利用ORkNN查询能够提供更加精准和人性化的服务。为了适应移动计算环境的需要，研究了在按需广播的环境中处理ORkNN查询的方法。该方法利用了高阶排序Voronoi图来处理ORkNN查询。通常情况下，预处理的Voronoi图不适合用来处理高阶反向最近邻查询，因为在k值提前不知道的情况下，需要预计算多个Voronoi图来应对k值不断变化的查询请求，从而造成极大的计算开销。该研究通过进一步开发高阶排序Voronoi图的性质，做到只需要预计算一个高阶排序Voronoi图即可处理所有的ORkNN查询请求，大大减少了预计算的开销。另外，由于已有的广播调度算法不适合用来处理按需广播下的ORkNN查询，提出了一个基于优先级的广播调度算法用来将ORkNN查询的结果高效地广播给客户端。实验结果表明，该广播调度算法在查询失败率和广播效率方面均优于其他算法。