Computer Science Department
School of Computer Science, Carnegie Mellon University
Spatial Join Selectivity Using Power Laws
Christof Faloutsos, Bernhard Seeger*, Agma Traina**, Caetano Traina, Jr.**
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 (O(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.
*Fachbereich Mathematik und Informatik, Universitaet Marburg, Germany