留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用累计AB直方图进行空间选择率估计

程昌秀 胡夏天 宋晓眉 陈驰

程昌秀, 胡夏天, 宋晓眉, 陈驰. 利用累计AB直方图进行空间选择率估计[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1183-1191. doi: 10.13203/j.whugis20140627
引用本文: 程昌秀, 胡夏天, 宋晓眉, 陈驰. 利用累计AB直方图进行空间选择率估计[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1183-1191. doi: 10.13203/j.whugis20140627
CHENG Changxiu, HU Xiatian, SONG Xiaomei, CHEN Chi. Selectivity Estimation Based on Cumulative Annular Bucket Histogram in Spatial Database[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1183-1191. doi: 10.13203/j.whugis20140627
Citation: CHENG Changxiu, HU Xiatian, SONG Xiaomei, CHEN Chi. Selectivity Estimation Based on Cumulative Annular Bucket Histogram in Spatial Database[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1183-1191. doi: 10.13203/j.whugis20140627

利用累计AB直方图进行空间选择率估计

doi: 10.13203/j.whugis20140627
基金项目: 

国家自然科学基金 41222009

国家自然科学基金 41271405

信息安全国家重点实验室2013-开放课题 2013-03-02

详细信息
    作者简介:

    程昌秀,博士,教授,主要从事多尺度空间数据分析与表达。chengcx@bnu.edu.cn

  • 中图分类号: P208

Selectivity Estimation Based on Cumulative Annular Bucket Histogram in Spatial Database

Funds: 

The National Natural Science Foundation of China 41222009

The National Natural Science Foundation of China 41271405

the Open Research Fund Program of Key Laboratory of Information Security 2013-03-02

More Information
    Author Bio:

    CHENG Changxiu, PhD, professor, specializes in analysis and representation of multi-scale spatial data. E-mail: chengcx@bnu.edu.cn

  • 摘要: 空间选择率估计是空间数据库查询优化的核心问题之一。现有空间直方图方法打破了空间面对象的完整性,难以实现精确拓扑谓词的选择率估计和空间直方图的查询推演。针对以上问题,本文提出了累计环形桶(annular bucket,AB)直方图,简称为累计AB直方图。该方法通过建立容纳空间面对象的“环形桶”,保留了空间面对象的整体性,可以实现基于最小外接矩形(minimum bounding rectangle,MBR)顶点位置的精确拓扑关系查询和空间推演。介绍了累计AB直方图的生成方法及其面向空间关系谓词的选择率估算方法,并以土地利用数据为例,检验了累计AB直方图选择率估计的准确性,讨论了该方法的效率和适用范围。
  • 图  1  “环形桶”样例及其AB直方图

    Figure  1.  An Example of Annular Bucket and Its AB Histogram

    图  2  空间数据和格网编码

    Figure  2.  Spatial Data and Grid Encoding

    图  3  累计AB直方图及H[20, 33]的含义

    Figure  3.  Cumulative Annular Bucket Histogram and Meaning of H[20, 33]

    图  4  数据样例及其累计AB直方图的生成

    Figure  4.  Data Sample and Building Its Cumulative AB Histogram

    图  5  AB直方图到累计AB直方图的推导过程示意图

    Figure  5.  Diagram of AB Histogram to Cumulative AB Histogram

    图  6  包含于操作的算法演示图

    Figure  6.  Graphical Expression of Estimation Algorithm on the ‘Within’ Operator

    图  7  包含操作的算法演示图

    Figure  7.  Diagram of Estimation Algorithm on the ‘Contains’ Operator

    图  8  相交操作的算法演示图

    Figure  8.  Diagram of Estimation Algorithm on the ‘Intersects’ Operator

    图  9  交叉操作的算法演示图

    Figure  9.  Diagram of Estimation Algorithm on the ‘Crosses’ Operator

    图  10  实验数据和查询窗口

    Figure  10.  Test Data and Query Windows

    表  1  累计AB直方图选择操作结果统计

    Table  1.   Statistical Results of Selecting Operation Based on Cumulative AB-Histograms

    相交 包含于 包含 交叉 重叠 相离
    估计值 真值 错误率/% 估计值 真值 错误率/% 估计值 真值 错误率/% 估计值 真值 错误率/% 估计值 真值 错误率/% 估计值 真值 错误率/%
    1 69.97 80 -12.5 0 0 0 43.9 45 -2.4 1.73 3 -42.2 26 35 -25.6 4 428 4 418 0.2
    2 12.72 10 27.2 0.46 1 -53.6 4.29 2 114..3 0.46 0 7.97 7 13.8 4 485.3 4 488 -0.1
    3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 498 4 498 0
    4 2 139 2 130 0.4 0 0 0 1924 1916 0.4 0 0 0 215 214 0.4 2 359.1 2 368 -0.4
    5 647.8 645 0.4 0 0 0 535 526 1.8 0 0 0 112 119 -5.5 3 850.2 3 853 -0.1
    6 539.1 555 -2.9 0 0 0 458 475 -3.5 0 0 0 80.9 80 1.1 3 958.9 3 943 0.4
    7 473.7 485 -2.3 0 0 0 366 369 -0.9 0 0 0 108 116 -6.9 4 024.3 4 013 0.3
    8 340.9 350 -2.6 0 0 0 273 280 -2.5 1 1 0 68 70 -2.9 4 157.1 4 148 0.2
    9 362.5 380 -4.6 1 1 0 303 314 -3.5 0 0 0 58.5 65 -10.0 4 135.5 4 118 0.4
    10 169.9 172 -1.2 0 0 0 117 111 5.3 1.19 2 -40.5 53 61 -13.0 4 328.1 4 326 0
    11 103.8 104 -0.2 1 1 0 65.2 66 -1.2 0 0 0 37.6 37 1.7 4 394.2 4 394 0
    12 20.75 19 9.2 1 1 0 5.48 4 36.9 0 0 0 14.3 14 2.0 4 477.2 4 479 0
    13 316.6 317 -0.1 0 0 0 217 214 1.3 0 0 0 99.8 103 -3.1 4 181.4 4181 0
    14 345.4 353 -2.2 0 0 0 273 279 -2.2 0 0 0 72.6 74 -1.8 4 152.6 4 145 0.2
    15 414.2 418 -0.9 0 0 0 309 307 0.5 0 0 0 106 111 -4.8 4 083.8 4 080 0.1
    下载: 导出CSV
  • [1] 程昌秀. 空间数据库管理系统概论[M]. 北京: 科学出版社, 2012

    Cheng Changxiu. Spatial Database Management System[M].Beijing: Science Press,2012
    [2] Wu S, Li F, Mehrotra S. Query Optimization for Massively Parallel Data Processing[C]. The 2nd ACM Symposium on Cloud Computing, Cascais, Portugal, 2011
    [3] 吴胜利. 估算查询结果大小的直方图方法之研究[J]. 软件学报, 1998, 9(4):285-289 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB804.009.htm

    Wu Shengli. Histogram Method for Size Estimation of Query Result[J]. Journal of Sofeware,1998,9(4):285-289 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB804.009.htm
    [4] 朱焰炉, 程昌秀, 陈荣国. 基于直方图的空间查询选择率估计研究[J]. 计算机科学, 2010, 37(12): 125-130 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201012027.htm

    Zhu Yanlu, Cheng Changxiu, Chen Rongguo. Selectivity Estimation for Spatial Query Based on Histogram[J].Science of Compute,2010, 37(12): 125-130 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201012027.htm
    [5] 郭平, 陈海珠. 空间查询代价模型[J]. 计算机科学, 2004, 31(12): 65-68 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJA200412018.htm

    Guo Ping, Chen Haizhu. Cost Model of Spatial Queries[J]. Science of Computer, 2004, 3(12): 65-68 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJA200412018.htm
    [6] 程昌秀, 陈荣国, 朱焰炉. 一种基于窗口查询的空间选择率估算方法[J]. 武汉大学学报·信息科学版, 2010, 35(4): 399-403 http://ch.whu.edu.cn/CN/abstract/abstract904.shtml

    Cheng Changxiu, Chen Rongguo, Zhu Yanlu. Spatial Selectivity Estimation of Window Query[J]. Geomatics and Information Science of Wuhan University, 2010, 35(4): 399-403 http://ch.whu.edu.cn/CN/abstract/abstract904.shtml
    [7] 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
    [8] Jin J, An N. Analyzing Range Queries on Spatial Data[C]. The 16th International Conference on Data Engineering, San Diego, California, 2000
    [9] Sun C, Agrawal D, Abbadi A E. Selectivity Estimation for Spatial Joins with Geometric Selections[M]. Berlin, Heidelberg: Springer, 2002
    [10] An N, Yang Z Y, Sivasubramaniam A. Selectivity Estimation for Spatial Joins[C]. The 17th International Conference on Data Engineering, Chicago, USA, 2001
    [11] Cho B K. Spatial Selectivity Estimation Using Cumulative Density Wavelet Histogram [M]. Berlin, Heidelberg: Springer,2007
    [12] Chi J H, Kim S H, Keun H R. Spatial Selectivity Estimation Using Compressed Histogram Information [M]. Berlin, Heidelberg: Springer,2005
    [13] Poosala V, Haas P J, Ioannidis Y E, et al. Improved Histograms for Selectivity Estimation of Range Predicates[J]. ACM SIGMOD Record, 1996, 25(2): 294-305 doi:  10.1145/235968
    [14] Cheng C X, Song X M, Zhou C H. Generic Cumulative Annular Bucket Histogram for Spatial Selectivity Estimation of Spatial Database Management System[J]. International Journal of Geographical Information Science, 2013, 27(2): 339-362 doi:  10.1080/13658816.2012.698017
    [15] 金标, 胡文龙. 一种定量化表达的空间关系模型[J]. 武汉大学学报·信息科学版, 2013, 38(7): 879-882 http://ch.whu.edu.cn/CN/abstract/abstract2708.shtml

    Jin Biao, Hu Wenlong. A Quantified Model for Spatial Relationships[J]. Geomatics and Information Science of Wuhan University,2013,38(7):879-882 http://ch.whu.edu.cn/CN/abstract/abstract2708.shtml
  • [1] 邵振峰, 孙悦鸣, 席江波, 李岩.  智能优化学习的高空间分辨率遥感影像语义分割 . 武汉大学学报 ● 信息科学版, 2022, 47(2): 234-241. doi: 10.13203/j.whugis20200640
    [2] 崔家武, 张兴福, 周波阳, 杜向锋, 魏德宏.  改进的GNSS/水准点优化选择的逐步剔除法 . 武汉大学学报 ● 信息科学版, 2019, 44(10): 1505-1510. doi: 10.13203/j.whugis20180074
    [3] 陈迪, 朱欣焰, 周春辉, 苏科华.  区域分片下的分布式空间查询处理与并行调度方法 . 武汉大学学报 ● 信息科学版, 2012, 37(8): 892-896.
    [4] 付仲良, 刘思远.  MR-tree空间索引的Voronoi图改进及其并行空间查询方法 . 武汉大学学报 ● 信息科学版, 2012, 37(12): 1490-1494.
    [5] 朱忠敏, 余娟, 龚威.  Peterson模型的参数选择及优化 . 武汉大学学报 ● 信息科学版, 2011, 36(9): 1025-1029.
    [6] 梁丹, 童小华.  利用Kullback-Laible信息量的空间数据几何纠正模型选择 . 武汉大学学报 ● 信息科学版, 2011, 36(8): 896-899.
    [7] 邓敏, 黄雪萍, 刘慧敏, 李光强.  利用自然语言空间关系的空间查询方法研究 . 武汉大学学报 ● 信息科学版, 2011, 36(9): 1089-1093.
    [8] 钱程扬, 龙毅, 徐震, 孙昊.  基于Web文本的开放式空间信息查询 . 武汉大学学报 ● 信息科学版, 2010, 35(1): 83-87.
    [9] 程昌秀, 陈荣国, 朱焰炉.  一种基于窗口查询的空间选择率估算方法 . 武汉大学学报 ● 信息科学版, 2010, 35(4): 399-402.
    [10] 蓝贵文, 黄全义, 周晓青.  一种面向WFS服务的分布式空间连接查询优化策略 . 武汉大学学报 ● 信息科学版, 2009, 34(6): 654-658.
    [11] 韩鹏, 龚健雅, 李志林.  基于信息熵的遥感分类最优空间尺度选择方法 . 武汉大学学报 ● 信息科学版, 2008, 33(7): 676-679.
    [12] 邵黎霞, 何宗宜.  基于时空棱镜和活动场所吸引率的目的地选择研究 . 武汉大学学报 ● 信息科学版, 2007, 32(6): 481-484.
    [13] 叶志伟, 郑肇葆, 万幼川, 虞欣.  基于蚁群优化的特征选择新方法 . 武汉大学学报 ● 信息科学版, 2007, 32(12): 1127-1130.
    [14] 余亮, 边馥苓.  一种原生XML空间索引及查询语言 . 武汉大学学报 ● 信息科学版, 2006, 31(10): 936-939.
    [15] 黎展荣, 杨如军, 周新忠.  关系数据库管理空间数据的方式下数据查询方法的研究 . 武汉大学学报 ● 信息科学版, 2005, 30(12): 1104-1106.
    [16] 马林兵, 龚健雅.  空间信息自然语言查询接口的研究与应用 . 武汉大学学报 ● 信息科学版, 2003, 28(3): 301-305.
    [17] 黄波, 林珲.  GeoSQL:一种可视化空间扩展SQL查询语言 . 武汉大学学报 ● 信息科学版, 1999, 24(3): 199-203.
    [18] 李霖.  基于幂集的查询模型及其查询能力 . 武汉大学学报 ● 信息科学版, 1998, 23(4): 374-376.
    [19] 李成名, 陈军, 朱英浩.  基于Voronoi图的空间邻近定义与查询 . 武汉大学学报 ● 信息科学版, 1998, 23(2): 128-131.
    [20] 李霖.  空间数据库查询语言的特征 . 武汉大学学报 ● 信息科学版, 1997, 22(2): 107-110.
  • 加载中
图(10) / 表(1)
计量
  • 文章访问数:  814
  • HTML全文浏览量:  35
  • PDF下载量:  241
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-02-10
  • 刊出日期:  2016-09-05

利用累计AB直方图进行空间选择率估计

doi: 10.13203/j.whugis20140627
    基金项目:

    国家自然科学基金 41222009

    国家自然科学基金 41271405

    信息安全国家重点实验室2013-开放课题 2013-03-02

    作者简介:

    程昌秀,博士,教授,主要从事多尺度空间数据分析与表达。chengcx@bnu.edu.cn

  • 中图分类号: P208

摘要: 空间选择率估计是空间数据库查询优化的核心问题之一。现有空间直方图方法打破了空间面对象的完整性,难以实现精确拓扑谓词的选择率估计和空间直方图的查询推演。针对以上问题,本文提出了累计环形桶(annular bucket,AB)直方图,简称为累计AB直方图。该方法通过建立容纳空间面对象的“环形桶”,保留了空间面对象的整体性,可以实现基于最小外接矩形(minimum bounding rectangle,MBR)顶点位置的精确拓扑关系查询和空间推演。介绍了累计AB直方图的生成方法及其面向空间关系谓词的选择率估算方法,并以土地利用数据为例,检验了累计AB直方图选择率估计的准确性,讨论了该方法的效率和适用范围。

English Abstract

程昌秀, 胡夏天, 宋晓眉, 陈驰. 利用累计AB直方图进行空间选择率估计[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1183-1191. doi: 10.13203/j.whugis20140627
引用本文: 程昌秀, 胡夏天, 宋晓眉, 陈驰. 利用累计AB直方图进行空间选择率估计[J]. 武汉大学学报 ● 信息科学版, 2016, 41(9): 1183-1191. doi: 10.13203/j.whugis20140627
CHENG Changxiu, HU Xiatian, SONG Xiaomei, CHEN Chi. Selectivity Estimation Based on Cumulative Annular Bucket Histogram in Spatial Database[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1183-1191. doi: 10.13203/j.whugis20140627
Citation: CHENG Changxiu, HU Xiatian, SONG Xiaomei, CHEN Chi. Selectivity Estimation Based on Cumulative Annular Bucket Histogram in Spatial Database[J]. Geomatics and Information Science of Wuhan University, 2016, 41(9): 1183-1191. doi: 10.13203/j.whugis20140627
  • 随着计算机技术的发展以及中央处理器(central processing unit,CPU)处理能力的提高,硬件对优化空间查询操作的限制作用逐渐减弱,但是影响输入/输出(input/output,I/O)代价的选择率估计却显得越来越重要[1, 2]。查询结果大小(选择率)估算的准确性将直接影响查询优化器的效果[3]

    关于空间选择率估计的研究,国内外学者先后提出了采样法、分形法、索引法、直方图法等方法[4],其中,直方图法概念直观、实现简单,最为常用,在DB2、Ingres、Sybase等商用关系数据库中得到了应用,其基本思想是将数据空间按一定规则分为多个子空间,分别统计落入这些子空间中的对象数,然后根据预定的估计模型处理这些记录,得到选择率[5]。自1998年以来,先后出现了欧拉、MinSkew[6]、SQ[4, 7]、CD[8]、S-Euler[9]、EulerApprox[9]、GH[6]等多种空间直方图。

    空间直方图早期的研究重点是提高开窗查询的选择率估计精度,后来逐渐转移到面向精细拓扑谓词和空间连接操作上。CD直方图和欧拉直方图的选择率估计较为准确[6],但是它们只能估计相交和相离操作的选择率。扩展的欧拉直方图、PH直方图[4]以及GH直方图[4]可以近似估计空间拓扑关系和空间连接操作的选择率,但是模型的稳健性较差,仅对符合某些规律的数据的选择率估计有较高的准确性[10-12]。此外,这些直方图仅限于二维空间拓扑关系的研究,且缺少对方位关系和度量关系的研究[13]

    针对上述问题,作者提出累计AB直方图,并将累计AB直方图应用于空间选择、空间连接的选择率估计和空间推演[14],但缺少累计AB直方图具体实现过程的介绍,且未分析该方法在不同的应用中的特点,也未分析其适用范围、网格与精度的关系等。本文继承了累计AB直方图方法,阐述了累计AB直方图生成及其推理过程,分析了网格数目、数据复杂度与选择率估计精度之间的关系,并讨论了累计AB直方图可能的应用范围。

    • AB直方图将研究的数据空间划分为等大小的格网,但并不是简单地将这些格网视为“桶”来存放几何对象,而是将这些空间格网组成一个个的“环形桶”,统计落在这些“环形桶”内的最小外接矩形(minimum bounding rectangle,MBR)的个数。如图 1(a)所示,图中8个几何对象的MBR分别落入到“环形桶”ABCD中,其AB直方图如图 1(b)所示。直方图中的每个“桶”都记录了环形区域左下格网和右上格网的空间坐标,根据这些坐标信息和环形桶内几何对象均匀分布的假设,不难推理出8个对象的空间分布状态,也不难推理出几何对象与查询窗口满足不同拓扑关系的查询选择框。虽然推演出的空间分布状态与实际的空间分布可能仍存在细微差距,但是已经十分接近原始的空间分布。

      图  1  “环形桶”样例及其AB直方图

      Figure 1.  An Example of Annular Bucket and Its AB Histogram

      在创建AB直方图过程中,随着数据空间的增大和格网的细分,环形桶的数目将不断增多。如果每次估计都需要找出相关的“桶”后再进行推算选择率,将会导致大量的时间消耗。为了提高选择率的估算速度,本文提出了累计AB直方图。累计AB直方图不需要遍历每个“桶”,仅根据累计稀疏矩阵简单加减运算便可得到选择率,其计算时间复杂度为O(1),与数据空间中“桶”的个数无关。

      由于空间选择率表征空间过滤步骤选出的几何对象数,故在系列AB直方图中,几何对象用其MBR代替。

      图 2所示数据为例,首先将网格进行编码,为了便于描述,将编码映射函数定义为M(ij),其中i为行号,j为列号(ij从0开始计数)。对于一个行列数为m×n的格网空间,经过统计得到用m×n行、m×n列的矩阵表示的AB直方图,然后经过半累计AB直方图的过渡运算得到累计AB直方图。

      图  2  空间数据和格网编码

      Figure 2.  Spatial Data and Grid Encoding

      AB直方图矩阵中ABH[M(ia, ja),M(ib, jb)]表示左下(lower left,LL)点落入(ia, ja) 网格、右上(upper right,UR)点落入(ib, jb) 网格中的几何对象数;半累计直方图矩阵中SemiH[M(ia, ja),M(ib, jb)]表示左下点落在(0,0)到(ia, ja)矩形区域内,而右上点落在(ib, jb) 格网中的对象数;而累积AB直方图中H[M(ia, ja), M(ib, jb)]表示左下点落入(0,0)到(ia, ja)的矩形区域内,而右上点落入(0,0)到(ib, jb)的矩形区域内的对象数目。

      图 3(a)给出了图 2所示数据的累计AB直方图稀疏矩阵。其中,斜线填充的区域的单元格H[20, 33]=[M(3, 2),M(5, 3)]=4的含义是MBR的左下点起于(0,0)到(3,2)区域,右上点止于(0,0)到(5,3)区域的对象数为4,即图 3(b)中细点划线标出的几何对象。下文图中左下落入的区域均用正斜杠(/)填充,而右上落入区域用反斜杠(\)。

      图  3  累计AB直方图及H[20, 33]的含义

      Figure 3.  Cumulative Annular Bucket Histogram and Meaning of H[20, 33]

      图 3(a)可知累积AB直方图的稀疏矩阵有以下特点:

      1) 对于m×n的格网空间,累积AB直方图的稀疏矩阵的大小为m×n行、m×n列;

      2) 矩阵为斜上三角阵,在斜上方的每个m×n的小矩阵中也为斜上三角阵。因为MBR的左下点不会出现在右上点的右上方,所以上述矩阵的左斜下方的值均为0;

      3) 累计直方图每个小三角阵的右下方单元格的值一定不小于左上方单元格的值。

    • 首先初始化AB直方图、半累计AB直方图、累计AB直方图,将矩阵内的值赋为0;然后,依次读取几何对象,找到MBR的左下、右上点格网坐标,根据既定的编码映射函数M,以左下点格网编码为行号,右上点格网编码为列号,找到AB直方图的稀疏矩阵中对应位置的值,并加1,遍历完所有几何对象后,得到的稀疏矩阵即为AB直方图。以图 4(a)中情景为列,遍历两个几何对象的MBR后得到图 4(b)所示的AB直方图稀疏矩阵。

      图  4  数据样例及其累计AB直方图的生成

      Figure 4.  Data Sample and Building Its Cumulative AB Histogram

    • AB直方图(ABH)到累计AB直方图(H)的转换需要借助半累计直方图(SemiH)。具体公式为:

      (1)

      其中,等号右边的SemiH可以根据AB直方图的稀疏矩阵和式(1)逐步递推得到。式(1)的原理如图 5(a)所示。在图 5(a)中,(1)所示的SemiH[M(ia, ja),M(ib, jb)]值等于左下点起于(2)中正斜杠填充区域且右上点止于(2)中反斜杠区域的几何对象数,加上左下点起于(3)中正斜杠填充区域且右上点止于(3)反斜杠区域的几何对象数,加上左下点起于(4)中正斜杠填充区域且右上点止于(4)中反斜杠区域的几何对象数,再减去左下点起于(5)中正斜杠填充区域填充区域且右上点止于(5)中反斜杠区域的几何对象数(因为在前两次“+”操作中,该类几何对象被算了两次,故需要减去一次)。

      图  5  AB直方图到累计AB直方图的推导过程示意图

      Figure 5.  Diagram of AB Histogram to Cumulative AB Histogram

      在式(1)中,直方图的下标(例如,M(ia-1, ja)、M(ia, ja-1)、M(ia-1, ja-1)中的ia-1或者ja-1)小于0时,该直方图单元格的值视为0或忽略不计。因此,在实际运算中,式(1)存在如下几种变型:

      1) 当ia=0且ja=0时,SemiH[M(0,0), M(ib, jb)]=ABH[M(0,0), M(ib, jb)]。即半累计AB直方图的第一行等于AB直方图的第一行。

      2) 当ia=0且ja>0时,SemiH[M(0, ja), M(ib, jb)]=SemiH[M(0, ja-1), M(ib, jb)]+ABH[M(0, ja), M(ib, jb)]。即对于第一排斜三角阵的后续行,其中单元格的半累计直方图的值等于上一行对应的半累计直方图的值加上本单元的AB直方图的值。

      3) 当ia>0且ja=0时,SemiH[M(ia, 0), M(ib, jb)]=SemiH[M(ia-1,0), M(ib, jb)]+ABH[M(ia, 0), M(ib, jb)]。即对于下两排的斜三角的第一行,其中单元格的半累计直方图的值等于上一排斜三角阵第一行对应单元的半累计值加上本单元的AB直方图的值。

      4) 当ia>0且ja>0时,SemiH[M(ia, ja),M(ib, jb)]=SemiH[M(ia-1, ja), M(ib, jb)]+SemiH[M(ia, ja-1), M(ib, jb)]+ABH[M(ia, ja), M(ib, jb)]-SemiH[M(ia-1, ja-1), M(ib, jb)]。即后两排斜三角阵的非第一行单元格的半累计值等于上一排斜三角阵中对应单元格半累计值加上本行三角阵中上一行对应位置半累计值,再加上本单元格的AB直方图值,最后减去上一排斜三角阵中对应位置的前一排单元格的半累计值。

      经上述行运算后,图 4(b)中所示的AB直方图变为如图 4(c)所示的半累计AB直方图。

      从SemiHH的递推转换过程如图 5(b)所示,算法见式(2)。图 4(c)经该运算后得到其累计直方AB图如图 4(d)所示。

      (2)
    • 包含于、包含、相交、交错、相离、重叠是二维空间几何对象常见的6种拓扑关系[15]。当查询窗口与格网边界重合时,基于上述累计AB直方图,6种拓扑关系的选择率估计如下。

    • 若几何对象落在查询窗口内,则其MBR的左下点和右上点都应该落在查询窗口内,如图 6(1)中的虚线所示。累计直方图不能直接提供该情况下几何对象的数目,但是通过图 6中后续图示的累计AB直方图值可以算出位于该查询区域内的几何对象数;即落在查询窗口的对象数等于左下点和右上点落入(0,0)到(ib, jb)内的对象数(图 6(2) 所示),减去左下点落入(0,0)到(ib, ja-1)内、右上点落入(0,0)到(ib, jb)矩形内的对象数(图 6(3)所示),再减去左下点入(0,0)到(ia-1, jb)内、右上点落入(0,0)到(ib, jb)内的对象数(图 6(4)所示),由于左下点落入(0,0)到(ia-1, ja-1)、右上点落入 (0,0)到(ib, jb)矩形内的选择率减掉两次,所以再加上它。根据累计AB直方图的分析,得到选择率的计算公式为:

      图  6  包含于操作的算法演示图

      Figure 6.  Graphical Expression of Estimation Algorithm on the ‘Within’ Operator

      (3)
    • 若几何对象包含查询窗口,则其MBR的右上点应该在查询窗口的右上方,MBR的左下点应该在查询窗口的左下方。根据累计AB直方图的原理和过程示意图 7,可以得到包含关系的选择率计算公式为:

      图  7  包含操作的算法演示图

      Figure 7.  Diagram of Estimation Algorithm on the ‘Contains’ Operator

      (4)
    • 若几何对象与查询窗口相交,则查询窗口与几何对象的MBR之间必须存在公共部分。根据图 8所示的逻辑关系和累计AB直方图的含义,采用排除法,相交操作的选择率计算公式为:

      图  8  相交操作的算法演示图

      Figure 8.  Diagram of Estimation Algorithm on the ‘Intersects’ Operator

      (5)
    • 若若几何对象跨域查询窗口,包含图 9中交叉1(在列方向穿过)和交叉2(在行方向穿过)两种情况。同样,根据图 9的过程和累计AB直方图的含义,得到基于交叉操作的选择计算公式:

      图  9  交叉操作的算法演示图

      Figure 9.  Diagram of Estimation Algorithm on the ‘Crosses’ Operator

      (6)
    • 由于相离和相交操作是互补的,即非相交即相离,则相离的选择率计算公式如下:

      (7)
    • 由于与查询窗口相交的几何对象,又可被分为包含于、包含、交叉、重叠和相等。由于几何对象与查询窗口Equals的概率极小,本文认为其选择率可以忽略不计。此时,除重叠外,其他拓扑关系的选择率都可以用累计AB直方图算出;则重叠的选择率则可以由其他拓扑操作的选择率推出,具体公式为:

      (8)
    • 上述为查询窗口与格网线重合的情况,在实际应用中这种情况几乎不存在,因此需要考虑设计合理的公式调节估计值。假设查询窗口Q与直方图格网不重叠,查询窗口内包的直方图格网的最大矩形为Qi,查询窗口外框的直方图格网的最小矩形为Qo。假设Q的面积为AQi面积为AiQo的面积为Ao。AB直方图中假设误差是按照面积平均分布的,则直接计算精细谓词的选择率估计公式为:

      (9)
      (10)
      (11)
      (12)
    • 本文以图 10(a)所示的包含4 498个面的土地利用数据为例,图 10(b)为15个大小不一、位置各异的查询窗口,测试上述6种拓扑关系的选择率精度。实验将土地利用数据的二维空间分割成30×30的格网并建立累计AB直方图。

      图  10  实验数据和查询窗口

      Figure 10.  Test Data and Query Windows

      根据上述的选择率估计函数通过执行GSQL语句去估计MBR满足包含于、包含、相交、交叉、相离、重叠这6个拓扑关系的地类斑块的个数,执行结果的相对错误率通过((估计值-真值)/ 真值)来计算,实验结果见表 1

      表 1  累计AB直方图选择操作结果统计

      Table 1.  Statistical Results of Selecting Operation Based on Cumulative AB-Histograms

      相交 包含于 包含 交叉 重叠 相离
      估计值 真值 错误率/% 估计值 真值 错误率/% 估计值 真值 错误率/% 估计值 真值 错误率/% 估计值 真值 错误率/% 估计值 真值 错误率/%
      1 69.97 80 -12.5 0 0 0 43.9 45 -2.4 1.73 3 -42.2 26 35 -25.6 4 428 4 418 0.2
      2 12.72 10 27.2 0.46 1 -53.6 4.29 2 114..3 0.46 0 7.97 7 13.8 4 485.3 4 488 -0.1
      3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 498 4 498 0
      4 2 139 2 130 0.4 0 0 0 1924 1916 0.4 0 0 0 215 214 0.4 2 359.1 2 368 -0.4
      5 647.8 645 0.4 0 0 0 535 526 1.8 0 0 0 112 119 -5.5 3 850.2 3 853 -0.1
      6 539.1 555 -2.9 0 0 0 458 475 -3.5 0 0 0 80.9 80 1.1 3 958.9 3 943 0.4
      7 473.7 485 -2.3 0 0 0 366 369 -0.9 0 0 0 108 116 -6.9 4 024.3 4 013 0.3
      8 340.9 350 -2.6 0 0 0 273 280 -2.5 1 1 0 68 70 -2.9 4 157.1 4 148 0.2
      9 362.5 380 -4.6 1 1 0 303 314 -3.5 0 0 0 58.5 65 -10.0 4 135.5 4 118 0.4
      10 169.9 172 -1.2 0 0 0 117 111 5.3 1.19 2 -40.5 53 61 -13.0 4 328.1 4 326 0
      11 103.8 104 -0.2 1 1 0 65.2 66 -1.2 0 0 0 37.6 37 1.7 4 394.2 4 394 0
      12 20.75 19 9.2 1 1 0 5.48 4 36.9 0 0 0 14.3 14 2.0 4 477.2 4 479 0
      13 316.6 317 -0.1 0 0 0 217 214 1.3 0 0 0 99.8 103 -3.1 4 181.4 4181 0
      14 345.4 353 -2.2 0 0 0 273 279 -2.2 0 0 0 72.6 74 -1.8 4 152.6 4 145 0.2
      15 414.2 418 -0.9 0 0 0 309 307 0.5 0 0 0 106 111 -4.8 4 083.8 4 080 0.1

      表 1展现了在6组共计90个实验中,75个(占样本的83.3%)实验的选择率估计精度达95%以上。实验结果表明,累计AB直方图选择率估计具有较高的精度。对于精度低于95%的15个实验,本文发现导致误差偏高的原因主要有两种:一是由于有些实验查询结果集的真值较小,导致了误差计算公式中的基数过小、误差较大,例如1号窗口的交叉、2号窗口的包含于、10号的包含等;二是重叠相关操作的误差率较大,这主要是由于重叠的选择率是由其他拓扑关系选择率推算出来的,存在误差累计和放大的情况。

      网格单元的大小与累计AB直方图的估计精度也有密切的关系。通常来说,网格单元越小估计精度越高,但是对AB直方图的创建过程有一定影响,而对后期选择率估计不会造成太大的影响。本文所述方法可分为两阶段考虑,首先是直方图的创建,其次是选择率的估计。网格单元越小AB直方图越大,需要的存储空间也就越多,AB直方图的创建耗时越长。但是在存储容量不断增长的今天,精细网格的稀疏AB直方图存储应该不是问题。尽管AB直方图的创建耗时会比较长,但它的创建是在查询之前一次性创建,并在查询过程中永久存储,故在选择率估计时直接调用AB直方图,不会对后期选择率估计的效率造成影响。根据选择率估算公式可知,计算仅涉及直方图中几个数值的加减操作,其算法复杂度为O(1),与AB直方图的大小无关。

      根据上述分析,不难得知,随着查询数据量的不断加大,以及数据复杂性的增加,AB直方图的创建效率会受到影响,但对后期选择率估算的效率影响不大。

      本文实验仅给出了累计AB直方图方法用于面状对象的选择率估计,其实它也可以应用于线状地物。对于点对象的选择率估计采用早期提出的MinSkew就会有良好效果。累计AB直方图同样可以推广到三维空间查询中,即将在二维空间中表示MBR长、宽的点对拓展为表现空间三维对象的长、宽、高的点对,如此既能清楚表达空间位置的同时又不失去几何对象的完整性。

    • 累计AB直方图是一个较为通用且实用的空间直方图。它为空间选择操作的选择率估计提出了更好的解决方案。累计AB直方图方法中关于几何对象的描述和表示方法不仅能较好地反映空间面对象(矩形)的形状信息,也顾及了对象自身存在的逻辑方位,故它较好地保留了空间面对象的完整性,为精细拓扑谓词的选择率估计奠定了基础。同时,这种根据空间MBR对象量身定做的“环形桶”即具有一定规则又不断变化,它灵活保存了MBR对象顶点自身的方位关系,也有效控制了桶的数量。累计AB直方图为空间选择率研究提供了一种新思路。

      本文实验验证了累计AB直方图在空间选择操作中选择率估计的准确性,后续将进一步研究其在空间连接操作和直方图推演中的应用,研究其在空间方位关系、度量关系、空间关系模型[15]以及三维空间中的选择率估计。同时,为了适应并行计算机的发展趋势,在并行环境下的测试方法的效率也是下一步研究的重点。

参考文献 (15)

目录

    /

    返回文章
    返回