  Given two collections of set objects $R$ and $S$, the $R \bowtie_{\subseteq}
S$ set containment join returns all object pairs $(r, s) \in R \times S$ such
that $r \subseteq s$. Besides being a basic operator in all modern data
management systems with a wide range of applications, the join can be used to
evaluate complex SQL queries based on relational division and as a module of
data mining algorithms. The state-of-the-art algorithm for set containment
joins (PRETTI) builds an inverted index on the right-hand collection $S$ and a
prefix tree on the left-hand collection $R$ that groups set objects with common
prefixes and thus, avoids redundant processing. In this paper, we present a
framework which improves PRETTI in two directions. First, we limit the prefix
tree construction by proposing an adaptive methodology based on a cost model;
this way, we can greatly reduce the space and time cost of the join. Second, we
partition the objects of each collection based on their first contained item,
assuming that the set objects are internally sorted. We show that we can
process the partitions and evaluate the join while building the prefix tree and
the inverted index progressively. This allows us to significantly reduce not
only the join cost, but also the maximum memory requirements during the join.
An experimental evaluation using both real and synthetic datasets shows that
our framework outperforms PRETTI by a wide margin.
