On group nearest group query processing

Deng, Ke, Sadiq, Shazia, Zhou, Xiaofang, Xu, Hu, Fung, Gabriel Pui Cheong and Lu, Yansheng (2012) On group nearest group query processing. IEEE Transactions on Knowledge and Data Engineering, 24 2: 295-308. doi:10.1109/TKDE.2010.230

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Deng, Ke
Sadiq, Shazia
Zhou, Xiaofang
Xu, Hu
Fung, Gabriel Pui Cheong
Lu, Yansheng
Title On group nearest group query processing
Journal name IEEE Transactions on Knowledge and Data Engineering   Check publisher's open access policy
ISSN 1041-4347
Publication date 2012-02
Year available 2010
Sub-type Article (original research)
DOI 10.1109/TKDE.2010.230
Open Access Status
Volume 24
Issue 2
Start page 295
End page 308
Total pages 14
Place of publication New York , NY, U.S.A.
Publisher IEEE
Collection year 2013
Language eng
Formatted abstract
Given a data point set D, a query point set Q, and an integer κ, the Group Nearest Group (GNG) query finds a subset ω (|ω|≤ κ) of points from D such that the total distance from all points in Q to the nearest point in ω is not greater than any other subset ω′ |ω′| ≤ κ) of points in D. GNG query is a partition-based clustering problem which can be found in many real applications and is NP-hard. In this paper, Exhaustive Hierarchical Combination (EHC) algorithm and Subset Hierarchial Refinement (SHR) algorithm are developed for GNG query processing. While EHC is capable to provide the optimal solution for κ=2, SHR is an efficient approximate approach that combines database techniques with local search heuristic. The processing focus of our approaches is on minimizing the access and evaluation of subsets of cardinality κ in D since the number of such subsets is exponentially greater than |D|. To do that, the hierarchical blocks of data points at high level are used to find an intermediate solution and then refined by following the guided search direction at low level so as to prune irrelevant subsets. The comprehensive experiments on both real and synthetic data sets demonstrate the superiority of SHR in terms of efficiency and quality.
Keyword K-median Clustering
Group Nearest Group Query
Group Nearest Neighbor Query
Clustering algorithms
Knowledge engineering
Spatial databases
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ
Additional Notes Article # 5645619. Published online 16 November 2010.

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2013 Collection
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 6 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 11 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 13 May 2011, 23:42:25 EST by Ms Deborah Brian on behalf of School of Information Technol and Elec Engineering