Scaling Location-based Services with Dynamically Composed Location Index

Performance and scalability of location-based services (LBSs) are crucial to the wide deployment of mobile enterprise systems. Location queries are a fundamental capability of LBSs. Conventional approaches to location query processing have been centered on an object-centric architecture where static and moving objects are processed under a unified framework through an object index or query index. In this paper, we identify and exploit the performance benefit of a location-centric framework by promoting a clean separation of location query processing over static objects from query processing over moving objects. We show the performance benefits of treating locations as first class citizens instead of objects. Concretely, we develop a federated location indexing scheme for processing location queries over static objects and maintain a grid-based object index for processing queries over moving objects. Our experimental results demonstrate that the location-centric framework enables highly efficient processing of different types of location queries in a mobile environment, prevails under all types of query workloads compared to the object-centric approaches, and in some scenarios it requires as low as only 6% of the IOs required by a corresponding object index for query evaluation.