Spatial Data on the Move

Spatial Data on the Move

Wee Hyong Tok (National University of Singapore, Singapore), Stéphane Bressan (National University of Singapore, Singapore), Panagiotis Kalnis (National University of Singapore, Singapore) and Baihua Zheng (Singapore Management University, Singapore)
Copyright: © 2009 |Pages: 15
DOI: 10.4018/978-1-60566-046-2.ch059
OnDemand PDF Download:


The pervasiveness of mobile computing devices and wide-availability of wireless networking infrastructure have empowered users with applications that provides location-based services as well as the ability to pose queries to remote servers. This necessitates the need for adaptive, robust, and efficient techniques for processing the queries. In this chapter, we identify the issues and challenges of processing spatial data on the move. Next, we present insights on state-of-art spatial query processing techniques used in these dynamic, mobile environments. We conclude with several potential open research problems in this exciting area.
Chapter Preview


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.

Chapter Organization

The next few sections are organized as follows: Background, Querying Spatial Data, Data Dissemination, and Conclusion. We first present a framework for understanding the various query processing techniques. Next, we present the state-of-art query processing techniques for handling the following type of queries: point and range queries (we look at access methods and data structures), nearest neighbor queries, spatial joins, aggregation, and predictive queries. Then, we look at data dissemination methods used in the mobile environment. We conclude in the last section.



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.

Key Terms in this Chapter

Continuous Spatial Queries: Continuous spatial queries are queries that are installed once in a system, and executed over an extended period of time against spatial datasets.

Spatial Join: A spatial join query finds all object pairs from two data sets that satisfy a spatial predicate. A common spatial predicate used in a spatial join is intersection.

Nearest Neighbor (NN) Queries/k-Nearest Neighbor (kNN) Queries: A kNN query retrieves the k nearest data object with respect to a query object. When k = 1, it is called a NN query.

Aggregation: An aggregation is an operation in databases which returns a summarized value, with respect to an aggregation function. Examples of aggregation function includes sum and count.

Spatio-Temporal Databases: Spatio-temporal databases deal with objects that change their location and/or shape over time.

Hilbert Curve: A Hilbert curve is part of the family of plane-filling curve. It is commonly used to transform multi-dimensional data to a single dimension.

Location-Aware Applications: Location-aware applications refer to a class of applications which are unable to recognize and react to the location the user is currently in. The results of the queries changes as the user moves.

Histogram: A histogram maintains statistics on the frequency of the data.

Complete Chapter List

Search this Book: