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

摘要

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.%针对已有的空间连接查询算法无法解决限定范围内的空间连接查询问题，提出了受限的空间连接查询，在给定查询范围内找到满足某种空间谓词的空间对象，给出直接解决方法和基于R-树的受限空间连接查询算法．基于QR树的优良特性，提出一种基于QR树的受限空间连接查询算法，该算法既避免了四叉树的较大存储代价，又克服了R树的节点重复的弊端，使得受限空间连接查询可以在多棵较小的R树上进行，较好地解决了空间连接查询开销较大的问题．对所提出的算法进行代价分析，实验证明算法具有较高效率．