An accurate selectivity estimation method for window queries and an implementation thereof

作     者：Changxiu CHENG Jing YANG Xiaomei SONG Shanli YANG Lijun WANG 

作者机构：Academy of Disaster Reduction and Emergency ManagementBeijing Normal UniversityBeijing 100875China State Key Laboratory of Resources and Environmental Information SystemsInstitute of Geographic Science and Natural Resources ResearchChinese Academy of SciencesBeijing 100101China China Internet Network Information CenterBeijing 100101China 

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

年 卷 期：2015年第18卷第2期

页      面：81-89页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：This work was supported by the National Natural Science Foundation of China[grant numbers 41222009 41271405] 

主　　题：cumulative density(CD)histogram selectivity estimation window queries spatial database spatial query optimization 

摘      要：Spatial selectivity estimation is crucial to choose the cheapest execution plan for a given query in a query *** article proposes an accurate spatial selectivity estimation method based on the cumulative density(CD)histograms,which can deal with any arbitrary spatial query *** this method,the selectivity can be estimated in original logic of the CD histogram,after the four corner values of a query window have been accurately interpolated on the continuous surface of the elevation *** the interpolation of any corner points,we first identify the cells that can affect the value of point(x,y)in the CD *** cells can be categorized into two classes:ones within the range from(0,0)to(x,y)and the other overlapping the range from(0,0)to(x,y).The values of the former class can be used directly,whereas we revise the values of any cells falling in the latter class by the number of vertices in the corresponding cell and the area ratio covered by the range from(0,0)to(x,y).This revision makes the estimation method more *** CD histograms and estimation method have been implemented in *** results show that the method can accurately estimate the selectivity of arbitrary query windows and can help the optimizer choose a cheaper query plan.