Efficient Distance-based Query Processing in Spatial Networks

Wang, Jiping (2014). Efficient Distance-based Query Processing in Spatial Networks MPhil Thesis, School of Information Technology and Electrical Engineering, The University of Queensland. doi:10.14264/uql.2014.487

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
s4301380_mphil_submission.pdf Thesis (open access) application/pdf 2.63MB 103

Author Wang, Jiping
Thesis Title Efficient Distance-based Query Processing in Spatial Networks
School, Centre or Institute School of Information Technology and Electrical Engineering
Institution The University of Queensland
DOI 10.14264/uql.2014.487
Publication date 2014-11-18
Thesis type MPhil Thesis
Open Access Status Other
Supervisor Xiaofang Zhou
Kevin Zheng
Total pages 95
Language eng
Subjects 0806 Information Systems
Formatted abstract
The prevalence of GPS-enabled mobile devices and wireless communication has given rise to a wide range of location-based services (e.g. Foursquare, Google Maps). These services support various types of queries related to the objects' spatial locations. For example, a user may want to find the five restaurants nearest to his location while visiting an unfamiliar city. Since these services provide real-time response to people's queries, the efficiency of query processing is crucial for them. 

In real-world applications, the movements of the objects are often constrained to underlying paths such as spatial networks. In these circumstances, the distance between two locations is measured by the length of the shortest path between them. As shortest path distance is the metric for most query types in spatial networks, their query processing is all network distance based. This makes the query processing in spatial networks quite different from that in the Euclidean space. Thus the traditional algorithms designed for the Euclidean space are not directly applicable. This thesis aims at supporting efficient query processing in spatial networks. Specifically, it focuses on two research problems.

The first work in the thesis studies the efficient object query processing in spatial networks. A novel graph partitioning based index, the Partition Tree, is proposed. It takes account of both the network topologies and the object distribution. Based on the Partition Tree, efficient algorithms are proposed for common types of queries in spatial networks including shortest path query and k-NN query. Furthermore, a cost model is derived to balance the cost of indexing and query efficiency.

The second work in the thesis studies the efficient trajectory query processing in spatial networks. A trajectory is a record of moving history of an object and the trajectory dataset contains rich information of specific moving patterns. To support efficient trajectory query processing, the Partition Tree is modified to index trajectories in this work. Then correspondent algorithms are proposed for trajectory queries in spatial networks.

Comprehensive experiments are conducted to verify the performance of the proposed approaches. The experimental results demonstrated that the proposed methods in this thesis have superior performance over the existing works.
Keyword Spatial networks
Query processing

Document type: Thesis
Collections: UQ Theses (RHD) - Official
UQ Theses (RHD) - Open Access
Version Filter Type
Citation counts: Google Scholar Search Google Scholar
Created: Wed, 29 Oct 2014, 13:21:39 EST by Jiping Wang on behalf of Scholarly Communication and Digitisation Service