SGER: Distributed Spatial Partitioning Algorithms for Scalable Processing of Mobile Location Queries

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

IIS-0640219 Ling Liu <lingliu@cc.gatech.edu> Georgia Institute of Institute SGER: Distributed Spatial Partitioning Algorithms for Scalable Processing of Mobile Location Queries Monitoring and evaluation of location queries over mobile objects has become the necessity of many location-based applications, such as fleet management, cargo tracking, and location aware advertisement. Two predominant costs determine the system performance and scalability: the wireless communication cost for location updates of mobile clients and the location query evaluation cost at the database server. This research project designs and develops a distributed spatial locality aware architecture and a suite of spatial partitioning algorithms to minimize the cost of both location updates and location query evaluations, while providing efficient and scalable location-based services. The project first exploits the spatial locality by capitalizing on object safe region and query monitoring region, and then develops the techniques for carefully combining the query monitoring region with the object safe region and the algorithms for effectively partitioning the server loads and reducing the energy and bandwidth consumption. A proof-of-concept prototype is produced to demonstrate the advantages of the distributed spatial partitioning approach over the conventional server-centric approach or the pure peer to peer approach in terms of system efficiency and scalability. The resulting products are expected to have a significant practical impact on a broad range of present and future mobile location-based applications. The prototype implementation and experimental research will also be used as an educational tool for graduate and senior undergraduate courses covering mobile computing and advanced Internet application development and will be disseminated via the following Web site http://disl.cc.gatech.edu/MobiEyes/web.