Mining frequent neighboring class sets in spatial databases

ABSTRACT

We consider the problem of finding neighboring class sets. Objects of each instance of a neighboring class set are grouped using their Euclidean distances from each other. Recently, location-based services are growing along with mobile computing infrastructure such as cellular phones and PDAs. Therefore, we expect to see the development of spatial databases that contains very large number of access records including location information. The most typical type would be a database of point objects. Records of the objects may consist of "requested service name," "number of packet transmitted" in addition to x and y coordinate values indicating where the request came from. The algorithm presented here efficiently finds sets of "service names" that were frequently close to each other in the spatial database. For example, it may find a frequent neighboring class set, where "ticket" and "timetable" are frequently requested close to each other. By recognizing this, location-based service providers can promote a "ticket" service for customers who access the "timetable."

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 3: Martin Ester , Hans-Peter Kriegel , Jörg Sander , Michael Wimmer , Xiaowei Xu, Incremental Clustering for Mining in a Data Warehousing Environment, Proceedings of the 24rd International Conference on Very Large Data Bases, p.323-333, August 24-27, 1998
• 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: Ralf Hartmut Güting, An introduction to spatial database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 6: Jaiwei Han , Krzysztof Koperski , Nebojsa Stefanovic, GeoMiner: a system prototype for spatial data mining, ACM SIGMOD Record, v.26 n.2, p.553-556, June 1997
• 7: 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]
• 8: Krzysztof Koperski , Jiawei Han, Discovery of Spatial Association Rules in Geographic Information Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.47-66, August 06-09, 1995
• 9: 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
• 10: Takao Ohya , Masao Iri , Kazuo Murota, A fast voronoi-diagram algorithm with quaternary tree bucketing, Information Processing Letters, v.18 n.4, p.227-231, May 1984 [doi>10.1016/0020-0190(84)90116-9]
• 11: T. Ohya, M. Iri, and K. Murota. Improvements of the incremental method for the voronoi diagram with computational comparison of various algorithms. Journal of the Operations Research Society of Japan, 27(4):306-337, 1984.
• 12: Wei Wang , Jiong Yang , Richard R. Muntz, STING: A Statistical Information Grid Approach to Spatial Data Mining, Proceedings of the 23rd International Conference on Very Large Data Bases, p.186-195, August 25-29, 1997

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

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

General Terms:
Algorithms, Design, Performance