Continuous Group Nearest Group Query on Moving Objects

Given a data set P and a query set Q, a group nearest group (GNG) query returns a k-subset M of P such that M minimizes the total distance cost from each query point in Q to its closest point in M. In this paper we extend the GNG query to its dynamic version, which is called continuous group nearest group (CGNG) query. A hill climbing schemed algorithm, ADM, is proposed to efficiently solve CGNG problem. ADM achieves the fast converging speed by checking only qualified candidates. Experiments show that the performance of ADM dominates the classical algorithm PAM and CLARANS with different parameter settings.