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
N1 - Publisher Copyright:
© 2018 IEEE.
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 -