[ Pagewise preview ]
| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/2002-2 | ||
| Previous version | 2001-32 | ||
| Submitted on | 15th of January 2002 | ||
| Author | Melnik, Sergey; Garcia-Molina, Hector | ||
| Title | Divide-and-Conquer Algorithm for Computing Set Containment Joins | ||
| Date of publication | March 2002 | ||
| Published in | Proc. 8th Int. Conf. on Extending Database Technology (EDBT) | ||
| Citation | Melnik, Sergey; Garcia-Molina, Hector. Divide-and-Conquer Algorithm for Computing Set Containment Joins, Proc. 8th Int. Conf. on Extending Database Technology (EDBT), 2002 | ||
| Number of pages | 18 | ||
| Language | English | ||
| Project | Database Group | ||
| Type | Conference or Journal Paper | ||
| Subject group | Query processing | ||
| 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 used in a variety of database applications. In this paper, we propose two partitioning algorithms for computing set containment joins efficiently. The first algorithm called Lattice Set Join is a partitioning-based version of an existing main-memory algorithm. The second one is a novel algorithm that we call Divide-and-Conquer Set Join. We show that the divide-and-conquer approach outperforms previously suggested algorithms over a wide range of data sets. We present a detailed analysis of the algorithms and describe their behavior in an implemented testbed. | ||
| Fulltext source |
| Management of the document by | siroker@db.stanford.edu
| |
[ Pagewise preview ]