  Spatial approximations have been traditionally used in spatial databases to
accelerate the processing of complex geometric operations. However,
approximations are typically only used in a first filtering step to determine a
set of candidate spatial objects that may fulfill the query condition. To
provide accurate results, the exact geometries of the candidate objects are
tested against the query condition, which is typically an expensive operation.
Nevertheless, many emerging applications (e.g., visualization tools) require
interactive responses, while only needing approximate results. Besides,
real-world geospatial data is inherently imprecise, which makes exact data
processing unnecessary. Given the uncertainty associated with spatial data and
the relaxed precision requirements of many applications, this vision paper
advocates for approximate spatial data processing techniques that omit exact
geometric tests and provide final answers solely on the basis of (fine-grained)
approximations. Thanks to recent hardware advances, this vision can be realized
today. Furthermore, our approximate techniques employ a distance-based error
bound, i.e., a bound on the maximum spatial distance between false (or missing)
and exact results which is crucial for meaningful analyses. This bound allows
to control the precision of the approximation and trade accuracy for
performance.
