Filtering with raster signatures

ABSTRACT

Efficient evaluation of spatial queries is an important issue in spatial database. Among spatial operations, spatial join is very useful, intersection being the most common predicate. However, the exact intersection test of two spatial objects is the most time-consuming and I/O-consuming step in processing spatial joins. On the other hand, the use of approximations can reduce the need for examining the exact geometry of spatial objects in order to find the intersecting ones. This work proposes a new raster approximation (Three-Color Raster Signature - 3CRS) for representing different data types (polygons, polylines and points), and to be used as filter in the second step of the Multi-Step Query Processor. We have also executed experimental tests over real datasets, the results having demonstrated the effectiveness of our approach.

REFERENCES

• 1: Aronoff, S. Geographic Information Systems, 1 ed., WDL Publications, Ottawa, Canada, 1989.
• 2: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 3: Jean-Daniel Boissonnat , Franco P. Preparata, Robust Plane Sweep for Intersecting Segments, SIAM Journal on Computing, v.29 n.5, p.1401-1421, March 2000 [doi>10.1137/S0097539797329373]
• 4: Brazilian Institute of Geography and Statistics Fundação Instituto Brasileiro de Geografia e Estatística -- IBGE: "Malha Municipal Digital do Brasil - 1994", Rio de Janeiro, 1996.
• 5: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider, Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems, Proceedings of the Ninth International Conference on Data Engineering, p.40-49, April 19-23, 1993
• 6: Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, Multi-step processing of spatial joins, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.197-208, May 24-27, 1994, Minneapolis, Minnesota, United States
• 7: Freiseisen W., and Pau, P. A generic plane-sweep for intersecting line segments, Technical Report RISC-Linz TR-98-18, University of Linz, Linz, Austria, 1998.
• 8: Gordon, S. R.,Goodwin, C.W.H., and Xiong, D. Final Report on Status of Spatial/Map Databases. Technical Report of Oak Ridge National Laboratory, June, 1994.
• 9: Ralf Hartmut Guting , Victor Almeida , Dirk Ansorge , Thomas Behr , Zhiming Ding , Thomas Hose , Frank Hoffmann , Markus Spiekermann , Ulrich Telle, SECONDO: An Extensible DBMS Platform for Research Prototyping and Teaching, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.1115-1116, April 05-08, 2005 [doi>10.1109/ICDE.2005.129]
• 10: Kothuri Venkata Ravi Kanth , Siva Ravada, Efficient Processing of Large Spatial Queries Using Interior Approximations, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.404-424, July 12-15, 2001
• 11: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 12: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• 13: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 14: Tao, Y., Sun, J., and Papadias, D. Selectivity estimation for predictive spatio-temporal queries. In Proceedings of the 19th International Conference on Data Engineering (ICDE'03) (Bangalore, India, March 5-8, 2003) IEEE Computer Society, 2003, 417--428.
• 15: Geraldo Zimbrao , Jano Moreira de Souza, A Raster Approximation For Processing of Spatial Joins, Proceedings of the 24rd International Conference on Very Large Data Bases, p.558-569, August 24-27, 1998
• 16: Hongjun Zhu , Jianwen Su , Oscar H. Ibarra, Toward Spatial Joins for Polygons, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.231, July 26-28, 2000 [doi>10.1109/SSDM.2000.869791]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Object representation

General Terms:
Algorithms, Experimentation, Management, Performance

Keywords:
GIS, four-colors raster signature, multi-step query processor, raster approximation, spatial databases, spatial join, three-colors raster signature