空间数据库中距离连接选择率估计方法研究

Research on Distance Join Selectivity Estimation for Spatial Database

通过综合分析和比较现有的选择率估计技术,提出了基于MBR缓冲区和直方图的距离连接估计方法,该方法基于空间对象的MBR缓冲区,只需要简单计算几个直方图统计量,就可以快速得到较为准确的估计结果.针对MBR缓冲区方法估计结果偏大的不足,提出一种利用线段分布特性基本定律实现距离连接选择率估计的新方法.该方法基于线段缓冲区,不需要遍历线段数据集,提高了估计效率,减少了估计结果的相对误差.实验结果证明,该文方法能够准确有效地进行空间距离查询选择率估计并且更加适合真实的数据集.

Spatial join query is widely used in geographic information system. Accurate and fast selectivity estimation for spatial join is profitable for optimizing the ioin query. Incorporating exist selectivity estimation techniques, authors firstly propose a distance join selectivity estimation method based on MBR buffer and histogram. The method based on the MBR buffer can be used to obtain satisfying estimation results fast by computing only several statistics of histogram. Since these methods produce larger results than true value, a new selectivity estimation method for distance join based on line segment distribution characteristic is proposed to improve the estimation based on MBR buffer and histogram. Line segment distribution law is according to statistical characteristic of realistic datasets. Without traversing the line segment datasets, the method based on the line segment buffer provides accurate results enjoying less relative error. The experimental results show that the methods are more efficient for spatial distance query selectivity estimation, and especially more applicable to realistic datasets.