近年来,随着互联网技术的飞速发展,基于地理位置信息的服务（Location-Based Services,简称LBS）受到越来越多的关注,而在LBS中,kNN（top-k nearest neighbors）查询是最经典也是最常用的一种查询模式,kNN查询可以筛选出距离查询点最近的k个对象。目前已有很多关于kNN查询问题的研究成果,但是,现有的研究成果都存在着缺陷和不足,或是索引的存储代价太高,或是查询算法的效率太低,亦或是索引的建立受限于k值,不能够灵活响应k值的变化,无法满足大型路网数据集上的高效查询。本文针对道路网络上的kNN查询进行研究,基于树分解的概念,提出了一种新的基于树分解的无参数的kNN查询解决方案,现有的无参数索引大多基于网格索引、分层索引以及GTree等,本文所提的无参数索引结合了树分解的高效,构建索引的效率更高,基于本文的索引结构,提出了一种高效的路网上kNN查询算法。最后,在多个真实的路网数据集上进行了大量的实验,证明了本文所提出的算法的高效性。本文的贡献总结如下:（1）针对索引不能适应k值变化的问题,本文提出了新的kNN索引——AWTDAC,该索引是一个无参数索引,打破了k值的限制,具有更高的适用性。（2）针对kNN查询算法效率低的问题,本文提出了新的树分解构造算法和kNN查询算法——AWTDN,传统树分解基于最小度原则,本文在其基础上进行改进,使用平均权重原则进行构造,在平均情况下,路网上相近的点,在平均权重树分解中也相近。基于平均权重原则构建的树分解,会使得位于其他任意两点之间最短路径中的顶点更大可能的出现在树分解的上层,这样树分解中就存储了真实的最短距离,可以提高后续kNN查询的效率。（3）针对索引存储代价高的问题,我们在AWTDAC的基础上进行了优化,以节点扩展列表替代了祖先表和孩子表,压缩了索引的存储成本,同时进一步提高了查询算法的效率。