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. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1145/762471.762474 | ACM Trans. Database Syst. |
Keywords | Field | DocType |
detailed analysis,data set,Adaptive Divide-and-Conquer Join,database application,set containment,Adaptive Pick-and-Sweep Join,adaptive algorithm,synthetic data,set-valued attribute | Joins,Computer science,Operator (computer programming),Database,Containment | Journal |
Volume | Issue | ISSN |
28 | 1 | 0362-5915 |
Citations | PageRank | References |
38 | 1.95 | 11 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sergey Melnik | 1 | 879 | 62.73 |
Héctor García-Molina | 2 | 24359 | 5652.13 |