Spatial query processing on distributed databases

In recent years, with the ubiquity of location-aware mobile devices and widespread deployment of wireless networks, location-based services (LBSs) have become popular rapidly. Spatial queries, one useful LBS, enable users to query about the interested data objects near them. Due to the rapid growth in spatial data, it is challenging to index data objects and answer spatial queries. In this paper, we propose novel index structures and companion algorithms to efficiently solve representative spatial queries, namely kNN and window queries, in the case of vast amounts of data objects. The proposed index structures are built on the top of the distributed database HBase and are separately designed according to the characteristics of kNN and window queries. With the index structures, we devise efficient kNN and window query processing algorithms to achieve fast query search. The experimental results show that the proposed algorithms and the index structures are effective and efficient in solving kNN and window queries. Moreover, the results also demonstrate the scalability of the proposed algorithms and index structures.