|
|
- 2016
利用累计AB直方图进行空间选择率估计
|
Abstract:
空间选择率估计是空间数据库查询优化的核心问题之一。现有空间直方图方法打破了空间面对象的完整性，难以实现精确拓扑谓词的选择率估计和空间直方图的查询推演。针对以上问题，本文提出了累计环形桶（annular bucket，AB）直方图，简称为累计AB直方图。该方法通过建立容纳空间面对象的“环形桶”，保留了空间面对象的整体性，可以实现基于最小外接矩形（minimum bounding rectangle，MBR）顶点位置的精确拓扑关系查询和空间推演。介绍了累计AB直方图的生成方法及其面向空间关系谓词的选择率估算方法，并以土地利用数据为例，检验了累计AB直方图选择率估计的准确性，讨论了该方法的效率和适用范围
| [1] | Aboulnaga A, Naughton J F. Accurate Estimation of the Cost of Spatial Selections[C]. The 16th International Conference on Data Engineering, San Diego, California, 2000 |
| [2] | An N, Yang Z Y, Sivasubramaniam A. Selectivity Estimation for Spatial Joins[C]. The 17th International Conference on Data Engineering, Chicago, USA, 2001 |
| [3] | Cho B K. Spatial Selectivity Estimation Using Cumulative Density Wavelet Histogram [M]. Berlin, Heidelberg: Springer,2007 |
| [4] | Cheng Changxiu. Spatial Database Management System[M].Beijing: Science Press,2012(程昌秀. 空间数据库管理系统概论[M]. 北京: 科学出版社, 2012) |
| [5] | Wu S, Li F, Mehrotra S. Query Optimization for Massively Parallel Data Processing[C]. The 2nd ACM Symposium on Cloud Computing, Cascais, Portugal, 2011 |
| [6] | Guo Ping, Chen Haizhu. Cost Model of Spatial Queries[J]. Science of Computer, 2004, 3(12): 65-68(郭平, 陈海珠. 空间查询代价模型[J]. 计算机科学, 2004, 31(12): 65-68) |
| [7] | Chi J H, Kim S H, Keun H R. Spatial Selectivity Estimation Using Compressed Histogram Information [M]. Berlin, Heidelberg: Springer,2005 |
| [8] | Poosala V, Haas P J, Ioannidis Y E, et al. Improved Histograms for Selectivity Estimation of Range Predicates[J]. <em>ACM SIGMOD Record</em>, 1996, 25(2): 294-305 |
| [9] | Zhu Yanlu, Cheng Changxiu, Chen Rongguo. Selectivity Estimation for Spatial Query Based on Histogram[J].<em>Science of Compute,</em>2010, 37(12): 125-130(朱焰炉, 程昌秀, 陈荣国. 基于直方图的空间查询选择率估计研究[J]. 计算机科学, 2010, 37(12): 125-130) |
| [10] | Jin J, An N. Analyzing Range Queries on Spatial Data[C]. The 16th International Conference on Data Engineering, San Diego, California, 2000 |
| [11] | Cheng C X, Song X M, Zhou C H. Generic Cumulative Annular Bucket Histogram for Spatial Selectivity Estimation of Spatial Database Management System[J]. <em>International Journal of Geographical Information Science</em>, 2013, 27(2): 339-362 |
| [12] | Wu Shengli. Histogram Method for Size Estimation of Query Result[J]. <em>Journal of Sofeware</em>,1998,9(4):285-289(吴胜利. 估算查询结果大小的直方图方法之研究[J]. 软件学报, 1998, 9(4):285-289) |
| [13] | Cheng Changxiu, Chen Rongguo, Zhu Yanlu. Spatial Selectivity Estimation of Window Query[J]. <em>Geomatics and Information Science of Wuhan University,</em>2010, 35(4): 399-403(程昌秀, 陈荣国, 朱焰炉. 一种基于窗口查询的空间选择率估算方法[J]. 武汉大学学报·信息科学版, 2010, 35(4): 399-403) |
| [14] | Sun C, Agrawal D, Abbadi A E. Selectivity Estimation for Spatial Joins with Geometric Selections[M]. Berlin, Heidelberg: Springer, 2002 |
| [15] | Jin Biao, Hu Wenlong. A Quantified Model for Spatial Relationships[J]. <em>Geomatics and Information Science of Wuhan University</em>,2013,38(7):879-882(金标, 胡文龙. 一种定量化表达的空间关系模型[J]. 武汉大学学报·信息科学版, 2013, 38(7): 879-882) |
