Moving Objects Management for Location-based Services

Abstract:

With the rapid development of GPS-enabled devices and wireless communication technologies, location-based services have attracted significant attention from both academic and industry communities. In this thesis, we focus on the management of moving objects data to make location-based services more intelligent in order to improve people's quality of life. Many interesting applications that target moving objects have great potential to bring revolutionary changes to people's life. However, there is an urgent call for efficient algorithms to support these applications, due to the explosion of geo-tagged information collected from various channels in this era. In this thesis, we have identified problems that are related to moving objects and have many interesting applications in location-based services, and proposed frameworks with efficient algorithms to solve these problems.

In particular, this thesis identifies three novel problems that deal with three types of spatial queries, respectively. First, we study the efficient processing of moving spatial keyword queries on road networks. Such queries consider both spatial locations and textual descriptions to find top k best objects of interest. Most of the existing studies on this topic are restricted to the Euclidean space only. In many applications, position and accessibility of spatial-textual objects are constrained by network connectivity, and spatial proximity should be determined by the shortest path distance rather than the Euclidean distance. However, there is still no research effort on continuous monitoring of spatial keyword queries on road networks. We propose two frameworks that traverse the network in an incremental manner. Meanwhile, different techniques are designed for these two frameworks to avoid unnecessary traversing of some network edges.

Second, we study the efficient processing of moving spatial queries against dynamic event streams. In this problem, the server continuously monitors moving users subscribing to dynamic event streams, and notifies users instantly when there is a matching event nearby. Past research on such problems either focused on how to handle incoming event streams efficiently by assuming users' locations are static or attempted to process continuous moving subscriptions against a static event dataset. Thus, we propose a novel location-aware pub/sub system named Elaps to support moving spatial queries against dynamic event streams for the first time. Elaps employs the concept of safe region to reduce the communication overhead. In Elaps, we develop a new concept called impact region that allows us to identify whether a safe region is affected by newly arrived events. Moreover, we propose a novel cost model to optimize the safe region size to keep the communication overhead low. Based on the cost model, we design two incremental methods for safe region construction. In addition, Elaps uses boolean expression, which is more expressive than keywords, to model user intent and we propose a novel index to handle spatial boolean expression matching.


Third, we study the efficient processing of optimal trajectories queries for influence maximization. Such queries find k best trajectories to be attached with a given advertisement and maximizes the expected influence of the advertisement among a large group of audience. We are the first to extend the classic influence maximization problem to the location-aware advertising field. We show that the problem is NP-hard and propose both exact and approximate solutions to find the best set of trajectories. In the exact solution, we devise an expansion-based framework that enumerates combinations of trajectories in a best-first manner. In addition, we propose two effective methods for the upper bound estimation to facilitate early termination. To support large k, we propose three approximate methods with performance guarantees. In particular, we propose a greedy method and an improved cluster-based approach, both with an approximation ratio of (1-1/e). We also propose a threshold method that can support any approximation ratio in (0,1]. In addition, we extend our problem to support influence maximization for a group of advertisements.

For each framework proposed in the thesis, we conduct extensive experiments in realistic settings with both real and synthetic datasets. These experiments reveal the effectiveness and efficiency of the proposed frameworks.