A spatial indexing approach for high performance location based services

Abstract

The rapid development of positioning technology, wireless communication and mobile devices has given rise to the exciting Location Based Services (LBS) thus significantly influencing existing navigational procedures. Motivated by the increasing need to search efficiently through a huge number of service locations (e.g. restaurants, hotels, shops, and more), this paper presents an efficient spatial index QR-tree, a hybrid index structure of Quadtree and R-tree, instead of the exhaustive search to improve the performance in response to user queries. QR-tree consists of two levels: the upper level is a Quadtree residing in the main memory which partitions the data space and the lower level is disk-resident R-trees assigned to the subspaces resulting from the partitioning process. Computational experiments show that the hybrid index structure is able to reduce query response time by up to 30% and achieve significant improvement on data update over the conventional indexing methods, thereby providing an effective option for efficient navigation services. © 2007 The Royal Institute of Navigation.