ISCAS OpenIR  > 基础软件国家工程研究中心
A shortest path algorithm for moving objects in spatial network databases
Yin Xiaolan; Ding Zhiming; Li Jing
2008
SourceProgress in Natural Science
Volume18Issue:7Pages:893-899
English AbstractOne 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).
Indexed TypeSCI
KeywordMoving Object
Language英语
Content Type期刊论文
URIhttp://ir.iscas.ac.cn/handle/311060/605
Collection基础软件国家工程研究中心
Recommended Citation
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.
Files in This Item:
File Name/Size DocType Version Access License
丁治明per-05.pdf(510KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Yin Xiaolan]'s Articles
[Ding Zhiming]'s Articles
[Li Jing]'s Articles
Baidu academic
Similar articles in Baidu academic
[Yin Xiaolan]'s Articles
[Ding Zhiming]'s Articles
[Li Jing]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Yin Xiaolan]'s Articles
[Ding Zhiming]'s Articles
[Li Jing]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.