A shortest path algorithm for moving objects in spatial network databases  

作　　者：Xiaolan Yin Zhiming Ding Jing Li 

机构地区：[1]Technology Center of Software Engineering, Institute of Software, Chinese Academy of Science, P.O. Box 8718, Beijing 100080, China [2]Graduate University, Chinese Academy of Sciences, Beijing 100049, China [3]Technology Center of Basic Software, Institute of Software, Chinese Academy of Sciences, Belting 100080, China

出　　处：《Progress in Natural Science:Materials International》2008年第7期893-899,共7页自然科学进展·国际材料（英文版）

基　　金：National Natural Science Foundation of China （Grant No. 60573164）.

摘　　要：One of the most important kinds of queries in Spatial Network Databases （SNDB） to support location-based services （LBS） is the shortest path query. Given an object in a network, e.g. a location of a car on a road network, and a set of objects of interests, e.g. hotels, gas station, and car, the shortest path query returns the shortest path from the query object to interested objects. The studies of shortest path query have two kinds of ways, online processing and preprocessing. The studies of preprocessing suppose that the interest objects are static. This paper proposes a shortest path algorithm with a set of index structures to support the situation of moving objects. This algorithm can transform a dynamic problem to a static problem. In this paper we focus on road networks. However, our algorithms do not use any domain specific information, and therefore can be applied to any network, This algorithm＇s complexity is O（klog2i）, and traditional Diikstra＇s comolexitv is O（（i ＋ k）^2）.One of the most important kinds of queries in Spatial Network Databases (SNDB) to support location-based services (LBS) is the shortest path query. Given an object in a network, e.g. a location of a car on a road network, and a set of objects of interests, e.g. hotels, gas station, and car, the shortest path query returns the shortest path from the query object to interested objects. The studies of shortest path query have two kinds of ways, online processing and preprocessing. The studies of preprocessing suppose that the interest objects are static. This paper proposes a shortest path algorithm with a set of index structures to support the situation of moving objects. This algorithm can transform a dynamic problem to a static problem. In this paper we focus on road networks. However, our algorithms do not use any domain specific information, and therefore can be applied to any network. This algorithm’s complexity is O(klog2i), and traditional Dijkstra’s complexity is O((i + k)2).

关 键 词：Moving object Spatial network databases Shortest path index Shortest path 

分 类 号：TN92[电子电信—通信与信息系统]