Geodetic distance queries on R-trees for indexing geographic data

Erich Schubert, Arthur Zimek, Hans Peter Kriegel

Publikation: Bidrag til bog/antologi/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

Geographic data have become abundantly available in the recent years due to the widespread deployment of GPS devices for example in mobile phones. At the same time, the data covered are no longer restricted to the local area of a single application, but often span the whole world. However, we do still use very rough approximations when indexing these data, which are usually stored and indexed using an equirectangular projection. When distances are measured using Euclidean distance in this projection, a non-neglibile error may occur. Databases are lacking good support for accelerated nearest neighbor queries and range queries in such datasets for the much more appropriate geodetic (great-circle) distance. In this article, we will show two approaches how a widely known spatial index structure - the R-tree - can be easily used for nearest neighbor queries with the geodetic distance, with no changes to the actual index structure. This allows existing database indexes immediately to be used with low distortion and highly efficient nearest neighbor queries and radius queries as well as window queries.

OriginalsprogEngelsk
TitelAdvances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings
RedaktørerM. A. Nascimento
ForlagSpringer
Publikationsdato13. aug. 2013
Sider146-164
ISBN (Trykt)978-3-642-40234-0
ISBN (Elektronisk)978-3-642-40235-7
DOI
StatusUdgivet - 13. aug. 2013
Udgivet eksterntJa
Begivenhed13th International Symposium on Spatial and Temporal Databases - Munich, Tyskland
Varighed: 21. aug. 201323. aug. 2013

Konference

Konference13th International Symposium on Spatial and Temporal Databases
LandTyskland
ByMunich
Periode21/08/201323/08/2013
NavnLecture Notes in Computer Science
Vol/bind8098
ISSN0302-9743

    Fingerprint

Citationsformater

Schubert, E., Zimek, A., & Kriegel, H. P. (2013). Geodetic distance queries on R-trees for indexing geographic data. I M. A. Nascimento (red.), Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings (s. 146-164). Springer. Lecture Notes in Computer Science, Bind. 8098 https://doi.org/10.1007/978-3-642-40235-7_9