GESS: a scalable similarity-join algorithm for mining large data sets in high dimensional spaces

ABSTRACT

The similarity join is an important operation for mining high-dimensional feature spaces. Given two data sets, the similarity join computes all tuples (x, y) that are within a distance &egr;.One of the most efficient algorithms for processing similarity-joins is the Multidimensional-Spatial Join (MSJ) by Koudas and Sevcik. In our previous work --- pursued for the two-dimensional case --- we found however that MSJ has several performance shortcomings in terms of CPU and I/O cost as well as memory-requirements. Therefore, MSJ is not generally applicable to high-dimensional data.In this paper, we propose a new algorithm named Generic External Space Sweep (GESS). GESS introduces a modest rate of data replication to reduce the number of expensive distance computations. We present a new cost-model for replication, an I/O model, and an inexpensive method for duplicate removal. The principal component of our algorithm is a highly flexible replication engine.Our analytical model predicts a tremendous reduction of the number of expensive distance computations by several orders of magnitude in comparison to MSJ (factor 10⁷). In addition, the memory requirements of GESS are shown to be lower by several orders of magnitude. Furthermore, the I/O cost of our algorithm is by factor 2 better (independent from the fact whether replication occurs or not). Our analytical results are confirmed by a large series of simulations and experiments with synthetic and real high-dimensional data sets.

REFERENCES

• 1: Jonathan Ashley , Myron Flickner , James Hafner , Denis Lee , Wayne Niblack , Dragutin Petkovic, The query by image content (QBIC) system, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.475, May 22-25, 1995, San Jose, California, United States
• 2: Alberto Belussi , Christos Faloutsos, Self-spacial join selectivity estimation using fractal concepts, ACM Transactions on Information Systems (TOIS), v.16 n.2, p.161-201, April 1998 [doi>10.1145/279339.279342]
• 3: Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263671]
• 4: Jochen Van den Bercken , Björn Blohsfeld , Jens-Peter Dittrich , Jürgen Krämer , Tobias Schäfer , Martin Schneider , Bernhard Seeger, XXL - A Library Approach to Supporting Efficient Implementations of Advanced Database Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.39-48, September 11-14, 2001
• 5: Jochen van den Bercken , Jens-Peter Dittrich , Bernhard Seeger, javax.XXL: a prototype for a library of query processing algorithms, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.588, May 15-18, 2000, Dallas, Texas, United States
• 6: Jochen Van den Bercken , Martin Schneider , Bernhard Seeger, Plug&Join: An easy-to-use Generic Algorithm for Efficiently Processing Equi and Non-Equi Joins, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.495-509, March 27-31, 2000
• 7: Christian Böhm , Bernhard Braunmüller , Markus Breunig , Hans-Peter Kriegel, High performance clustering based on the similarity join, Proceedings of the ninth international conference on Information and knowledge management, p.298-305, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354832]
• 8: Christian Böhm , Hans-Peter Kriegel, A Cost Model and Index Architecture for the Similarity Join, Proceedings of the 17th International Conference on Data Engineering, p.411-420, April 02-06, 2001
• 9: William W. Cohen, Data integration using similarity joins and a word-based information representation language, ACM Transactions on Information Systems (TOIS), v.18 n.3, p.288-321, July 2000 [doi>10.1145/352595.352598]
• 10: http://tilde-hoschek.home.cern.ch/~hoschek- /colt/index.htm.
• 11: Data Redundancy and Duplicate Detection in Spatial Join Processing, Proceedings of the 16th International Conference on Data Engineering, p.535, February 28-March 03, 2000
• 12: Christos Faloutsos , Bernhard Seeger , Agma Traina , Caetano Traina, Jr., Spatial join selectivity using power laws, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.177-188, May 15-18, 2000, Dallas, Texas, United States
• 13: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 14: Nick Koudas , Kenneth C. Sevcik, Size separation spatial join, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.324-335, May 11-15, 1997, Tucson, Arizona, United States
• 15: Nick Koudas , Kenneth C. Sevcik, High Dimensional Similarity Joins: Algorithms and Performance Evaluation, Proceedings of the Fourteenth International Conference on Data Engineering, p.466-475, February 23-27, 1998
• 16: Nick Koudas , Kenneth C. Sevcik, High Dimensional Similarity Joins: Algorithms and Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.12 n.1, p.3-18, January 2000 [doi>10.1109/69.842246]
• 17: Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.247-258, June 04-06, 1996, Montreal, Quebec, Canada
• 18: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• 19: Jack A. Orenstein, An Algorithm for Computing the Overlay of k-Dimensional Spaces, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.381-400, August 28-30, 1991
• 20: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
• 21: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 22: D. Scott. Multivariate Density Estimation. Wiley-Interscience, 1992.
• 23: Kyuseok Shim , Ramakrishnan Srikant , Rakesh Agrawal, High-Dimensional Similarity Joins, Proceedings of the Thirteenth International Conference on Data Engineering, p.301-311, April 07-11, 1997
• 24: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

General Terms:
Algorithms, Design, Theory