GB-Tree: An efficient LBS location data indexing method

Location-Based Service (LBS) has become more and more important with the rapid development of mobile internet, it as an information service mainly make use of geographic position of mobile phone to provide accurate services for consumers. LBS involves a mass of longitude-latitude data and mainly involves three problems: Point Query, Range Query, and K-Nearest Neighbors. The object of this paper is to develop an efficient method to query the longitude-latitude data. After doing some research, we propose the GB-Tree, an indexing for longitude-latitude data capable of handling both range queries and k-nearest neighbors´ queries. GB-Tree is the combination of B+ Tree and GEOHASH algorithm to organize longitude-latitude data. So it retains all performance characteristics of B+ tree. For solving the range queries and k-nearest queries problems, we propose two algorithms based on GB-Tree index, which make good use of the structure of GB-Tree. In addition, we have done performance evaluation of the GB-Tree and the algorithms. The result of the experiments show the high efficiency. The latency of the algorithm is low enough to meet the needs of reality.