Spatial query processing for location based services

• Main Author: Liu, Yaqiong
• Other Authors: Seah Hock Soon
• Format: Theses and Dissertations
• Language: English
• Published: 2016
• Subjects: DRNTU::Engineering
• Online Access: https://hdl.handle.net/10356/66553
• Institution: Nanyang Technological University

With the rapid development of wireless communications, location-based services (LBSs) have received extensive researchers' attention. Many LBSs are dependent on the tracking of continuously varying positions of a large set of mobile users, which are also called mobile objects or clients. In this thesis, we consider three spatial queries based on three related LBSs. First, given a road network, a group of moving objects together with their friendships, and a network distance threshold for each pair of friends, the problem of proximity detection in road networks is to find friend pairs whose network distance is within the threshold. The problem of proximity detection is often encountered in massively multiplayer virtual games and friend-locator applications. Because of the limited battery power and bandwidth, we need a solution which incurs low communication cost. Hence, the primary goal of this problem is to reduce the total communication cost. However, most existing proximity detection solutions focus on the Euclidean space which cannot be used in road network space and the solutions for road networks incur substantial communication costs. Motivated by this, we propose two types of solutions to the proximity detection problem in road networks. In the first type of solution, each mobile client is assigned a mobile region of a fixed size. We design algorithms with a fixed radius for the server and client respectively, with the purpose of reducing unnecessary probing messages and updating messages. Second, we present a self-adjustment strategy to automatically adjust the size of the mobile region for the purpose of minimizing the communication cost. Experiments show that our second type of solution works efficiently and robustly with a much lower communication cost with respect to various parameters. In addition, we propose server-side computational cost optimization techniques to reduce the total computational cost. Second, points of interest (POI) recommendation with real-world applications is another research issue that has attracted researchers' much attention. Given a set of moving users, i.e., moving objects, and their historical GPS trajectories, the POI recommendation problem is to recommend semantic POIs, based on the GPS trajectories of the users. We first develop a novel algorithm, namely, SEM-DTBJ-Cluster, which stands for semantics-enhanced density-based clustering, for extracting semantic points of interest from GPS trajectories. We subsequently take three different factors (popularity, temporal influence and geographical influence) into consideration, and describe the impacts of popularity, temporal and geographical information, by deriving three different scoring functions based on three recommendation models. We finally combine the three scoring functions together and obtain a unified framework PTG-Recommend for recommending candidate POIs to a moving user. Our work is the first that considers the influence of popularity, the influence of temporal features, and the influence of geographical features of a POI together. Results of experiments on two GPS trajectory datasets not only prove the effectiveness of our framework, but also show that it performs better than the baseline POI recommendation methods with regard to precision and recall. Third, route queries are important problems that find applications in many location-based services. Considerable existing studies address routing problems in static road networks. However, the travel costs on edges in road networks always change over time. Such road networks are referred as time-dependent road networks. Most existing studies on time-dependent road networks focus on simply finding a shortest path with the minimum travel time without considering waiting at some nodes, or fuel consumption and toll fee. In fact, waiting at a node is likely to happen and one edge can be traversed at different speeds. Additionally, traveling along a route consumes both fuels and toll fee. In many cases, an optimal route is the minimum-cost route under time and speed constraints. Motivated by this, we study the Cost-Optimal routing problem in Time-dEpendent Road networks with time and speed constraints, denoted as COTER for short, where the travel cost of a route is composed of fuel cost and toll fees. We utilize two fuel consumption models and compute the minimum fuel consumption of an edge under the constraint that the travel time on this edge is exactly the given time, for helping users determine optimal speeds on each edge. We allow the toll fee to be an arbitrary single-valued time-dependent function of the departure time for each edge. We define a time-dependent OC function (Optimal Cost function) for each node n_i, and derive the recurrence relation formula between n_i's incoming neighbors' OC-functions and n_i's OC-function. We propose a five-step approximate algorithm, namely, ALG-COTER, which answers COTER using optimized single-source shortest-path algorithm, topological sorting, dynamic programming, nonlinear programming and backtrack algorithms. Experimental results show that our algorithm answers COTER queries efficiently and our algorithm is scalable with respect to different parameters that have influences on the running time.