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

Selectivity Estimation Based on Cumulative Annular Bucket Histogram in Spatial Database

作　　者：程昌秀[1] 胡夏天 宋晓眉[2] 陈驰[3] 

机构地区：[1]北京师范大学减灾与应急管理研究院,北京100875 [2]中国科学院地理科学与资源研究所,北京100101 [3]中国科学院信息工程研究所信息安全国家重点实验室,北京100093

出　　处：《武汉大学学报（信息科学版）》2016年第9期1183-1191,共9页Geomatics and Information Science of Wuhan University

基　　金：国家自然科学基金(41222009;41271405);信息安全国家重点实验室2013年开放课题(2013-03-02)~~

摘　　要：空间选择率估计是空间数据库查询优化的核心问题之一。现有空间直方图方法打破了空间面对象的完整性,难以实现精确拓扑谓词的选择率估计和空间直方图的查询推演。针对以上问题,本文提出了累计环形桶(annular bucket,AB)直方图,简称为累计AB直方图。该方法通过建立容纳空间面对象的"环形桶",保留了空间面对象的整体性,可以实现基于最小外接矩形(minimum bounding rectangle,MBR)顶点位置的精确拓扑关系查询和空间推演。介绍了累计AB直方图的生成方法及其面向空间关系谓词的选择率估算方法,并以土地利用数据为例,检验了累计AB直方图选择率估计的准确性,讨论了该方法的效率和适用范围。Selectivity estimation for spatial databases is a core scientific problem in query optimization.The exiting spatial histograms violate theintegrity of spatial objects,so it is difficult to precisely calculate the selectivity of spatial data to deduce the histograms of query results.In view of the above problems,we propose a forward cumulative annular bucket histogram,referred to as the cumulative AB histogram.This histogram establishes annular buckets to receive all spatial area objects.Therefore,it maintains the integrity of area objects and achieves better performance on the selectivity estimation and histogram deduction in fine spatial topological query.We discuss some theories of the cumulative AB-histogram in detail and propose selectivity estimation methods for fine topological queries.We take land use data as example to show accuracy of selectivity estimation and discusstopics relevant to the efficiency and scope of applications.

关 键 词：空间查询优化 选择率估计 累计AB直方图 空间选择查询 

分 类 号：P208[天文地球—地图制图学与地理信息工程]