The Generic Annular Bucket Histogram for Estimating the Selectivity of Spatial Selection and Spatial Join

作     者：Changxiu Cheng Chenghu Zhou Rongguo Chen 

作者机构：State Key Laboratory of Resources and Environmental Information Systems Institute of Geographical Sciences and Natural Resources Research Chinese Academy of Sciences Beijing China 

出 版 物：《Geo-Spatial Information Science》 (地球空间信息科学学报（英文）)

年 卷 期：2011年第14卷第4期

页      面：262-273页

核心收录：

学科分类：0303[法学-社会学] 12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0709[理学-地质学] 08[工学] 0708[理学-地球物理学] 0705[理学-地理学] 0813[工学-建筑学] 0833[工学-城乡规划学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Supported by the Innovation Project of IGSNRR (No. O9V90220ZZ) the Research Plan of LREIS (O88RA700KA),CAS 

主　　题：selectivity estimation AB histogram annular bucket spatial selection spatial join 

摘      要：Selectivity estimation is crucial for query optimizers choosing an optimal spatial execution plan in a spatial database management *** paper presents an Annular Bucket spatial histogram(AB histogram)that can estimate the selectivity in finer spatial selection and spatial join operations even when the spatial query has more operators or more *** AB histogram is represented as a set of bucket-range,bucket-count value *** bucket-range often covers an annular region like a sin-gle-cell-sized photo *** bucket-count is the number of objects whose Minimum Bounding Rectangles(MBRs)fall between outer rectangle and inner rectangle of the *** that all MBRs in each a bucket distribute evenly,for every buck-et,we can obtain serial probabilities that satisfy a certain spatial selection or join conditions from the operations semantics and the spatial relations between every bucket-range and query ***,according to some probability theories,spatial selection or join selectivity can be estimated by the every bucket-count and its *** paper also shows a way to generate an updated AB histogram from an original AB histogram and those *** tests show that the AB histogram not only supports the selectivity estimation of spatial selection or spatial join with disjoint,intersect,within,contains,and overlap operators but also provides an approach to generate a reliable updated histogram whose spatial distribution is close to the distribution of ac-tual query result.