Analyzing range queries on spatial data

Ji Jin, Ning An, Anand Sivasubramaniam

Research output: Contribution to conferencePaperpeer-review

56 Scopus citations


Analysis of range queries on spatial (multidimensional) data is both important and challenging. Most previous analysis attempts have made certain simplifying assumptions about the datasets and/or queries to keep the analysis tractable. As a result, they may not be universally applicable. This paper proposes a set of five analysis techniques to estimate the selectivity and number of index nodes accessed in serving a range query. The underlying philosophy behind these techniques is to maintain an auxiliary data structure called a density file, whose creation is a onetime cost, which can be quickly consulted when the query is given. The schemes differ in what information is kept in the density file, how it is maintained, and how this information is looked up. It is shown that one of the proposed schemes, called Cumulative Density (CD), gives very accurate results (usually less than 5% error) using a diverse suite of point and rectangular datasets, that are uniform or skewed, and a wide range of query window parameters. The estimation takes a constant amount of time, which is typically lower than 1% of the time that it would take to execute the query, regardless of dataset or query window parameters.

Original languageEnglish (US)
Number of pages10
StatePublished - 2000
Event2000 IEEE 16th International Conference on Data Engineering (ICDE'00) - San Diego, CA, USA
Duration: Feb 29 2000Mar 3 2000


Conference2000 IEEE 16th International Conference on Data Engineering (ICDE'00)
CitySan Diego, CA, USA

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Analyzing range queries on spatial data'. Together they form a unique fingerprint.

Cite this