论文部分内容阅读
多对象最近邻查询(All Nearest Neighbors Query)[1]在地理信息系统、城市规划和资源分配等领域有广泛的实际应用，也可作为模式识别和分类[2]、某些聚类算法或应用的核心模块[3，4，5]。道路网络在实际生最近邻查询问题还没得到很好的解决：一方面，针对欧氏空间的查询处理算法不能直接适用于道路网络环境：另一方面活中广泛存在，但是至今为止，道路网络环境中的多对象，通过重复调用道路网络环境下的最近邻查询算法来进行多对象最近邻查询处理的计算代价较大。我们利用M树[6]对道路网络中的边建立索引结构，基于该索引，提出了一个新颖的多对象最近邻查询处理算法BANNS(Batched All Nearest NeighborsSearch)。
1、定义道路网络中边与边之间的MaxD距离，其实际意义为：在道路网络中，从一条边的任意一个端点出发，到达另一条边的某个端点所经过的道路网络距离一定不超过MaxD距离。
2、利用M树[6]为道路网络环境中的边建立索引结构。基于该索引结构，我们提出了BANNS算法，采用了批处理的基本思想来处理道路网络中的多对象最近邻查询。
3、为了给实际应用提供更多的信息，我们对BANNS算法进行了扩展，使BAkNNS算法能查询空间对象集合B中A集合元素的多个最近邻。
4、分别使用人造道路网络和真实道路网络数据，验证了BANNS和BAkNNS算法的性能。实验结果显示BANNS和BAkNNS性能稳定、高效：当空间对象集合A较大时，B.ANNS算法具有更好的性能：对于BAkNNS算法来说，随着k的增加，可以适当增大M树的扇出值。
综上，我们研究了道路网络中的多对象最近邻查询问题，提出一个新颖的查询处理算法BANNS，并对其进行了扩展。BANNS算法对于空间对象集合A和B都不要求其本身带有任何索引结构，并能稳定、高效地进行查询处理。