# Problem of finding pairs of elements that co-occur in some number of sets

I have a fairly general problem and I wonder if it has a name. The problem statement, as best I can put it, is the following:

Let $I=\{i_1,i_2,...,i_n\}$ be a set of items. Let $C=\{C_1,C_2,...,C_m\}$ be a set of containers. Each container is unique and contains a set of items from $I$. Let $C_{a,b} \subseteq C$ be the set of containers that contain both $i_a$ and $i_b$. Find all $(i_a, i_b)$ pairs where $\left\vert{C_{a,b}}\right\vert \geq k$ for a given $k \in \mathbb{N}$.

If the items are people and the containers are times and places, then we are asking which people met at least $k$ times. If the items are groceries and the containers are shopping carts, then the problem is a variation of association rule learning. If the items are words and the containers are documents, then we are looking for a co-occurrence network.

I don't know if it has a special name. It looks like one algorithmic approach to solve it is by using matrix multiplication: let $M_{i,j}=1$ if item $i$ is in container $j$, otherwise $M_{i,j}=0$; then compute $N = M \cdot M^t$ and search for all cells of $N$ such that $N_{a,b}\ge k$. In addition to the problems you mention, it's also similar to Computing the "at least k friends in common" graph.
• Thanks! For large $n$ it's not feasible to enumerate all pairs. Anyway I'm just looking for the name. The question you link is indeed related. Too bad it has no answer. – Daniel Darabos Jul 8 '15 at 8:41