The Case for Distance-Bounded Spatial
Link to original publication 
Download Bibtex entry
Tzirita Zacharatou, Andreas Kipf, Ibrahim Sabek, Varun Pandey, Harish
Doraiswamy, Volker Markl
recording of the presentation is available here:
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.
------ Links: ------