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:
$37.50

Abstract

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
Top

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.

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.

Top

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.

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:
Reset
Editorial Advisory Board
Table of Contents
Foreword
Gabriele Kotsis
Acknowledgment
Ismail Khalil
Chapter 1
Elhadi Shakshuki, Xinyu Xing, Haroon Malik
Wireless multimedia sensor networks (WMSNs) are a new and emerging type of sensor networks that contain sensor nodes equipped with cameras... Sample PDF
An Introduction to Wireless Multimedia Sensor Networks
$37.50
Chapter 2
Jing Wang
Wireless sensor networks have seen a wealth of research efforts and practical implementations in recent years. With the advance of CMOS cameras and... Sample PDF
Enabling Wireless Multimedia Sensor Networks
$37.50
Chapter 3
Julio Aráuz
On the stage of today’s communications world, broadband mobile technologies are a continuously flourishing trend. In this context, WiMAX, a... Sample PDF
Research Challenges in Multimedia WiMAX
$37.50
Chapter 4
Reinhard Kronsteiner
This chapter is about mobile multimedia and its usage in group decisions. With respect to the complexity of mobile decision scenarios, this paper... Sample PDF
Engineering Mobile Group Decision Support
$37.50
Chapter 5
The Ubiquitous Grid  (pages 66-75)
Patricia Sedlar
The strength of grid computing, namely being able to aggregate distributed computing and data storage capacities for solving larger, more complex... Sample PDF
The Ubiquitous Grid
$37.50
Chapter 6
Paul Fergus
The number of consumer devices that are being equipped with networking capabilities is increasing rapidly. This is seen as a fundamental strategy... Sample PDF
Next Generation Mobile Multimedia
$37.50
Chapter 7
Reinhard Kronsteiner, Bettina Thurnher
This chapter considers the mobility of persons while they are changing between different working environments and the influence of increasing... Sample PDF
Opportunities and Risks for Mobile Decision Support
$37.50
Chapter 8
Volker Derballa
Mobile technology enables enterprises to invent new business models by applying new forms of organization or offering new products and services. In... Sample PDF
Business Model Typology for Mobile Commerce
$37.50
Chapter 9
Edgar R. Weippl
While security in general is increasingly well addressed, both mobile security and multimedia security are still areas of research undergoing major... Sample PDF
Security, Trust, and Privacy on Mobile Devices and Multimedia Applications
$37.50
Chapter 10
Goran Gvozden, Mislav Grgic, Sonja Grgic, Miran Gosta
This chapter gives description and comparison of video coding standards currently used in bandwidth limited mobile communications emphasizing at the... Sample PDF
Comparison of Video Coding Standards Used in Mobile Applications
$37.50
Chapter 11
Saad Harous
In this chapter, we will introduce mobile ad hoc networks and issues related to routing data in such networks. Mobile ad hoc networks (MANET) are... Sample PDF
Routing Algorithms for Mobile Ad Hoc Networks
$37.50
Chapter 12
Mamun I. Abu-Tair
Recently there have been considerable interests focusing on the performance evaluation of IEEE 802.11e Medium Access Control (MAC) protocols, which... Sample PDF
Performance Analysis and Evaluation of IEEE 802.11E MAC in WLANs with Hidden Stations and Multimedia Applications
$37.50
Chapter 13
High Speed Packet Access  (pages 175-190)
Mario Cvitkovic
Data services and multimedia are expected to have significant growth over the next few years and will likely become the dominant source of 3G... Sample PDF
High Speed Packet Access
$37.50
Chapter 14
Sami Habib
The evolutionary search approach has demonstrated its effectiveness in many real world applications, such as the coverage problem in wireless sensor... Sample PDF
Exploring Coverage within Wireless Sensor Networks through Evolutionary Computations
$37.50
Chapter 15
René Rosenbaum
Imagery must be adequately processed and adapted to be used in mobile environments. This contribution shows that this can be reached by a rigorous... Sample PDF
Mobile Image Communication: New Concepts Using JPEG2000
$37.50
Chapter 16
Ulf Wehling
In this chapter we propose a platform-independent concept for the transparent replication of digital assets in hybrid wireless networks. The concept... Sample PDF
Topic-Based Transparent Replication of Digital Assets
$37.50
Chapter 17
Abdulhussain E. Mahdi
Speech quality is the most visible and important aspect of quality of service (QoS) for telecommunication networks. Hence, the ability to monitor... Sample PDF
Perception-Based Speech Quality Measurement in Modern Telecommunications
$37.50
Chapter 18
Árpád Huszák
In this chapter we present a novel selective retransmission scheme, based on congestion control algorithm. Our method is efficient in narrowband... Sample PDF
Adaptive Retransmission Scheme for Video Streaming Applications
$37.50
Chapter 19
Gregor Rozinaj
In this chapter we describe a proposal of a metropolitan information system (MIS) for providing various information for inhabitants of the city, as... Sample PDF
Terminals for the Smart Information Retrieval
$37.50
Chapter 20
Oredope Adetola
The concept of multimedia streaming gives the end-users the ability to playback various multimedia contents while they are still being downloaded... Sample PDF
Streaming Multimedia via Peer-to-Peer Systems
$37.50
Chapter 21
Hamidah Ibrahim
An important problem for a database system is to guarantee database consistency. Difficulty arises in devising an efficient algorithm for checking... Sample PDF
Event-Condition-Action (ECA) Rules for Maintaining the Integrity Constraints of Mobile Databases
$37.50
Chapter 22
Janne Lahti
Video management research has been neglecting the increased attractiveness of using camera-equipped mobile phones for the production of short... Sample PDF
Context-Aware Capture and Sharing of Mobile Videos
$37.50
Chapter 23
Panayotis Fouliras
Data dissemination has already been identified as one of the most important aspects for mobile environments and particularly so for large volumes of... Sample PDF
Video and Data Dissemination in Mobile Broadcasting Environments
$37.50
Chapter 24
Wanji Mai, Chris Tweed, Peter Hung, Seán McLoone, Ronan Farrell
In this chapter, the idea of identification of outdoor buildings using mobile devices is presented. The prototype system involves integration of... Sample PDF
A Practical Perspective on Building Identification from Low-Resolution Mobile Images
$37.50
Chapter 25
Chris Stary
Although mobile interactivity is becoming quite common, for content-rich applications, such as educational hypermedia systems, user-centered design... Sample PDF
Ubiquitous Access to Adaptive Hypermedia
$37.50
Chapter 26
Danilo Avola
The actual mobile technology and the increasing need to obtain rich multimedia content about each and every aspect of the human life are changing... Sample PDF
Context Modelling Approaches for Mobile Systems
$37.50
Chapter 27
Eduardo Antonio Viruete Navarro
In the last years, much work has been done to create a complete solution in m-Health environments. The problem can be summarized as follows: any... Sample PDF
Mobility Support in 4G Heterogeneous Networks for Interoperable M-Health Devices
$37.50
Chapter 28
László Bokor
The support of broadcasting and multicasting as an efficient L3-based service poses rigorous requirements to the next generation mobile... Sample PDF
Novel Results on MBMS Service Provisioning in UMTS/WLAN Heterogeneous Architectures
$37.50
Chapter 29
Paolo Barsocchi, Alan A. Bertossi, M. Cristina Pinotti, Francesco Potortì
Broadcasting is an efficient and scalable way of transmitting data over wireless channels to an unlimited number of clients. In this chapter the... Sample PDF
Quality of Service of Data Broadcasting Algorithms on Erroneous Wireless Channels
$37.50
Chapter 30
Shiguo Lian
Digital fingerprinting is reported and used in copy tracing. It embeds different information, for example, Customer ID, into multimedia content... Sample PDF
Traitor Tracing in Mobile Multimedia Communication
$37.50
Chapter 31
Do van Thanh, Ivar Jørstad
Although promised for some time now, advanced multimedia services for mobile devices were not yet a reality. With IMS (IP Multimedia Subsystem), the... Sample PDF
Advanced Mobile Multimedia Services with IMS
$37.50
Chapter 32
Tania Das
Movement prediction oriented adaptive location management provides a major role in personal communication service (PCS) system. Generally the GSM... Sample PDF
Movement Prediction Oriented Adaptive Location Management
$37.50
Chapter 33
Yoshio Nakajima, Alireza Goudarzi Nemati, Tomoya Enokido, Makoto Takizawa
In a peer-to-peer (P2P) overlay network, a peer process (peer) communicates with other peers and manipulates objects like databases in the peers.... Sample PDF
Subjective and Objective Trustworthiness of Acquaintance Peers
$37.50
Chapter 34
Hui Zhu
Particle Swarm Optimization (PSO) is a newly appeared technique for evolutionary computation. It was originated as a simulation for a simplified... Sample PDF
An Improved Particle Swarm Optimization for Indoor Positioning
$37.50
Chapter 35
Ben Abdallah Abderazek, Arquimedes Canedo, Kenichi Kuroda
Mobile processors are used in numerous embedded systems, including laptops, personal digital organizers, wearable computers, cellular phones, mobile... Sample PDF
Processor for Mobile Applications
$37.50
Chapter 36
Kashinath Basu
A significant proportion of the traffic on the 4th generation of mobile networks (4G) will be interactive multimedia traffic. This chapter presents... Sample PDF
A Model for Providing Mobile Multimedia Services Over 4G Networks
$37.50
Chapter 37
Wieland Schwinger, Christoph Grün, Birgit Pröll, Werner Retschitzegger
Today’s tourists expect to get personalized access to tourism information at anytime, from anywhere with any media. Mobile tourist guides provide... Sample PDF
Context-Awareness in Mobile Tourist Guides
$37.50
Chapter 38
Daniel C. Doolan, Sabin Tabirca, Laurence T. Yang
Today in the beginning of the 21st century, mobile devices are now ubiquitous. No matter where we go or what we do, we are touched by this new... Sample PDF
Unlocking the Hidden Power of the Mobile
$37.50
Chapter 39
Daniel C. Doolan, Sabin Tabirca, Laurence T. Yang
The Message Passing Interface (MPI) was published as a standard in 1992. Since then, many implementations have been developed. The MPICH library is... Sample PDF
Parallel Computing on a Mobile Device
$37.50
Chapter 40
Daniel C. Doolan, Kevin Duggan, Sabin Tabirca, Laurence T. Yang
The growth of mobile phone sales is phenomenal, with estimated sales for 2007/2008 expected to be approximately $1 billion. The majority of these... Sample PDF
From Single to Multiplayer Mobile Bluetooth Gaming
$37.50
Chapter 41
Christos K. Georgiadis
Discovering and redirecting multimedia services in a personalized manner is achieving increasing importance for mobile users. It is a powerful... Sample PDF
Mobile Agents and Personalized Multimedia Services
$37.50
Chapter 42
Hongbo Ni, Xingshe Zhou, Zhiwen Yu, Daqing Zhang
The vision of pervasive computing is floating into the domain of the household and aims to assist inhabitants (users) to live more conveniently and... Sample PDF
Enhancing User Experience with Context-Dependent Tasks in Smart Home
$37.50
Chapter 43
Pavol Podhradský, Eugen Mikóczy, Matejka Juraj, Ondrej Lábaj, Róbert Tomek
This chapter presents results of practical experience with NGN and mainly its application layer. The presented university laboratory based mainly on... Sample PDF
Practical Experience with New Services and Applications Supported by NGN
$37.50
Chapter 44
Jong-Woon Yoo
This chapter presents an intelligent interface system, including a new gesture-based wearable input device called iThrow as a main user interface... Sample PDF
A Gesture-Based Intuitive Interaction System and its Target Selection Algorithm
$37.50
Chapter 45
Diego Liberati
This chapter is about the effects on perception of joint sensory stimulation. It shows that by combining various simultaneous stimuli, it is... Sample PDF
Attention Facilitation via Multimedia Stimulation
$37.50
Chapter 46
Mercedes Paulini
Mobile computing provides a new dimension in communication and access to data resources that is transforming the way people use information and... Sample PDF
Context-Aware Urban Exploration: A Paradigm for Non-Directed Exploration in Mobile Computing
$37.50
Chapter 47
Robert Schmohl, Uwe Baumgarten, Lars Köthner
Recent advances in mobile computing have spawned a very heterogeneous environment of mobile devices, which is reflected by the presence of the... Sample PDF
Content Adaptation for Heterogeneous Mobile Devices
$37.50
Chapter 48
Roman Y. Shtykh, Qun Jin, Shunichi Nakadate, Norihiro Kandou, Takeshi Hayata, Jianhua Ma
Mobile social networking services (MoSNS) are a yet unexplored environment for human networked socialization. By introducing the concept of... Sample PDF
Mobile SNS from the Perspective of Human Self-Extension
$37.50
Chapter 49
Stephan Reiff-Marganiec, Yi Hong, Hong Qing Yu, Schahram Dustdar, Christoph Dorn, Daniel Schall
Collaborative Work Environments are software systems that allow teams, which are nowadays often distributed in location and organization to which... Sample PDF
Context Aware Collaborative Working Environments
$37.50
Chapter 50
Baud Haryo Prananto
Lifelog media system stores and manages users’ everyday experiences in the form of multimedia data. To build such a system, we require an integrated... Sample PDF
Design and Implementation of a Mobile and Portable Lifelog Media System
$37.50
Chapter 51
Diego Moreira Alves
The main objective of this chapter is to present a solution to the development of speech synthesis and speech recognition systems through mobile... Sample PDF
Speech Synthesis and Recognition Based on Mobile Computing Application
$37.50
Chapter 52
Dietmar G. Wiedemann
This chapter introduces the concept of mobile viral marketing as an innovative marketing tool. The outcome of the chapter is a description model... Sample PDF
Creating Successful Mobile Viral Marketing Strategies
$37.50
Chapter 53
Henrik Stormer
In the last years, mobile devices have become more and more popular. To further enhance the success of mobile devices, companies in the mobile... Sample PDF
Customizable Viewlets: A Generic Approach for the Mobile Web
$37.50
Chapter 54
Mahieddine Djoudi, Saad Harous
Support for the Semitic language on mobile devices, while not yet universal, is becoming more ubiquitous. Many items and data contents written in... Sample PDF
Text Entry System for Semitic Languages on Mobile Devices
$37.50
Chapter 55
Patrícia Dockhorn Costa, Luís Ferreira Pires, Marten van Sinderen
Context-awareness has been investigated for almost a decade and is considered as a convenient and desirable feature in distributed mobile systems... Sample PDF
Concepts and Architectures for Mobile Context-Aware Applications
$37.50
Chapter 56
Frédéric Lassabe, Philippe Canalda, Damien Charlet, Pascal Chatonnay, François Spies
Advances in technology have enabled a proliferation of mobile devices and a broad spectrum of novel and outbreaking solutions for new applications... Sample PDF
Mobility within Rich Multimedia Services
$37.50
Chapter 57
Anastasis A. Sofokleous, Marios C. Angelides, Christos N. Schizas
Mobile communications and computing has changed forever the way people communicate and interact and it has made “any information, any device, any... Sample PDF
Mobile Computing: Technology Challenges, Constraints, and Standards
$37.50
Chapter 58
Say Ying Lim
In this chapter, we present an extensive study of database operations on mobile devices which provides an understanding and direction for processing... Sample PDF
A Taxonomy of Database Operations on Mobile Devices
$37.50
Chapter 59
Spatial Data on the Move  (pages 850-864)
Wee Hyong Tok, Stéphane Bressan, Panagiotis Kalnis, Baihua Zheng
The pervasiveness of mobile computing devices and wide-availability of wireless networking infrastructure have empowered users with applications... Sample PDF
Spatial Data on the Move
$37.50
Chapter 60
Ioannis Priggouris, Evangelos Zervas, Stathes Hadjiefthymiades
The vision that wireless technology in the near future will provide mobile users with at least similar multimedia services as those available to the... Sample PDF
Location-Based Network Resource Management
$37.50
Chapter 61
Ghita Kouadri Mostéfaoui
The abstract should be changed to this new abstract: Research on mobile multimedia mainly focuses on improving wireless protocols in order to... Sample PDF
Software Engineering for Mobile Multimedia: A Roadmap
$37.50
Chapter 62
Yuping Yang
One current vision of future communication systems lies in a universal system that can deliver information and communications at any time and place... Sample PDF
Personalized Redirection of Communication and Data
$37.50
Chapter 63
Florian Ledermann
In this chapter, a domain independent taxonomy of sign functions rooted in an analysis of physical signs found in public space is presented. This... Sample PDF
Towards a Taxonomy of Display Styles for Ubiquitous Multimedia
$37.50
Chapter 64
Do Van Thanh, Ivar Jørstad, Schahram Dustdar
Mobile communication and Web technologies have paved the way for mobile multimedia collaborative services that allows people, team and organisation... Sample PDF
Mobile Multimedia Collaborative Services
$37.50
Chapter 65
Mohamed Ali Feki
This chapter will describe our experience concerning a model-based method for environment design in the field of smart homes dedicated to people... Sample PDF
Context Awareness for Pervasive Assistive Environment
$37.50
Chapter 66
Damien Charlet, Frédéric Lassabe, Philippe Canalda, Pascal Chatonnay, François Spies
Advances in technology have enabled a proliferation of mobile devices and a broad spectrum of novel and out breaking solutions for new applications... Sample PDF
Mobility Prediction for Multimedia Services
$37.50
Chapter 67
Roland Wagner, Franz Gruber, Werner Hartmann
After the enormous success of the internet and mobile networks, the next upcoming boost for information technology will be the combination of both.... Sample PDF
Distribution Patterns for Mobile Internet Applications
$37.50
About the Contributors