Melnik, Sergey and Garcia-Molina, Hector (2002) Divide-and-Conquer Algorithm for Computing Set Containment Joins. In: 8th International Conference on Extending Database Technology (EDBT 2002), March 25-27, 2002, Prague, Czech Republic.
| BibTeX | DublinCore | EndNote | HTML |
This is the latest version of this item.
![[img]](/style/images/fileicons/application_pdf.png)
| PDF 371Kb |
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.
| Item Type: | Conference or Workshop Item (Paper) | |
|---|---|---|
| Subjects: | Computer Science > Query Processing | |
| Projects: | Miscellaneous | |
| Related URLs: | Project Homepage | http://infolab.stanford.edu/ |
| ID Code: | 731 | |
| Deposited By: | Import Account | |
| Deposited On: | 14 Jan 2002 16:00 | |
| Last Modified: | 25 Dec 2008 09:47 |
Available Versions of this Item
- Divide-and-Conquer Algorithm for Computing Set Containment Joins (Extended Technical Report). (deposited 20 Sep 2001 17:00)
- Divide-and-Conquer Algorithm for Computing Set Containment Joins. (deposited 14 Jan 2002 16:00) [Currently Displayed]
Download statistics
Repository Staff Only: item control page
