Selectivity Estimation of Window Queries for Line Segment Datasets

Abstract

Despite of the fact that large line segment datasets are becoming more and more popular, most of the analysis for estimating the selectivity of window queries posed on spatial data - the most important parameter for query optimization - has focused on point or region data only. 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, road maps, 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1998
Accession Number
ADA350434

Entities

People

  • Christos Faloutsos
  • Guido Proietti

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Accuracy
  • Amazon River
  • Aspect Ratio
  • Computer Science
  • Databases
  • Distribution Functions
  • Electronic Mail
  • Errors
  • Geographic Information Systems
  • Graphs
  • Information Science
  • Intervals
  • Railroads
  • Rivers
  • Sampling
  • Structural Properties
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Educational Psychology
  • Regression Analysis.