Stanford InfoLab Publication Server

Divide-and-Conquer Algorithm for Computing Set Containment Joins (Extended Technical Report)

Melnik, Sergey and Garcia-Molina, Hector (2001) Divide-and-Conquer Algorithm for Computing Set Containment Joins (Extended Technical Report). Technical Report. Stanford.

WarningThere is a more recent version of this item available.



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:Techreport (Technical Report)
Subjects:Computer Science > Query Processing
Related URLs:Project Homepage
ID Code:502
Deposited By:Import Account
Deposited On:20 Sep 2001 17:00
Last Modified:27 Dec 2008 10:33

Available Versions of this Item

Download statistics

Repository Staff Only: item control page