Abstract This paper revisits set containment join (SCJ) problem, which uses the subset relationship (i.e., $$\subseteq$$ ⊆ ) as condition to join set-valued attributes of two relations and has many fundamental applications in commercial and scientific fields. Existing in-memory algorithms for SCJ are either signature-based or prefix-tree-based. The former incurs high CPU cost because of the enumeration of signatures, while the latter incurs high space cost because of the storage of prefix trees. This paper proposes a new adaptive parameter-free in-memory algorithm, named as frequency-hashjoin or $${\mathsf {FreshJoin}}$$ FreshJoin in short, to evaluate SCJ efficiently. $${\mathsf {FreshJoin}}$$ FreshJoin builds a flat index on-the-fly to record three kinds of signatures (i.e., two least frequent elements and a hash signature whose length is determined adaptively by the frequencies of elements in the universe set). The index consists of two sparse inverted indices and two arrays which record hash signatures of all sets in each relation. The index is well organized such that $${\mathsf {FreshJoin}}$$ FreshJoin can avoid enumerating hash signatures. The rationality of this design is explained. And, the time and space cost of the proposed algorithm, which provide a rule to choose $${\mathsf {FreshJoin}}$$ FreshJoin from existing algorithms, are analyzed. Experiments on 16 real-life datasets show that $${\mathsf {FreshJoin}}$$ FreshJoin usually reduces more than 50% of space cost while remains as competitive as the state-of-the-art algorithms in running time.

This paper describes a PC-cluster based parallel DBMS, InfiniteDB, developed by the authors. InfiniteDB aims at efficiently storing and processing of massive databases in response to the rapidly growing in database size and the need of high performance analyzing of massive databases. It supports the parallelisms of intra-query, inter-query, intra-operation, inter-operation and pipelining. It provides effective strategies for processing massive databases including the multiple data declustering methods, the declustering-aware algorithms for the execution of relational operations and other database operations, and the adaptive query optimization method. It also provides the functions of parallel data warehousing and data mining, the coordinator-wrapper mechanism to support the integration of heterogeneous information resources on the Internet, and the fault tolerant and resilient infrastructures. It has been used in many applications and has proved quite effective for storing and processing massive databases in practice.