Back to search

Georgia Institute of Technology

Novel spatial query processing techniques for scaling location based services

Abstract

dc:description.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.

Degree

thesis:*
Department dc:contributor.department
Computing
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pesti, Peter
Advisor dc:contributor.advisor
  • Liu, Ling
Committee members dc:contributor.committeemember
  • Choi, Wonik
  • Mark, Leo
  • Omiecinski, Edward
  • Pu, Calton

Subjects

dc:subject × 12

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/45844

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Pesti, Peter. Novel spatial query processing techniques for scaling location based services. Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/45844