MOVNet: A framework to process location-based queries on moving objects in road networks

Recently, the usage of various GPS devices (e.g., car-based navigation systems and handheld PDAs) has become very popular in many - especially urban - areas. More and more people carry these devices on the go. Moreover, since wireless connectivity is embedded into these devices, the end users are able to report their positions when experiencing the service and hence themselves become Points Of Interest (POIs) during query processing. With the rapidly growing number of users willing to subscribe to various location-based services, designing novel systems that support a very large number of users is raising intense interest in the research community.;Specifically, the mobility that is made possible by these portable GPS devices in metro cities results in two fundamental requirements when implementing location-based services: road network-based distance computation and the capability to process moving objects as POIs. It is highly desirable to design a novel infrastructure that (i) efficiently manages object location updates; and (ii) provides fast distance computation with regard to the connectivity of the underlying network. To the best of our knowledge, there have been few studies that address both challenges at the same time.;In this dissertation, we first discuss the requirements and challenges of designing a scalable and flexible location-based service on moving POIs in metro cities. We propose a novel system to process location-based queries on MOVing objects in road Networks (MOVNet, for short). In its current form, MOVNet utilizes a dual-index structure in which an on-disk R-tree stores the network connectivity and an in-memory grid index maintains moving object position updates. In addition, a technique to speedily compute the overlapping grid cells in the network is proposed to relate these two indices. Moreover, given an arbitrary edge in the space, we analyze the minimum and maximum number of grid cells that are possibly affected, which can be effectively used to prune the search space during query processing. Based on these features, we first propose algorithms for snapshot network-distance-based range queries and k nearest neighbor queries to support mobile location-based services. Next, we extend the functionality of MOVNet to support continuous query processing by introducing the concept of a Shortest-Distance-based Tree (SD-Tree, for short). We illustrate that the network connectivity and distance information can be preserved and reused by the SD-Tree when the query point moves to a new location, hence reducing the update cost for continuous queries. We demonstrate via theoretical analysis and experimental results that MOVNet yields excellent performance in various networks and with a very large number of moving objects.