Computer Science Department
School of Computer Science, Carnegie Mellon University
Selectivity Estimation of Window Queries for Line Segment Datasets
Guido Proietti*, Christos Faloutsos
In this paper we move one significant step forward in line segment datasets theoretical analysis. We discovered that real lines closely follow a distribution law, that we named the SLED law (Segment LEngth Distribution). The SLED law can be used for an accurate estimation of the selectivity of window queries. Experiments on a variety of real line segment datasets (hydrographic systems, roadmaps, railroads, utilities networks) show that our law holds and that our formula is extremely accurate, enjoying a maximum relative error of 4% in estimating the selectivity.
*On leave from Dipartimento di Matematica Pura ed Applicata, University of L'Aquila, Via Vetoio, I-67010, Italy.