Group Nearest Neighbor Queries Based on Voronoi Diagrams

Group nearest neighbor query is more complex than the traditional nearest neighbor query because it contains one more query points. Its objective is to find a data point that has the smallest sum of distances to all query points. The conditions that group nearest neighbor should be satisfied and the theories that valuate the group nearest neighbor are put forward, which are obtained by considering the distribution characteristics of query points and the qualities of geometric figures that they form. The VGNN algorithm is presented to deal with group nearest neighbor query based on Voronoi diagrams. It can get the query points' nearest neighbor exactly by using the VGNN algorithm. When the query points are non-collinear, the query way of the VGNN algorithm is firstly to estimate one data point that is the query points' nearest neighbor possible, and then to outspread around the data point to find the final result. And it also concludes the search region when the query points are collinear to limit the quantity of data points which are included in the computation. The VTree index grounded on Voronoi diagrams is brought forward. Experimental results show that the VGNN algorithm based on the VTree index has better performance, and it is more stable when the query points are non-collinear.