Group Obstacle Nearest Neighbor Query in Spatial Database

Existing research work on group nearest neighbor query is based on Euclidean distance, which can not solve the nearest neighbor query problem based on obstructed distance in the case of presence of obstacles.A new variant of group nearest neighbor query in obstacle environments is proposed, that is, group obstacle nearest neighbor query. It retrieves a data point from dataset with the smallest sum of obstructed distances to all query points.According to the different positional relationships between a point in the dataset and MBR of query points, the pruning regions for MBR of query points to the point in the dataset in various circumstances are constructed.By using the pruning regions, the obstacles of no effect on obstructed distance calculation are cut.And the obstructed distance calculation algorithm between the point in the dataset and query points is given.The pruning rules of group obstacle nearest neighbor query are defined, which contain the Euclidean distance pruning rules and obstructed distance pruning rules.The GONN algorithm for group obstacle nearest neighbor query is put forward, which is based on the BF traversal of R-tree for dataset and combines the pruning rules and the obstructed distance calculation algorithm.The proofs of the algorithm's correctness and termination are brought forward, and time complexity analysis is given.Experimental results show that the algorithm has high efficiency.