Spatial Data on the Move

Introduction

The pervasiveness of wireless networks (e.g., Wi-Fi and 3G) has empowered users with wireless mobility. Coupled with the wide-availability of mobile devices, such as laptops, personal digital assistants (PDAs), and 3G mobile phones, it enables users to access data anytime and anywhere. Applications that are built to support such data access often need to formulate queries (often spatial in nature) and send the queries to a remote server in order to either retrieve the results or retrieve the data, which is then processed locally by the mobile device. Due to the mobility of the users and limited resources available on the devices used, it compels the need for efficient and scalable query processing techniques that can address the challenges on handling spatial data on the move.

Mobile devices (e.g., PDAs, laptops) connect to the servers via wireless networks (e.g., WiFi, 3G, CDMA2000), and have limited resources (power, CPU, memory). Hence, it is necessary to optimize the resources usage. Existing wireless technology suffers from the problem of low-bandwidth (compared with the wired networks) and the range. The maximum bandwidth for WiFiMax, WiFi, and 3G are 75Mbps, 54Mbps and 2Mbps respectively. Also, as the network is susceptible to interference (from other wireless devices, obstructions, etc.), the achievable bandwidth is usually much lower. To reduce unnecessary communication overheads between the server and the clients, it is important to transfer only the required data items. In addition, the query processing techniques would need to adapt to the unpredictable nature of the underlying networks, and yet ensure that data is delivered continuously to the clients.

As the users carrying the mobile devices move, the queries pose might move based on the users’ current location. Query processing algorithms need to tackle these mobility challenges. For example, a mobile device might issue the following k-nearest neighbor (kNN) query: Retrieve the five nearest fast food restaurants. However, as the user who is carrying the mobile devices move, the results of the kNN query changes. Thus, many existing algorithms designed for static environment, which assumes that the query is static cannot be used directly. In addition, many existing indices are optimized for static datasets, and cannot be directly used for indexing moving data, due to the overheads from updates, and deletions due to expiration of queries or data items. This compels the need for new indices, designed to handle issues introduced due to mobility.

Notably, long-running continuous spatial queries are relatively more common in a mobile environment compared to ad hoc queries and pre-canned queries. For example, users might be interested in monitoring specific regions for activities over an extended period of time, or predict the number of objects at a region in the future. The distinction between queries and data objects is thus relatively blurred. Another observation is that the number of queries is usually relatively smaller than the number of data objects especially over an extended period of time. Thus, to process queries efficiently, it might be more efficient to index the query instead of the data objects.

In this chapter, we present a comprehensive survey on the state-of-art techniques that have been proposed for handling these queries in a wireless mobile environment. We focus on the spatial access method and query processing techniques that have been developed for spatio-temporal and location-aware environment domain.

Background

In this section, we provide a generic framework for studying the different query processing techniques discussed in the later section. In the framework, we consider the nature of queries and objects, the types of queries and ad hoc vs. continuous queries.