Performing boundary shape matching in spatial data

ABSTRACT

This paper describes a new approach to knowledge discovery among spatial objects-namely that of partial boundary shape matching. Our focus is on mining spatial data, whereby many objects called features (represented as polygons) are compared with one or more point sets called clusters. The research described has practical application in such domains as Geographic Information Systems, in which a cluster of points (possibly created by an SQL query) is compared to many natural or man-made features to detect partial or total matches of the facing boundaries of the cluster and feature. We begin by using an alpha-shape to characterize the shape of an arbitrary cluster of points, thus producing a set of edges denoting the cluster's boundary. We then provide an approach for detecting a boundary shape match between the facing curves of the cluster and feature, and show how to quantify the value of the match. Optimizations and experimental results are also provided. Finally, we describe several orientation strategies yielding signifficant performance enhancements.

REFERENCES

• 1: Rakesh Agrawal , Sakti P. Ghosh , Tomasz Imielinski , Balakrishna R. Iyer , Arun N. Swami, An Interval Classifier for Database Mining Applications, Proceedings of the 18th International Conference on Very Large Data Bases, p.560-573, August 23-27, 1992
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: {3} H. Edelsbrunner, D. Kirkpatrick, and R. Seidel. "On the Shape of a Set of Points in the Plane", IEEE Transactions on Information Theory, 29, 4, pp. 551-559, 1983.
• 4: Martin Ester , Hans-Peter Kriegel , Xiaowei Xu, Knowledge Discovery in Large Spatial Databases: Focusing Techniques for Efficient Class Identification, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.67-82, August 06-09, 1995
• 5: {5} W. J. Frawley, G. Piatetsky-Shapiro, and C. J. Matheus. "Knowledge Discovery in Databases: An Overview", Knowledge Discovery in Databases, Piatetsky-Shapiro and Frawley (eds.), AAAI/MIT Press, pp. 1-27, 1991.
• 6: Jiawei Han , Yandong Cai , Nick Cercone, Knowledge Discovery in Databases: An Attribute-Oriented Approach, Proceedings of the 18th International Conference on Very Large Data Bases, p.547-559, August 23-27, 1992
• 7: Daniel A. Keim , Hans-Peter Kriegel , Thomas Seidl, Supporting Data Mining of Large Databases by Visual Feedback Queries, Proceedings of the Tenth International Conference on Data Engineering, p.302-313, February 14-18, 1994
• 8: {8} D. Kirkpatrick and J. Radke. "A Framework for Computational Morphology", Computational Geometry, G.Toussaint (ed.), The Netherlands: Elsevier Science Publishers B.V., 1985, pp. 217-248, 1985.
• 9: Edwin M. Knorr , Raymond T. Ng, Finding Aggregate Proximity Relationships and Commonalities in Spatial Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.884-897, December 1996 [doi>10.1109/69.553156]
• 10: {10} W. Lu, J. Han, and B. C. Ooi. "Discovery of General Knowledge in Large Spatial Databases", Proceedings of the Far East Workshop on Geographic Information Systems, Singapore, pp. 275-289, 1993.
• 11: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 12: Joseph O'Rourke, Computational geometry in C, Cambridge University Press, New York, NY, 1994

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
          Subjects: Size and shape

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
GIS, pattern matching, spatial knowledge discovery