Date Added: Nov 2012
Spatial index and query are enabling techniques for achieving the vision of the Internet of Things. K-NN is an algorithm which is used widely in spatial database. Traditional query algorithms use R-tree as the index structure and improve the query efficiency by using the measurement distance and pruning strategy. Based on the study of previous algorithms, this paper proposes a novel K-NN query algorithm based on PB-tree with the parallel lines division. PB-tree index is different from the traditional R-tree index, where PB-tree adopts parallel lines to divide the spatial region and uses parallel lines as the parent node. It is similar to the binary tree index structure and requires to query three small portions nearest to the queried object in each K-NN query.