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

Selectivity Estimation Based on Cumulative Annular Bucket Histogram in Spatial Database

空间选择率估计是空间数据库查询优化的核心问题之一。现有空间直方图方法打破了空间面对象的完整性,难以实现精确拓扑谓词的选择率估计和空间直方图的查询推演。针对以上问题,本文提出了累计环形桶(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.