Paper Info
Title
Selectivity Estimation for Spatial Joins
Abstract
Spatial Joins are important and time consuming operations in spatial database management systems. It is crucial to be able to accurately estimate the performance of these operations so that one can derive efficient query execution plans, and even develop/refine data structures to improve their performance. While estimation techniques for analyzing the performance of other operations, such as range queries, on spatial data has come under scrutiny the problem of estimating selectivity for spatial joins has been little explored. The limited forays Bite this area hare used parametric techniques, which are largely restrictive on the data sets that they carl be used for since they tend to make simplifying assumptions about the nature of the datasets to be joined Sampling and histogram based techniques, on the other hand, are much less restrictive. However, there has been no prior attempt at understanding the accuracy of sampling techniques, or developing histogram based techniques to estimate the selectivity of spatial joins. Apart from extensively evaluating the accuracy of sampling techniques for the very first time, this paper presents two novel histogram based solutions for spatial join estimation. Using a wide spectrum of both real and synthetic datasets, it is shown that one of our proposed schemes, called Geometric Histograms (GH), cart accurately quantify the selectivity of spatial joins.
Year
DOI
Venue
2001
10.1109/ICDE.2001.914849
ICDE
Keywords
Field
DocType
sampling technique,spectrum,spatial data,performance,data structure,data engineering,sampling techniques,range query,range queries,histograms,database systems,sampling methods,data structures,management system,spatial database,computer science
Spatial analysis,Histogram,Data structure,Data mining,Joins,Computer science,Range query (data structures),Sampling (statistics),Spatial query,Spatial database,Database
Conference
ISSN
ISBN
Citations 
1084-4627
0-7695-1001-9
18
PageRank 
References 
Authors
0.82
20
3
Name
Order
Citations
PageRank
Ning An139836.33
Zhen-Yu Yang2180.82
Anand Sivasubramaniam34485291.86