随着移动计算、无线通信以及定位技术的快速发展,大量的应用领域,如交通、商贸、物流、气象、军事等,积累了巨大的空间数据。人们迫切需要对这些数据进行各种查询分析以便发现其隐藏的知识或做出正确的决策。本文首先分析了利用传统的树索引和网格索引进行K-NN查询的优缺点,基于树索引的K-NN算法,采用测量距离和剪枝策略提高查询效率,在继续查找下一近邻时,往往需要大量的距离计算以便排除不必要的查找区域,在数据量庞大的情况下,频繁的计算距离所花费的时间代价很大,算法查询效率急剧下降,基于网格索引的K-NN查询算法,通过计算被查询对象与其周围八个网格中的对象距离,获取近邻对象,并一层层向外扩大查询范围,查询范围不灵活,会出现空网格单元使得近邻对象的查询次序与实际排序顺序不一致,致使搜索缓慢,存储利用率低。本文提出了基于动态矩形遍历搜索的K-NN查询算法,采用聚类方法将空间数据对象聚类到被查询对象所在的水平和竖直方向,选择大小合适的矩形动态进行移动以获取下次进行查询的范围,采用动态矩形进行遍历搜索K-NN对象,由于将数据对象进行聚类,使得每类中数据对象间距变小,动态矩形在每个方向的查询区域不为空,节省了存储空间,采用要查找的K-NN对象数目来选取动态矩形的大小,排除了人为性,查找范围具有很大随机性,由实际数据对象的空间分布决定,动态矩形大小更为合理,同时有效排除了当前不必要查询的区域,在四个方向上是循环进行查找,每次遍历过程中,动态矩形只在一个方向进行一次数据对象范围划分,查找完后,便转向下一个方向进行避免了某方向长期被占用,由于下一个查找方向是上次遍历过程中下一个具有最小近邻距离的方向,所查找的近邻对象之间的顺序趋于最终结果排序顺序,只需进行少量对象间的调整即可,提高了查询效率。论文在采用Java开发技术实现了对基于动态矩形遍历搜索的K-NN查询算法方法的仿真测试。然后依照空间数据库中有关索引算法性能评价的准则,运用随机所产生的空间数据对象集进行测试,实现了对基于动态矩形遍历搜索的K-NN查询算法,树索引和网格索引进行K-NN查询算法的仿真与比较,实验表明,新提出的K-NN查询算法,在查询性能上明显优于传统的索引算法,与树索引相比,不需要进行大量计算进行剪枝去获取有效查询范围,与基于网格索引的查询算法相比,减少了向外扩展的次数,提高了近邻区域的利用率。