受限空间连接查询及代价分析  

Constrained spatial join queries and cost analysis

作　　者：杨泽雪[1,2] 郝忠孝[1,3] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080 [2]黑龙江工程学院计算机科学与技术系,哈尔滨150050 [3]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《哈尔滨工业大学学报》2012年第11期118-122,共5页Journal of Harbin Institute of Technology

基　　金：国家自然科学基金资助项目(60673136);黑龙江省自然科学基金资助项目(F201134)

摘　　要：针对已有的空间连接查询算法无法解决限定范围内的空间连接查询问题,提出了受限的空间连接查询,在给定查询范围内找到满足某种空间谓词的空间对象,给出直接解决方法和基于R-树的受限空间连接查询算法.基于QR树的优良特性,提出一种基于QR树的受限空间连接查询算法,该算法既避免了四叉树的较大存储代价,又克服了R树的节点重复的弊端,使得受限空间连接查询可以在多棵较小的R树上进行,较好地解决了空间连接查询开销较大的问题.对所提出的算法进行代价分析,实验证明算法具有较高效率.Aimed at the problem that the existed spatial join algorithms can not solve the spatial join query within the constrained range, the constrained spatial join query is proposed which finds all the pairs of objects satisfying some spatial predicate within the given range. The directed solving methods and algorithms based on R-tree are given. Based on good property of QR-tree, a constrained spatial join algorithm is proposed which avoids larger storage cost of quadtree and overcomes the drawbacks of R-tree node overlapping. Thus the algorithm implements the constrained spatial join join overhead is solved. The cost analysis for has high efficiency. query on many small R-tree and the problem of expensive the proposed algorithms is given. spatial Experiments show the algorithm has high efficiency.

关 键 词：空间连接查询 QR树 空间数据库 R树 受限空间连接查询 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]