Efficient k-Closest-Pair Range-Queries in Spatial Databases

摘要：

In order to efficiently retrieve the k-closest pairs between two spatial data sets in a specified space, such as in GIS and CAD applications, we propose a novel algorithm to handle the k-closest-pair range-query problem by progressively augmenting the query window instead of finding all objects in the whole space. We first describe a specific range estimation method to compute the circle query range which helps eliminate the unnecessary distance calculations among spatial objects and improve performance. Then, we use R*-tree to store closest pairs and give algorithms for maintaining this structure. Extensive experiments performed with synthetic as well as with real data sets show that the new algorithm outperforms the existing approaches in most cases. In particular, this technique works well when two spatial data sets are identical.

作者: Shaojie Qiao Changjie Tang Jing Peng Hongjun Li Shengqiao Ni

作者单位: School of Computer Science Sichuan University

会议类型: 国际会议

会议名称: The Ninth International Conference on Web-Age Information Management(第九届web时代信息管理国际会议)(WAIM 2008)

会议地点: 张家界

会议语种:英文

在线出版日期: 2008-07-20（万方平台首次上网日期，不代表论文的发表时间）