A shortest path algorithm for moving objects in spatial network databases

	A shortest path algorithm for moving objects in spatial network databases
	Yin Xiaolan; Ding Zhiming; Li Jing
	2008
发表期刊	Progress in Natural Science
卷号	18 期号:7 页码:893-899
摘要	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(klog2 i), and traditional Dijkstra’s complexity is O((i + k)2).
收录类别	SCI
关键词	Moving Object
语种	英语
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/605
专题	基础软件国家工程研究中心
推荐引用方式 GB/T 7714	Yin Xiaolan,Ding Zhiming,Li Jing. A shortest path algorithm for moving objects in spatial network databases[J]. Progress in Natural Science,2008,18(7):893-899.
APA	Yin Xiaolan,Ding Zhiming,&Li Jing.(2008).A shortest path algorithm for moving objects in spatial network databases.Progress in Natural Science,18(7),893-899.
MLA	Yin Xiaolan,et al."A shortest path algorithm for moving objects in spatial network databases".Progress in Natural Science 18.7(2008):893-899.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
丁治明per-05.pdf（510KB）			开放获取	使用许可	请求全文