An interactive framework for raster data spatial joins

ABSTRACT

Many Geographic Information Systems (GIS) handle large geospatial datasets stored in raster representation. Spatial joins over raster data are important queries in GIS for data analysis and decision support. However, evaluating spatial joins can be very time intensive due to the size of these datasets. In this paper we propose a new interactive framework that allows users to get approximate answers in near instantaneous time, thus allowing for truly interactive data exploration. Our method utilizes two proposed statistical approaches: probabilistic join and sampling based join. Our probabilistic join method provides speedup of two orders of magnitude with no correctness guarantee, while our sampling based method provides an order of magnitude improvement over the full quad-tree join and also provides running confidence intervals. We propose a framework that combines the two approaches to allow end users to tradeoff speed versus bounded accuracy. The two approaches are evaluated empirically with real and synthetic datasets.

REFERENCES

• 1: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 2: 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
• 3: 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
• 4: Leonardo Guerreiro Azevedo , Ralf Hartmut Güting , Rafael Brand Rodrigues , Geraldo Zimbrão , Jano Moreira de Souza, Filtering with raster signatures, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183471.1183503]
• 5: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 6: Reynold Cheng , Sarvjeet Singh , Sunil Prabhakar , Rahul Shah , Jeffrey Scott Vitter , Yuni Xia, Efficient join processing over uncertain data, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183719]
• 7: Peter J. Haas, Large-Sample and Deterministic Confidence Intervals for Online Aggregation, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.51-63, August 11-13, 1997 [doi>10.1109/SSDM.1997.621151]
• 8: F. Olken. Random Sampling from Databases. PhD thesis, University of California at Berkeley, 1993.
• 9: R. J. Serfling. Basic Statistics for Business and Economics. McGraw-Hill, 2002.
• 10: H. Tveite. Data Modeling and Database Requirements for Geographical Data. PhD thesis, University of Norway, 1997.
• 11: Michael Vassilakopoulos , Yannis Manolopoulos, On sampling regional data, Data & Knowledge Engineering, v.22 n.3, p.309-318, May 1997 [doi>10.1016/S0169-023X(96)00047-X]
• 12: W. D. Bae, S. Alkobaisi, and S. T. Leutenegger. An incremental refinining spatial join algorithm for estimating qeury results in GIS. In Proceedings of DEXA, pages 935--944, 2006.
• 13: W. D. Bae, S. Alkobaisi, and S. T. Leutenegger. IRSJ: Incremental refining spatial joins for interactive queries in GIS. In Technical Report DU-CS-07-10. University of Denver, 2007.
• 14: USGS. http://tin.er.usgs.gov/, 2001, 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Design, Performance

Keywords:
probabilistic join, raster spatial join, sampling, visualization