Spatial Join Selectivity Using Power Laws

摘要

We discovered a surprising law governing the spatial join selectivity across two sets of points. Our law dictates that the number of qualifying pairs follows a power law, whose exponent we call 'pair-count exponent' (PC). We show that this law also holds for self-spatial-joins ('find schools within 5 miles of other schools') in addition to the general case that the two point-sets are distinct. Our law holds for many real datasets, including diverse environments (geographic datasets, feature vectors from biology data, galaxy data from astronomy). In addition, we introduce the concept of the Box-Occupancy-Product-Sum (BOPS) plot, and we show that it can compute the pair-count exponent in a timely manner, reducing the run time by orders of magnitude, from quadratic to linear. Due to the pair-count exponent and our analysis (Law 1), we can achieve accurate selectivity estimates in constant time (0(1)) without the need for sampling or other expensive operations. The relative error in selectivity is about 30% with our fast BOPS method, and even better (about 10%), if we use the slower, quadratic method.