Algorithm to find intersection between collection of sets

Question

I have two dataframes representing products two distributors sell. They look like this:

df1 for distributor 1.

Country, Age group, Product
{USA, Canada}, {Toddlers, Teens}, {Jeans, Shoes}
{USA, Mexico}, {Teens, Adults}, {Hair bands, Mufflers}

So, the distributor 1 sells jeans and shoes for toddlers and teens in USA and Canada. They also sell hair bands and mufflers for teens and adults in USA and Mexico.

df2 for distributor 2.

Country, Age group, Product
{Russia, Canada}, {Toddlers, Babys}, {Shoes, Hats}
{Russia, USA}, {Adults, Elderly}, {Mufflers, Hats}

I want to find out if any particular value of Country, Age group and Product matches both df2 and df1. That is, I want of find out if there are conflicts where both distributor is trying to sell the same product to the same age group in the same country.

A straightforward approach would be to explode both the dataframes to look like this:

df1:

Country Age group   Product
Canada  Teens   Jeans
Canada  Teens   Shoes
Canada  Toddlers    Jeans
Canada  Toddlers    Shoe
...

df2:

Country Age group   Product
Canada  Babys   Hats
Canada  Babys   Shoes
Canada  Toddlers    Hats
Canada  Toddlers    Shoes
Russia  Adults  Hats
...

Then, convert them to to set of tuples, df1:

{('Canada', 'Teens', 'Jeans'),
 ('Canada', 'Teens', 'Shoes'),
 ('Canada', 'Toddlers', 'Jeans'),
 ...}

df2:

{('Canada', 'Babys', 'Hats'),
 ('Canada', 'Babys', 'Shoes'),
 ('Canada', 'Toddlers', 'Hats'),
 ('Canada', 'Toddlers', 'Shoes'),
 ('Russia', 'Adults', 'Hats'),
 ...}

Then find their intersection:

>>df1s.intersection(df2s)
{('Canada', 'Toddlers', 'Shoes'), ('USA', 'Adults', 'Mufflers')}

The problem I have with this approach is due to the number of columns and possible values in the set, the exploded dataframes have too many rows and final sets have too many items to fit in memory. Is there an (ideally efficient) algorithm to get this done without having to explode the dataframes?

Answer 1

One algorithm is to consider all pairs of rows (one row from df1, one row from df2), and find whether there is any intersection between these two rows. Given two rows, this is easy: you compute the intersection of the sets in each column. The running time will be $O(n_1n_2)$ where $n_1n_2$ are the number of rows in df1,df2, which is quadratic and thus potentially slow, but the memory requirements are very small.

Another approach is to iterate over the intersection in lexicographic order. Here is the algorithm:

• Compute $$C = \bigcup \{t.\text{country} \mid t \in \text{df1}\} \cap \bigcup \{t.\text{country} \mid t \in \text{df2}\},$$ the set of countries that appear at least once in df1 and at least once in df2.

• For each country $c \in C$:

  • Compute $$A = \bigcup \{t.\text{age} \mid c \in t.\text{country}, t \in \text{df1}\} \cap \bigcup \{t.\text{age} \mid c \in t.\text{country}, t \in \text{df2}\},$$ the set of ages that appear at least once in df1 and at least once in df2, together with country $c$.

  • For each age $a \in A$:

    • Compute $$P = \bigcup \{t.\text{product} \mid c \in t.\text{country}, a \in t.\text{age}, t \in \text{df1}\} \cap \bigcup \{t.\text{age} \mid c \in t.\text{country}, a \in t.\text{age}, t \in \text{df2}\},$$ the set of products that appear at least once in df1 and at least once in df2, together with country $c$ and age $a$.

    • Output $(c,a,p)$ for each $p \in P$.

In the worst case, this could be inefficient if this iteration forces you to explore all possibilities of $c,a$, but in practice I suspect that it will allow you to prune the search early (e.g., $A$ will often not contain all possible age groups), hence this might be more efficient in practice.

You can compute $C,A$ efficiently by constructing appropriate indices. Computing $P$ might require iterating over the entire data frames.

A third approach is to compute the explosion for all pairs of attributes. In other words, compute all possible values for (country,age) that appear in df1, all possible values for (country,age) that appear in df2, and take the intersection. Then, compute all possible values for (age,product) that appear in df1, all possible values for (age,product) that appear in df2, and take the intersection. Finally, do the same for (country,product). Next, use the following algorithm:

• For each country $c$:

  • For each (country,age) $(c,a)$ in the intersection:

    • For each product $p$ such that $(a,p)$ is in the intersection for (age,product) and $(c,p)$ is in the intersection for (country,product):

      • Check whether there is a row in both df1 and df2 with $(c,a,p)$, by linearly scanning through both tables. If yes, output $(c,a,p)$.

You can compute the pairwise intersections pretty efficiently by exploding each row and taking the union over all rows. This might be the best of the three algorithms in practice. The memory requirement is not too great because you only require pairwise explosions, not three-way explosions.