Metric space similarity joins

ABSTRACT

Similarity join algorithms find pairs of objects that lie within a certain distance ε of each other. Algorithms that are adapted from spatial join techniques are designed primarily for data in a vector space and often employ some form of a multidimensional index. For these algorithms, when the data lies in a metric space, the usual solution is to embed the data in vector space and then make use of a multidimensional index. Such an approach has a number of drawbacks when the data is high dimensional as we must eventually find the most discriminating dimensions, which is not trivial. In addition, although the maximum distance between objects increases with dimension, the ability to discriminate between objects in each dimension does not. These drawbacks are overcome via the introduction of a new method called Quickjoin that does not require a multidimensional index and instead adapts techniques used in distance-based indexing for use in a method that is conceptually similar to the Quicksort algorithm. A formal analysis is provided of the Quickjoin method. Experiments show that the Quickjoin method significantly outperforms two existing techniques.

REFERENCES

• 1: Charu C. Aggarwal, Towards systematic design of distance functions for data mining applications, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956756]
• 2: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 3: Rakesh Agrawal , Giuseppe Psaila , Edward L. Wimmers , Mohamed Zaït, Querying Shapes of Histories, Proceedings of the 21th International Conference on Very Large Data Bases, p.502-514, September 11-15, 1995
• 4: Walid G. Aref , Hanan Samet, Hashing by proximity to process duplicates in spatial databases, Proceedings of the third international conference on Information and knowledge management, p.347-354, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191307]
• 5: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Scalable Sweeping-Based Spatial Join, Proceedings of the 24rd International Conference on Very Large Data Bases, p.570-581, August 24-27, 1998
• 6: 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]
• 7: Christian Böhm , Bernhard Braunmüller , Florian Krebs , Hans-Peter Kriegel, Epsilon grid order: an algorithm for the similarity join on massive high-dimensional data, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.379-388, May 21-24, 2001, Santa Barbara, California, United States
• 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: Sergey Brin, Near Neighbor Search in Large Metric Spaces, Proceedings of the 21th International Conference on Very Large Data Bases, p.574-584, September 11-15, 1995
• 10: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 11: Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001 [doi>10.1145/502807.502808]
• 12: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 13: 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
• 14: Jens-Peter Dittrich , Bernhard Seeger, GESS: a scalable similarity-join algorithm for mining large data sets in high dimensional spaces, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.47-56, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502524]
• 15: Vlastislav Dohnal , Claudio Gennaro , Pasquale Savino , Pavel Zezula, D-Index: Distance Searching Index for Metric Data Sets, Multimedia Tools and Applications, v.21 n.1, p.9-33, September 2003 [doi>10.1023/A:1025026030880]
• 16: Dohnal, V., Gennaro, C., Savino, P., and Zezula, P. 2003a. Similarity join in metric spaces. In Proceedings of the 25th European Conference on IR Research (Advances in Information Retrieval) (ECIR'03). Pisa, Italy, 452--467.
• 17: Dohnal, V., Gennaro, C., and Zezula, P. 2003b. Similarity join in metric spaces using eD-Index. In Proceedings of the 14th International Conference on Database and Expert Systems Applications. (DEXA'03). Prague, Czech Republic, 484--493.
• 18: Ramez A. Elmasri , Shamkant B. Navathe, Fundamentals of Database Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 19: Jost Enderle , Matthias Hampel , Thomas Seidl, Joining interval data in relational databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007645]
• 20: C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
• 21: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 22: 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
• 23: Lilian Harada , Miyuki Nakano , Masaru Kitsuregawa , Mikio Takagi, Query Processing for Multi-Attribute Clustered Records, Proceedings of the 16th International Conference on Very Large Data Bases, p.59-70, August 13-16, 1990
• 24: Hettich, S. and Bay, S. D. 1999. The UCI KDD archive. Department of Information and Computer Science. University of California, Irvine, CA. [http://kdd.ics.uci.edu].
• 25: Gisli R. Hjaltason , Hanan Samet, Index-driven similarity search in metric spaces (Survey Article), ACM Transactions on Database Systems (TODS), v.28 n.4, p.517-580, December 2003 [doi>10.1145/958942.958948]
• 26: Hoare, C. A. R. 1962. Quicksort. Comput. J. 5, 1, 10--15.
• 27: Hristescu, G. and Farach-Colton, M. 1999. Cluster-preserving embedding of proteins. Tech. rep., Department of Computer Science, Rutgers University, Piscataway, NJ.
• 28: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Integrated Query Processing Strategies for Spatial Path Queries, Proceedings of the Thirteenth International Conference on Data Engineering, p.477-486, April 07-11, 1997
• 29: Daniel P. Huttenlocher , Klara Kedem , Jon M. Kleinberg, On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane, Proceedings of the eighth annual symposium on Computational geometry, p.110-119, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142700]
• 30: Edwin H. Jacox , Hanan Samet, Iterative spatial join, ACM Transactions on Database Systems (TODS), v.28 n.3, p.230-256, September 2003 [doi>10.1145/937598.937600]
• 31: 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]
• 32: H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States
• 33: Joseph JaJa, A Perspective on Quicksort, Computing in Science and Engineering, v.2 n.1, p.43-49, January 2000 [doi>10.1109/5992.814657]
• 34: Kahveci, T., Lang, C., and Singh, A. K. 2003. Joining massive high-dimensional datasets. In Proceedings of the 19th IEEE International Conference on Data Engineering. Bangalore, India, 264--276.
• 35: Dmitri V. Kalashnikov , Sunil Prabhakar, Similarity Join for Low-and High-Dimensional Data, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications, p.7, March 26-28, 2003
• 36: Gershon Kedem, The quad-CIF tree: A data structure for hierarchical on-line algorithms, Proceedings of the 19th conference on Design automation, p.352-357, January 1982
• 37: Masaru Kitsuregawa , Lilian Harada , Mikio Takagi, Join Strategies on KB-Tree Indexed Relations, Proceedings of the Fifth International Conference on Data Engineering, p.85-93, February 06-10, 1989
• 38: 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
• 39: Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
• 40: 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
• 41: 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
• 42: 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]
• 43: Levenshtein, V. A. 1966. Binary codes capable of correcting deletions, insertion, and reversals. Cybern. Control Theory 10, 8, 707--710.
• 44: Linial, N., London, E., and Rabinovich, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15, 215--245.
• 45: Ming-Ling Lo , Chinya V. Ravishankar, Generating Seeded Trees from Data Sets, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.328-347, August 06-09, 1995
• 46: T. H. Merrett , Yahiko Kambayashi , H. Yasuura, Scheduling of page-fetches in join operations, Proceedings of the seventh international conference on Very Large Data Bases, p.488-498, September 09-11, 1981, Cannes, France
• 47: Gabriele Neyer , Peter Widmayer, Singularities Make Spatial Join Scheduling Hard, Proceedings of the 8th International Symposium on Algorithms and Computation, p.293-302, December 17-19, 1997
• 48: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 49: 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
• 50: Jack A. Orenstein, Strategies for Optimizing the Use of Redundancy in Spatial Databases, Proceedings of the First Symposium on Design and Implementation of Large Spatial Databases, p.115-134, July 17-18, 1989
• 51: Dimitris Papadias , Dinos Arkoumanis, Approximate Processing of Multiway Spatial Joins in Very Large Databases, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.179-196, March 25-27, 2002
• 52: 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
• 53: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 54: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 55: W. J. Rucklidge, Locating objects using the Hausdorff distance, Proceedings of the Fifth International Conference on Computer Vision, p.457, June 20-23, 1995
• 56: William Rucklidge, Efficient Visual Recognition Using the Hausdorff Distance, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 57: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 58: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 59: Hanan Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 60: 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
• 61: K. Shim , R. Srikant , R. Agrawal, High-Dimensional Similarity Joins, IEEE Transactions on Knowledge and Data Engineering, v.14 n.1, p.156-171, January 2002 [doi>10.1109/69.979979]
• 62: Improvements in Distance-Based Indexing, Proceedings of the 16th International Conference on Scientific and Statistical Database Management, p.161, June 21-23, 2004 [doi>10.1109/SSDBM.2004.42]
• 63: Uhlmann, J. K. 1991. Satisfying general proximity/similarity queries with metric trees. Inform. Process. Lett. 40, 4, 175--179.
• 64: Voronoi, G. 1909. Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxiême mémoire: Recherches sur les parallèlloèdres primitifs. Seconde partie. Journal für die Reine und Angewandte Mathematik 136, 2, 67--181.
• 65: Jason Tsong-Li Wang , Xiong Wang , King-Ip Lin , Dennis Shasha , Bruce A. Shapiro , Kaizhong Zhang, Evaluating a class of distance-mapping algorithms for data mining and clustering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.307-311, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312264]
• 66: Chenyi Xia , Hongjun Lu , Beng Chin Ooi , Jing Hu, Gorder: an efficient method for KNN join processing, Proceedings of the Thirtieth international conference on Very large data bases, p.756-767, August 31-September 03, 2004, Toronto, Canada
• 67: Peter N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.311-321, January 25-27, 1993, Austin, Texas, United States
• 68: Pavel Zezula , Giuseppe Amato , Vlastislav Dohnal , Michal Batko, Similarity Search: The Metric Space Approach (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 69: All-Nearest-Neighbors Queries in Spatial Databases, Proceedings of the 16th International Conference on Scientific and Statistical Database Management, p.297, June 21-23, 2004 [doi>10.1109/SSDBM.2004.12]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Multimedia databases
      H.2.8 Database applications
          Subjects: Image databases

General Terms:
Algorithms, Performance

Keywords:
Similarity join, distance-based indexing, external memory algorithms, nearest neighbor queries, range queries, ranking