杨泽雪，郝忠孝

（1.哈尔滨理工大学计算机科学与技术学院，150080 哈尔滨;2.黑龙江工程学院计算机科学与技术系，150050 哈尔滨;3.哈尔滨工业大学计算机科学与技术学院，150001 哈尔滨）

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

杨泽雪1，2，郝忠孝1，3

（1.哈尔滨理工大学计算机科学与技术学院，150080 哈尔滨;2.黑龙江工程学院计算机科学与技术系，150050 哈尔滨;3.哈尔滨工业大学计算机科学与技术学院，150001 哈尔滨）

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

空间连接查询;QR树;空间数据库;R树;受限空间连接查询

近年来空间连接查询成为空间数据库中的热点问题.给定两个空间数据集，空间连接查询找到两个数据集中所有满足某个空间谓词的对象.空间谓词包括交叠、相交、方向和距离等，本文主要研究相交的情况.例如:找到与某条河流相交的所有城市.按照两个空间数据集是否有索引，可以将空间连接查询分……