基于路网的连续K最近邻查询

Continuous K nearest neighbor queries in road networks

连续K最近邻(CKNN)查询是最近邻查询的扩展,可广泛地应用于地理信息系统、城市规划、智能交通等领域.CKNN查询搜索某一路径上所有点的K个最近的感兴趣对象.本文研究基于交通路网的连续K最近邻查询问题,不同于传统的基于欧式空间的CKNN查询,基于路网的CKNN查询中对象间的距离度量不再是欧式距离,而是基于路网的最短可达距离.显然,传统的基于欧式距离的CKNN查询算法并不能直接应用于基于路网的CKNN查询问题.本文提出了一种基于路网的高效的CKNN查询算法-IIE算法,广泛实验表明本文提出的IIE算法优于传统的IE算法.

Continuous K nearest neighbors（CKNN） query is an extension of nearest neighbor query and can be widely ap- plied into geographical information systems, city plan, intelligent traffic, etc. A CKNN query retrieves K nearest neighbors of every point in the specified line segment. This paper explores CKNN query processing in road networks. Conventional CKNN queries focus on Euclidean spaces where the distance between two objects is determined solely by their relative position in space. For CKNN queries in road networks, the distance measure is the network distance, i. e. , the length of the shortest trajectory connecting two objects, rather than their Euclidean distance. Obviously, the existing algorithms based on Euclidean distance are not suitable for processing CKNN queries in road networks. This paper presents an eft^eient CKNN query algorithm （called improved IE algorithm, liE）. Extensive experiments are conducted, and the results show the proposed liE algorithm perf.,rrns more efficient than the conventional IE algorithm.