Should SDBMS support a join index?: a case study from CrimeStat

ABSTRACT

Given a spatial crime data warehouse, that is updated infrequently and a set of operations O as well as constraints of storage and update overheads, the index type selection problem is to find a set of index types that can reduce the I/O cost of the set of operations. The index type selection problem is important to improve user experience and system resource utilization in crucial spatial statistics application domains such as mapping and analysis for public safety, public health, ecology, and transportation. This is because the response time of frequent queries based on the set of operations can be improved significantly by an effective choice of index types. Many spatial statistical queries in these application domains make use of a spatial neighborhood matrix, known as W in spatial statistics, which can be thought of as a spatial self-join in spatial database terminology. Currently supported index types such as B-Tree and R-Tree families do not adequately support spatial statistical analysis because they require on-the-fly computation of the WMatrix, slowing down spatial statistical analysis. In contrast, this paper argues that Spatial Database Management Systems (SDBMS) should support a join index to materialize the WMatrix and eliminate on-the-fly computation of the common selfjoin. A detailed case study using the popular spatial statistical software package for public safety, namely CrimeStat, shows that join indices can significantly speed up spatial analysis such as calculation of Ripley's K and identification of hotspots.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, ACM SIGMOD Record, v.19 n.2, p.322-331, Jun. 1990
• 2: N. A. Cressie, editor. Statistics for Spatial Data. Wiley- Interscience, 1993.
• 3: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 4: 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
• 5: Edwin H. Jacox , Hanan Samet, Spatial join techniques, ACM Transactions on Database Systems (TODS), v.32 n.1, p.7-es, March 2007 [doi>10.1145/1206049.1206056]
• 6: N. Levine, CrimeStat: A spatial statistics program for the analysis of Crime incident locations, version 3.1. Ned Levine and Associates: Houston, TX/National Institute of Justice: Washington, DC, 2004. URL: www.icpsr.umich.edu/CrimeStat
• 7: G. Malcom. Microsoft SQL Server 2008, Delivering Location Intelligence with Spatial Data. SQL Server Technical Article. Microsoft Corporation, Aug 2007. Available online at http://download.microsoft.com/download/a/c/d/acd8e043- d69b-4f09-bc9e-4168b65aaa71/SpatialData.doc
• 8: A. Mitchell, editor. The ESRI Guide to GIS Analysis, Volume 1: Geographic Patterns and Relationships. ESRI Press, 2005.
• 9: A. Mitchell, editor. The ESRI Guide to GIS Analysis, Volume 2:Statistical Measurements and Statistics. ESRI Press, 2005.
• 10: Doron Rotem, Spatial Join Indices, Proceedings of the Seventh International Conference on Data Engineering, p.500-509, April 08-12, 1991
• 11: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• 12: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 13: S. Shekhar and S. Chawla, editors. Spatial Databases: A Tour. Prentice Hall, 2002.
• 14: B. D. Ripley. The second-order analysis of stationary point processes. Journal of Applied Probability 13: 255--66. 1976.
• 15: Shashi Shekhar , Chang-Tien Lu , Sanjay Chawla , Sivakumar Ravada, Efficient Join-Index-Based Spatial-Join Processing: A Clustering Approach, IEEE Transactions on Knowledge and Data Engineering, v.14 n.6, p.1400-1421, November 2002 [doi>10.1109/TKDE.2002.1047776]
• 16: Oracle Spatial 11g: Advanced Spatial Data Management for the Enterprise. Oracle Data Sheet. Feb 2005. Available online at http://www.oracle.com/technology/products/spatial/pdf/11g_ collateral/spatial11g_datasheet.pdf
• 17: Shashi Shekhar , Duen-Ren Liu, CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations, IEEE Transactions on Knowledge and Data Engineering, v.9 n.1, p.102-119, January 1997 [doi>10.1109/69.567054]
• 18: Michael Worboys , Matt Duckham, GIS: A Computing Perspective, 2nd Edition, CRC Press, Inc., Boca Raton, FL, 2004
• 19: IBM Informix Spatial DataBlade Module: User's Guide. IBM Corporation, Ver 8.20, Part No. 000-9119, Aug: 2002. Available online at http://publib.boulder.ibm.com/epubs/pdf/9119.pdf

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design

General Terms:
Design, Experimentation

Keywords:
W matrix, join index, self-join, spatial statistics