Spatial join for high-resolution objects

Modern database applications including computer-aided design (CAD), medical imaging, molecular biology, or Multimedia Information Systems impose new requirements on efficient spatial query processing. One of the most common query types in Spatial Database Management Systems is the spatial join. In this paper, we investigate spatial join processing for two sets of very complex spatial objects. We present an approach that is based on a fast filter step performing the spatial join on simple primitives which conservatively approximate the objects. Our main attention is focused on the problem how to generate approximations adequate for high-resolution objects. In this paper, we introduce gray approximations as a general concept which helps to range between replicating and non-replicating object approximations. The key idea of our approach is to build these replications based on statistical information taking the data distribution of the respective join-partner relation into account. Furthermore, our approach uses compression techniques for the effective storage and retrieval of the decomposed spatial objects. We demonstrate the benefits of our new method for the spatial intersection join on high resolution data. The experimental evaluation on real-world test data points out that our new concept accelerates the spatial intersection join considerably. 1