Hardware acceleration for spatial selections and joins

ABSTRACT

Spatial database operations are typically performed in two steps. In the filtering step, indexes and the minimum bounding rectangles (MBRs) of the objects are used to quickly determine a set of candidate objects, and in the refinement step, the actual geometries of the objects are retrieved and compared to the query geometry or each other. Because of the complexity of the computational geometry algorithms involved, the CPU cost of the refinement step is usually the dominant cost of the operation for complex geometries such as polygons. In this paper, we propose a novel approach to address this problem using efficient rendering and searching capabilities of modern graphics hardware. This approach does not require expensive pre-processing of the data or changes to existing storage and index structures, and it applies to both intersection and distance predicates. Our experiments with real world datasets show that by combining hardware and software methods, the overall computational cost can be reduced substantially for both spatial selections and joins.

REFERENCES

• 1: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 2: 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
• 3: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 4: Edward P. F. Chan, Evaluation of Buffer Queries in Spatial Databases, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.197-216, July 12-15, 2001
• 5: 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
• 6: 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
• 7: Wael M. Badawy , Walid G. Aref, On local heuristics to speed up polygon-polygon intersection tests, Proceedings of the 7th ACM international symposium on Advances in geographic information systems, p.97-102, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/320134.320160]
• 8: Ravi K. Kothuri. Personal commnunications, 2002.
• 9: Ravi Kanth V Kothuri , Siva Ravada , Daniel Abugov, Quadtree and R-tree indexes in oracle spatial: a comparison using GIS data, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564755]
• 10: Jarek Rossignac , Abe Megahed , Bengt-Olaf Schneider, Interactive inspection of solids: cross-sections and interferences, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.353-360, July 1992
• 11: George Baciu, Wingo Sai-Keung Wong, and Hanqiu Sun. Recode: An image-based collision detection algorithm. The Journal of Visualization and Computer Animation, 10(4):181--192, 1999.
• 12: Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
• 13: Kenneth E. Hoff, III , Andrew Zaferakis , Ming Lin , Dinesh Manocha, Fast and simple 2D geometric proximity queries using graphics hardware, Proceedings of the 2001 symposium on Interactive 3D graphics, p.145-148, March 2001 [doi>10.1145/364338.364383]
• 14: Mark Segal and Kurt Akeley. The OpenGL Graphics System: A Specification (Version 1.2.1). Silicon Graphics, Inc., April 1999.
• 15: Joseph O'Rourke, Computational geometry in C (2nd ed.), Cambridge University Press, New York, NY, 1998
• 16: Wyoming Gap Analysis. Land Cover for Wyoming. University of Wyoming, Spatial Data and Visualization Center, December 1996.
• 17: Wyoming Gap Analysis. Land Ownership and Management for Wyoming. University of Wyoming, Spatial Data and Visualization Center, December 1996.
• 18: U.S. Geological Survey. State Boundaries of the United States. U.S. Geological Survey, November 1999.
• 19: Chris Daly and George Taylor. United States Average Annual Precipitation, 1961--1990. Spatial Climate Analysis Service, Oregon State University; USDA - NRCS National Water and Climate Center, Portland, Oregon; USDA - NRCS National Cartography and Geospatial Center, Fort Worth, September 2000.
• 20: John Watermolen. 1:2,000,000-Scale Hydrologic Unit Boundaries. U.S. Geological Survey, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
      H.2.8 Database applications
          Subjects: Spatial databases and GIS
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Design, Experimentation, Performance

Keywords:
hardware acceleration, spatial join, spatial selection