Adaptive algorithms for set containment joins

ABSTRACT

A set containment join is a join between set-valued attributes of two relations, whose join condition is specified using the subset (⊆) operator. Set containment joins are deployed in many database applications, even those that do not support set-valued attributes. In this article, we propose two novel partitioning algorithms, called the Adaptive Pick-and-Sweep Join (APSJ) and the Adaptive Divide-and-Conquer Join (ADCJ), which allow computing set containment joins efficiently. We show that APSJ outperforms previously suggested algorithms for many data sets, often by an order of magnitude. We present a detailed analysis of the algorithms and study their performance on real and synthetic data using an implemented testbed.

REFERENCES

• 1: Christian Böhm , Hans-Peter Kriegel, Dynamically Optimizing High-Dimensional Index Structures, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.36-50, March 27-31, 2000
• 2: Jin-Yi Cai , Venkatesan T. Chakaravarthy , Raghav Kaushik , Jeffrey F. Naughton, On the complexity of join predicates, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.207-214, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375592]
• 3: Chris Faloutsos , Stavros Christodoulakis, Signature files: an access method for documents and its analytical performance evaluation, ACM Transactions on Information Systems (TOIS), v.2 n.4, p.267-288, Oct. 1984 [doi>10.1145/2275.357411]
• 4: Jim Gray , Prakash Sundaresan , Susanne Englert , Ken Baclawski , Peter J. Weinberger, Quickly generating billion-record synthetic databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.243-252, May 24-27, 1994, Minneapolis, Minnesota, United States
• 5: Joseph M. Hellerstein , Elias Koutsoupias , Christos H. Papadimitriou, On the analysis of indexing schemes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.249-256, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263688]
• 6: Sven Helmer , Guido Moerkotte, Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates, Proceedings of the 23rd International Conference on Very Large Data Bases, p.386-395, August 25-29, 1997
• 7: Jun Hirai , Sriram Raghavan , Hector Garcia-Molina , Andreas Paepcke, WebBase: a repository of Web pages, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.277-293, June 2000, Amsterdam, The Netherlands
• 8: Yoshiharu Ishikawa , Hiroyuki Kitagawa , Nobuo Ohbo, Evaluation of signature files as set access facilities in OODBs, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.247-256, May 25-28, 1993, Washington, D.C., United States
• 9: Sergey Melnik , Hector Garcia-Molina, Divide-and-Conquer Algorithm for Computing Set Containment Joins, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.427-444, March 25-27, 2002
• 10: 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
• 11: Karthikeyan Ramasamy , Jignesh M. Patel , Jeffrey F. Naughton , Raghav Kaushik, Set Containment Joins: The Good, The Bad and The Ugly, Proceedings of the 26th International Conference on Very Large Data Bases, p.351-362, September 10-14, 2000

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance