Approximate geospatial joins with precision guarantees

Andreas Kipf; Harald Lang; Varun Pandey; Raul Alexandru Persa; Peter Boncz; Thomas Neumann; Alfons Kemper

doi:10.1109/ICDE.2018.00150

Approximate geospatial joins with precision guarantees

Andreas Kipf, Harald Lang, Varun Pandey, Raul Alexandru Persa, Peter Boncz, Thomas Neumann, Alfons Kemper

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

12 Scopus citations

Abstract

Geospatial joins are a core building block of connected mobility applications. An especially challenging problem are joins between streaming points and static polygons. Since points are not known beforehand, they cannot be indexed. Nevertheless, points need to be mapped to polygons with low latencies to enable real-Time feedback. We present an approximate geospatial join that guarantees a user-defined precision. Our technique uses a quadtree-based hierarchical grid to approximate polygons and stores these approximations in a specialized radix tree. Our approach can perform up to several orders of magnitude faster than existing techniques while providing sufficiently precise results for many applications.

Original language	English
Title of host publication	Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1364-1367
Number of pages	4
ISBN (Electronic)	9781538655207
DOIs	https://doi.org/10.1109/ICDE.2018.00150
State	Published - 24 Oct 2018
Event	34th IEEE International Conference on Data Engineering, ICDE 2018 - Paris, France Duration: 16 Apr 2018 → 19 Apr 2018

Publication series

Name	Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018

Conference

Conference	34th IEEE International Conference on Data Engineering, ICDE 2018
Country/Territory	France
City	Paris
Period	16/04/18 → 19/04/18

Keywords

Approximate Query Processing
Geospatial Joins
Main Memory Database Systems

Access to Document

10.1109/ICDE.2018.00150

Cite this

Kipf, A., Lang, H., Pandey, V., Persa, R. A., Boncz, P., Neumann, T., & Kemper, A. (2018). Approximate geospatial joins with precision guarantees. In Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018 (pp. 1364-1367). Article 8509371 (Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICDE.2018.00150

@inproceedings{f0d0e16d8f6347ca911fa45432d36648,

title = "Approximate geospatial joins with precision guarantees",

abstract = "Geospatial joins are a core building block of connected mobility applications. An especially challenging problem are joins between streaming points and static polygons. Since points are not known beforehand, they cannot be indexed. Nevertheless, points need to be mapped to polygons with low latencies to enable real-Time feedback. We present an approximate geospatial join that guarantees a user-defined precision. Our technique uses a quadtree-based hierarchical grid to approximate polygons and stores these approximations in a specialized radix tree. Our approach can perform up to several orders of magnitude faster than existing techniques while providing sufficiently precise results for many applications.",

keywords = "Approximate Query Processing, Geospatial Joins, Main Memory Database Systems",

author = "Andreas Kipf and Harald Lang and Varun Pandey and Persa, {Raul Alexandru} and Peter Boncz and Thomas Neumann and Alfons Kemper",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 34th IEEE International Conference on Data Engineering, ICDE 2018 ; Conference date: 16-04-2018 Through 19-04-2018",

year = "2018",

month = oct,

day = "24",

doi = "10.1109/ICDE.2018.00150",

language = "English",

series = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1364--1367",

booktitle = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",

}

Kipf, A, Lang, H, Pandey, V, Persa, RA, Boncz, P, Neumann, T & Kemper, A 2018, Approximate geospatial joins with precision guarantees. in Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018., 8509371, Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018, Institute of Electrical and Electronics Engineers Inc., pp. 1364-1367, 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, 16/04/18. https://doi.org/10.1109/ICDE.2018.00150

Approximate geospatial joins with precision guarantees. / Kipf, Andreas; Lang, Harald; Pandey, Varun et al.
Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 1364-1367 8509371 (Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Approximate geospatial joins with precision guarantees

AU - Kipf, Andreas

AU - Lang, Harald

AU - Pandey, Varun

AU - Persa, Raul Alexandru

AU - Boncz, Peter

AU - Neumann, Thomas

AU - Kemper, Alfons

PY - 2018/10/24

Y1 - 2018/10/24

N2 - Geospatial joins are a core building block of connected mobility applications. An especially challenging problem are joins between streaming points and static polygons. Since points are not known beforehand, they cannot be indexed. Nevertheless, points need to be mapped to polygons with low latencies to enable real-Time feedback. We present an approximate geospatial join that guarantees a user-defined precision. Our technique uses a quadtree-based hierarchical grid to approximate polygons and stores these approximations in a specialized radix tree. Our approach can perform up to several orders of magnitude faster than existing techniques while providing sufficiently precise results for many applications.

AB - Geospatial joins are a core building block of connected mobility applications. An especially challenging problem are joins between streaming points and static polygons. Since points are not known beforehand, they cannot be indexed. Nevertheless, points need to be mapped to polygons with low latencies to enable real-Time feedback. We present an approximate geospatial join that guarantees a user-defined precision. Our technique uses a quadtree-based hierarchical grid to approximate polygons and stores these approximations in a specialized radix tree. Our approach can perform up to several orders of magnitude faster than existing techniques while providing sufficiently precise results for many applications.

KW - Approximate Query Processing

KW - Geospatial Joins

KW - Main Memory Database Systems

UR - http://www.scopus.com/inward/record.url?scp=85050279464&partnerID=8YFLogxK

U2 - 10.1109/ICDE.2018.00150

DO - 10.1109/ICDE.2018.00150

M3 - Conference contribution

AN - SCOPUS:85050279464

T3 - Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018

SP - 1364

EP - 1367

BT - Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 34th IEEE International Conference on Data Engineering, ICDE 2018

Y2 - 16 April 2018 through 19 April 2018

ER -

Kipf A, Lang H, Pandey V, Persa RA, Boncz P, Neumann T et al. Approximate geospatial joins with precision guarantees. In Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018. Institute of Electrical and Electronics Engineers Inc. 2018. p. 1364-1367. 8509371. (Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018). doi: 10.1109/ICDE.2018.00150

Approximate geospatial joins with precision guarantees

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this