Please use this identifier to cite or link to this item:

Spatial query estimation without the local uniformity assumption

Authors Tao, Yufei
Faloutsos, Christos
Papadias, Dimitris View this author's profile
Issue Date 2006
Source Geoinformatica , v. 10, (3), 2006, SEP, p. 261-293
Summary Existing estimation approaches for spatial databases often rely on the assumption that data distribution in a small region is uniform, which seldom holds in practice. Moreover, their applicability is limited to specific estimation tasks under certain distance metric. This paper develops the Power-method, a comprehensive technique applicable to a wide range of query optimization problems under both L-infinity and L-2 metrics. The Power-method eliminates the local uniformity assumption and is, therefore, accurate even for datasets where existing approaches fail. Furthermore, it performs estimation by evaluating only one simple formula with minimal computational overhead. Extensive experiments confirm that the Power-method outperforms previous techniques in terms of accuracy and applicability to various optimization scenarios.
ISSN 1384-6175
Rights The original publication is available at
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
Geoinfo06LPL.pdf 536320 B Adobe PDF