Approximate Query Processing in Spatial Databases Using Raster Signatures

Traditional query processing provides exact answers to queries trying to maximize throughput while minimizing response time. However, in many applications, the response time of exact answers is often longer than what is acceptable. Huge volume of data, slow network link, even temporary nonavailability of data, complex queries are examples of database characteristics where getting an exact answer can demand a long time. Approximate query processing has emerged as an alternative approach to give to the user an answer in a short time, although not an exact one. The goal is to provide an estimated result very close to the exact answer, along with a confidence interval, but in one order of magnitude less time than the time to compute the exact answer. There is a large set of techniques for approximate query processing available in different research areas. However, most of them are only suitable for traditional data. In spatial databases field, the data usually have high complexity and are available in huge amounts, leading to long response times even for simple queries. This work extends the proposals of Azevedo et al. (2004) and Azevedo et al. (2005) of using Four-Color Raster Signature (4CRS) (Zimbrao and Souza, 1998) for fast and approximate processing of queries on polygon datasets. We propose new algorithms for a set of spatial operations that can be processed approximately using 4CRS.