Geodetic distance queries on R-trees for indexing geographic data

Erich Schubert, Arthur Zimek, Hans Peter Kriegel

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationAdvances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings
EditorsM. A. Nascimento
PublisherSpringer
Publication date13. Aug 2013
Pages146-164
ISBN (Print)978-3-642-40234-0
ISBN (Electronic)978-3-642-40235-7
DOIs
Publication statusPublished - 13. Aug 2013
Externally publishedYes
Event13th International Symposium on Spatial and Temporal Databases - Munich, Germany
Duration: 21. Aug 201323. Aug 2013

Conference

Conference13th International Symposium on Spatial and Temporal Databases
CountryGermany
CityMunich
Period21/08/201323/08/2013
SeriesLecture Notes in Computer Science
Volume8098
ISSN0302-9743

Fingerprint

Mobile phones
Global positioning system

Cite this

Schubert, E., Zimek, A., & Kriegel, H. P. (2013). Geodetic distance queries on R-trees for indexing geographic data. In M. A. Nascimento (Ed.), Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings (pp. 146-164). Springer. Lecture Notes in Computer Science, Vol.. 8098 https://doi.org/10.1007/978-3-642-40235-7_9
Schubert, Erich ; Zimek, Arthur ; Kriegel, Hans Peter. / Geodetic distance queries on R-trees for indexing geographic data. Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings. editor / M. A. Nascimento. Springer, 2013. pp. 146-164 (Lecture Notes in Computer Science, Vol. 8098).
@inproceedings{6f7088cf65ff4d76ad8af49d49fca268,
title = "Geodetic distance queries on R-trees for indexing geographic data",
abstract = "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.",
author = "Erich Schubert and Arthur Zimek and Kriegel, {Hans Peter}",
year = "2013",
month = "8",
day = "13",
doi = "10.1007/978-3-642-40235-7_9",
language = "English",
isbn = "978-3-642-40234-0",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "146--164",
editor = "Nascimento, {M. A.}",
booktitle = "Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings",
address = "Germany",

}

Schubert, E, Zimek, A & Kriegel, HP 2013, Geodetic distance queries on R-trees for indexing geographic data. in MA Nascimento (ed.), Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings. Springer, Lecture Notes in Computer Science, vol. 8098, pp. 146-164, 13th International Symposium on Spatial and Temporal Databases, Munich, Germany, 21/08/2013. https://doi.org/10.1007/978-3-642-40235-7_9

Geodetic distance queries on R-trees for indexing geographic data. / Schubert, Erich; Zimek, Arthur; Kriegel, Hans Peter.

Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings. ed. / M. A. Nascimento. Springer, 2013. p. 146-164 (Lecture Notes in Computer Science, Vol. 8098).

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - Geodetic distance queries on R-trees for indexing geographic data

AU - Schubert, Erich

AU - Zimek, Arthur

AU - Kriegel, Hans Peter

PY - 2013/8/13

Y1 - 2013/8/13

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-40235-7_9

DO - 10.1007/978-3-642-40235-7_9

M3 - Article in proceedings

AN - SCOPUS:84881246465

SN - 978-3-642-40234-0

T3 - Lecture Notes in Computer Science

SP - 146

EP - 164

BT - Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings

A2 - Nascimento, M. A.

PB - Springer

ER -

Schubert E, Zimek A, Kriegel HP. Geodetic distance queries on R-trees for indexing geographic data. In Nascimento MA, editor, Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings. Springer. 2013. p. 146-164. (Lecture Notes in Computer Science, Vol. 8098). https://doi.org/10.1007/978-3-642-40235-7_9