Spatial query processing for trip planning and location recommendation

Shang, Shuo (2013). Spatial query processing for trip planning and location recommendation PhD Thesis, School of Information Technology and Electrical Engineering, The University of Queensland.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
s41802636_phd_finalthesis.pdf Thesis full text application/pdf 1.97MB 15
Author Shang, Shuo
Thesis Title Spatial query processing for trip planning and location recommendation
School, Centre or Institute School of Information Technology and Electrical Engineering
Institution The University of Queensland
Publication date 2013
Thesis type PhD Thesis
Supervisor Xiaofang Zhou
Total pages 166
Total colour pages 16
Total black and white pages 150
Language eng
Subjects 0806 Information Systems
Formatted abstract
The continuous proliferation of GPS-enabled mobile devices (e.g., car navigation systems, smart phones and PDAs) and the rapid development of online map services (e.g., Google-maps1, Bingmaps2 and MapQuest3) enable people to acquire their current geographic positions in real time and to interact with servers to query the spatial information regarding their decisions. The potential market of such location based services in the near future creates various mobile applications. An emerging one is Trip Planning and Location Recommendation, which is designed to plan the convenient routes and recommend suitable locations (POIs: points of interests) to users. In this thesis, we propose and investigate a series of novel problems on trip planning and location recommendation in spatial networks, and provide effective and efficient solutions for them under various problem settings. The brief description of our contributions are stated below.

First, we study a novel spatial keyword query, namely User Oriented Trajectory Search (UOTS). If a trajectory is connecting/close to the specified query locations, and the textual attributes of the trajectory are similar to the traveler’s preference, it will be recommended to the traveler for reference. This type of queries can bring significant benefits to travelers in many popular applications such as trip planning and recommendation. We propose a novel collaborative searching approach to answer the UOTS query efficiently. Conceptually, the UOTS query processing is conducted in the spatial and textual domains alternately. A pair of upper and lower bounds are devised to constrain the searching range in two domains. In the meantime, a heuristic searching strategy based on priority ranking is adopted for scheduling the multiple query sources, which can further reduce the searching range and enhance the query efficiency notably. Furthermore, the devised collaborative searching approach can be extended to situations where the query locations are ordered.

Second, we are the first to study the Path Nearest Neighbor (PNN) query processing on compressed trajectories (PNN-CT query), and the target is to retrieve the PNN with the highest probability. This type of queries can benefit users in many useful applications (e.g., trip planning). To answer the PNN-CT query efficiently, a two-phase solution is proposed: (i) we use the meta-data and sample points to specify a tight search range; (ii) we propose a reconstruction algorithm based on probabilistic models to account for the uncertainty when decompressing the trajectory segments in the candidate set. Furthermore, an effective combination strategy is adopted to find the PNN with the highest probability.

Third, we make some effort on processing the Best Point Detour (BPD) query efficiently, to identify the point detour with the minimum detour cost. This problem can be frequently found in our daily life but is less studied. To improve the query performance, we devise a series of optimization techniques based on network expansion and branch-and-bound strategy. Furthermore, we investigate the continuous-BPD query by running BPD queries in a deliberately planned strategy. The efficiency study reveals that the number of BPD queries executed is optimal.

Fourth, we also investigate Reverse Path Nearest Neighbor (R-PNN) query processing, which is designed to find the most accessible locations in road networks. The R-PNN query is useful in many important applications such as urban planning, facility allocation, traffic monitoring, etc. To answer the R-PNN query in real time, an effective trajectory clustering technique is conducted in the first place. Based on the grouped trajectory data, we propose a series of effective pruning rules and efficient refinement strategy to reduce the computation cost. The performance of the proposed R-PNN query processing is verified by extensive experiments based on real and synthetic trajectory data in road networks.
Keyword Spatial-temporal databases
Query processing
Uncertain data management
Trajectory search and mining
Location based services

Citation counts: Google Scholar Search Google Scholar
Created: Fri, 11 Jan 2013, 15:54:17 EST by Shuo Shang on behalf of Scholarly Communication and Digitisation Service