Processing Group Nearest Group Query
Ke Deng, Hu Xu, Shazia Wasim Sadiq, Yansheng Lu, Gabriel Pui Cheong Fung, Heng Tao Shen · Proceedings - International Conference on Data Engineering · 2009
Given a data point set D, a query point set Q and an integer k, the group nearest group (GNG) query finds a subset of points from D, omega (|omega| les k), such that the total distance from all points in Q to the nearest point in omega is no greater than any other subset of points in D, omega(|omega| les k). GNG query can be found in many real applications. In this paper, exhaustive hierarchical combination algorithm (EHC) and subset hierarchical refinement algorithm (SHR) are developed for GNG query processing. The superiority of SHR in terms of efficiency and quality compared to existing algorithms developed originally for data clustering is demonstrated.