Selectivity estimation is crucial for query optimizers choosing an optimal spatial execution plan in a spatial database management system.This paper presents an Annular Bucket spatial histogram(AB histogram)that can e...Selectivity estimation is crucial for query optimizers choosing an optimal spatial execution plan in a spatial database management system.This 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 joins.The AB histogram is represented as a set of bucket-range,bucket-count value pairs.The bucket-range often covers an annular region like a sin-gle-cell-sized photo frame.The bucket-count is the number of objects whose Minimum Bounding Rectangles(MBRs)fall between outer rectangle and inner rectangle of the bucket-range.Assuming 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 ranges.Thus,according to some probability theories,spatial selection or join selectivity can be estimated by the every bucket-count and its probabilities.This paper also shows a way to generate an updated AB histogram from an original AB histogram and those probabilities.Our 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.展开更多
Spatial relationships are core components in the design and definition of spatial queries.A spatial relationship determines how two or more spatial objects are related or connected in space.Hence,given a spatial datas...Spatial relationships are core components in the design and definition of spatial queries.A spatial relationship determines how two or more spatial objects are related or connected in space.Hence,given a spatial dataset,users can retrieve spatial objects in a given relationship with a search object.Different interpretations of spatial relationships are conceivable,leading to different types of relationships.The main types are(i)topological relationships(e.g.overlap,meet,inside),(ii)metric relationships(e.g.nearest neighbors),and(iii)direction relationships(e.g.cardinal directions).Although spatial information retrieval has been extensively studied in the literature,it is unclear which types of spatial queries can be defined using spatial relationships.In this article,we introduce a taxonomy for naming,describing,and classifying types of spatial queries frequently found in the literature.This taxonomy is based on the types of spatial relationships that are employed by spatial queries.By using this taxonomy,we discuss the intuitive descriptions,formal definitions,and possible implementation techniques of several types of spatial queries.The discussions lead to the identification of correspondences between types of spatial queries.Further,we identify challenges and open research topics in the spatial information retrieval area.展开更多
基金Supported by the Innovation Project of IGSNRR (No. O9V90220ZZ)the Research Plan of LREIS (O88RA700KA),CAS
文摘Selectivity estimation is crucial for query optimizers choosing an optimal spatial execution plan in a spatial database management system.This 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 joins.The AB histogram is represented as a set of bucket-range,bucket-count value pairs.The bucket-range often covers an annular region like a sin-gle-cell-sized photo frame.The bucket-count is the number of objects whose Minimum Bounding Rectangles(MBRs)fall between outer rectangle and inner rectangle of the bucket-range.Assuming 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 ranges.Thus,according to some probability theories,spatial selection or join selectivity can be estimated by the every bucket-count and its probabilities.This paper also shows a way to generate an updated AB histogram from an original AB histogram and those probabilities.Our 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.
基金financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior-Brasil(CAPES)-Finance Code 001.Anderson C.Carniel was supported by Google as a recipient of the 2022 Google Research Scholar program.
文摘Spatial relationships are core components in the design and definition of spatial queries.A spatial relationship determines how two or more spatial objects are related or connected in space.Hence,given a spatial dataset,users can retrieve spatial objects in a given relationship with a search object.Different interpretations of spatial relationships are conceivable,leading to different types of relationships.The main types are(i)topological relationships(e.g.overlap,meet,inside),(ii)metric relationships(e.g.nearest neighbors),and(iii)direction relationships(e.g.cardinal directions).Although spatial information retrieval has been extensively studied in the literature,it is unclear which types of spatial queries can be defined using spatial relationships.In this article,we introduce a taxonomy for naming,describing,and classifying types of spatial queries frequently found in the literature.This taxonomy is based on the types of spatial relationships that are employed by spatial queries.By using this taxonomy,we discuss the intuitive descriptions,formal definitions,and possible implementation techniques of several types of spatial queries.The discussions lead to the identification of correspondences between types of spatial queries.Further,we identify challenges and open research topics in the spatial information retrieval area.
