| 引用本文: | 杨泽雪,郝忠孝.受限空间连接查询及代价分析[J].哈尔滨工业大学学报,2012,44(11):118.DOI:10.11918/j.issn.0367-6234.2012.11.023 |
| YANG Ze-xue,HAO Zhong-xiao.Constrained spatial join queries and cost analysis[J].Journal of Harbin Institute of Technology,2012,44(11):118.DOI:10.11918/j.issn.0367-6234.2012.11.023 |
|
| 摘要: |
| 针对已有的空间连接查询算法无法解决限定范围内的空间连接查询问题,提出了受限的空间连接查询,在给定查询范围内找到满足某种空间谓词的空间对象,给出直接解决方法和基于R-树的受限空间连接查询算法．基于QR树的优良特性,提出一种基于QR树的受限空间连接查询算法,该算法既避免了四叉树的较大存储代价,又克服了R树的节点重复的弊端,使得受限空间连接查询可以在多棵较小的R树上进行,较好地解决了空间连接查询开销较大的问题．对所提出的算法进行代价分析,实验证明算法具有较高效率． |
| 关键词: 空间连接查询 QR树 空间数据库 R树 受限空间连接查询 |
| DOI：10.11918/j.issn.0367-6234.2012.11.023 |
| 分类号:TP311.13 |
| 基金项目:国家自然科学基金资助项目(60673136)；黑龙江省自然科学基金资助项目(F201134). |
|
| Constrained spatial join queries and cost analysis |
|
YANG Ze-xue1,2, HAO Zhong-xiao1,3
|
|
1.College of Computer Science and Technology, Harbin University of Science and Technology, 150080 Harbin,China ;2.Dept.of Computer Science and Technology, Heilongjiang Institute of Technology, 150050 Harbin,China ;3.College of Computer Science and Technology, Harbin Institute of Technology, 150001 Harbin, China
|
| Abstract: |
| 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 query on many small R-tree and the problem of expensive spatial join overhead is solved. The cost analysis for the proposed algorithms is given. Experiments show the algorithm has high efficiency. |
| Key words: spatial join query QR-tree spatial database R-tree constrained spatial join query |
