Stanford InfoLab Publication Server

Adaptive Algorithms for Set Containment Joins (Technical Report)

Melnik, Sergey and Garcia-Molina, Hector (2001) Adaptive Algorithms for Set Containment Joins (Technical Report). Technical Report. Stanford.




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, called the Adaptive Pick-and-Sweep Join and the Adaptive Divide-and-Conquer Join, for computing set containment joins efficiently. We show that our algorithms outperform 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)
Uncontrolled Keywords:Set containment join, Database performance
Subjects:Computer Science > Query Processing
Related URLs:Project Homepage
ID Code:517
Deposited By:Import Account
Deposited On:07 Nov 2001 16:00
Last Modified:27 Dec 2008 10:32

Download statistics

Repository Staff Only: item control page