Institutional Repository
| A shortest path algorithm for moving objects in spatial network databases | |
| Yin Xiaolan; Ding Zhiming; Li Jing | |
| 2008 | |
| Source | Progress in Natural Science
 |
| Volume | 18Issue:7Pages:893-899 |
| English Abstract | 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). |
| Indexed Type | SCI |
| Keyword | Moving Object |
| Language | 英语 |
| Content Type | 期刊论文 |
| URI | http://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） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment