Adaptive geospatial joins for modern hardware
2018
textabstractGeospatial 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 adaptive geospatial join that uses true hit
filtering to avoid expensive geometric computations in most
cases. Our technique uses a quadtree-based hierarchical grid
to approximate polygons and stores these approximations in a
specialized radix tree. We emphasize on an approximate version
of our algorithm that guarantees a user-defined precision. The
exact version of our algorithm can adapt to the expected point
distribution by refining the index. We optimized our implementation
for modern hardware architectures with wide SIMD vector
processing units, including Intel’s brand new Knights Landing.
Overall, our approach can perform up to two orders of magnitude
faster than existing techniques.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
15
References
8
Citations
NaN
KQI