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.