Geospatial joins are a core building block of con- nected 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.

IEEE International Conference on Data Engineering
Database Architectures

Kipf, A, Lang, H, Pandey, V.N, Persa, R.A, Boncz, P.A, Neumann, T, & Kemper, A. (2018). Approximate geospatial joins with precision guarantees. In Proceedings of the International Conference on Data Engineering.