HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item:
Title: Spatial query estimation without the local uniformity assumption
Authors: Tao, Yufei
Faloutsos, Christos
Papadias, Dimitris
Keywords: Databases
Range queries
Nearest neighbor
Issue Date: Sep-2006
Citation: GeoInformatica, v. 10, no. 3, September 2006, p. 261-293
Abstract: 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 and L2 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.
Rights: The original publication is available at
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
Geoinfo06LPL.pdfpre-published version523KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.