Novel spatial query processing techniques for scaling location based services

Show full item record

Please use this identifier to cite or link to this item:

Title: Novel spatial query processing techniques for scaling location based services
Author: Pesti, Peter
Abstract: Location based services (LBS) are gaining widespread user acceptance and increased daily usage. GPS based mobile navigation systems (Garmin), location-related social network updates and "check-ins" (Facebook), location-based games (Nokia), friend queries (Foursquare) and ads (Google) are some of the popular LBSs available to mobile users today. Despite these successes, current user services fall short of a vision where mobile users could ask for continuous location-based services with always-up-to-date information around them, such as the list of friends or favorite restaurants within 15 minutes of driving. Providing such a location based service in real time faces a number of technical challenges. In this dissertation research, we propose a suite of novel techniques and system architectures to address some known technical challenges of continuous location queries and updates. Our solution approaches enable the creation of new, practical and scalable location based services with better energy efficiency on mobile clients and higher throughput at the location servers. Our first contribution is the development of RoadTrack, a road network aware and query-aware location update framework and a suite of algorithms. A unique characteristic of RoadTrack is the innovative design of encounter points and system-defined precincts to manage the desired spatial resolution of location updates for different mobile clients while reducing the complexity and energy consumption of location update strategies. The second novelty of this dissertation research is the technical development of Dandelion data structures and algorithms that can deliver superior performance for the periodic re-evaluation of continuous road-network distance based location queries, when compared with the alternative of repeatedly performing a network expansion along a mobile user's trajectory. The third contribution of this dissertation research is the FastExpand algorithm that can speed up the computation of single-issue shortest-distance road network queries. Finally, we have developed the open source GT MobiSim mobility simulator, a discrete event simulation platform to generate realistic driving trajectories for real road maps. It has been downloaded and utilized by many to evaluate the efficiency and effectiveness of the location query and location update algorithms, including the research efforts in this dissertation.
Type: Dissertation
Date: 2012-11-12
Publisher: Georgia Institute of Technology
Subject: CQ
Range query
Road network
Location based services
Continuous query
Querying (Computer science)
Database searching
System design
Department: Computing
Advisor: Committee Chair: Liu, Ling; Committee Member: Choi, Wonik; Committee Member: Mark, Leo; Committee Member: Omiecinski, Edward; Committee Member: Pu, Calton
Degree: PhD

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
pesti_peter_201212_phd.pdf 3.286Mb PDF View/ Open

This item appears in the following Collection(s)

Show full item record