# Algorithm to identify common subsets

Given a large dataset $$D$$ and multiple sets of filters that can be applied to $$D$$, e.g.

• $$setA = \{filterOnColorRed\}$$
• $$setB = \{filterOnAgeGreaterThan20\}$$
• $$setC = \{filterOnColorRed, filterOnAgeGreaterThan20\}$$
• $$setD = \{filterOnColorRed, filterOnAgeGreaterThan20, filterOnSizeIsLarge\}$$

where each filter is expensive (but it's unknown ahead of time how expensive each filter is, so we assume they all have a similar cost, importantly applying multiple filters at once is only as expensive as applying a single filter), it would helpful to compute the set such that:

$$setA$$ or $$setB$$ are computed first, and then $$setC$$ ultimately followed by $$setD$$, rationale being that using $$setA$$ or $$setB$$ makes it cheaper to compute $$setC$$, and the same can be said about using $$setC$$ to compute $$setD$$.

Is there an algorithm that can be used to solve this efficiently (assuming $$N$$ sets of filters, of varying sizes)?

Or is the best approach to basically build a DAG where each set of filter is a vertex, and there's an edge from $$V1$$ to $$V2$$ iff $$V1$$ is a strict subset of $$V2$$ (let's assume no two sets are equal to simplify things a bit). And then run a topological sort over this graph and process the sets in the resulting order?

As an extension to the question, given:

• $$setA' = \{filterOnColorRed, filterOnSizeIsLarge\}$$
• $$setB' = \{filterOnAgeGreaterThan20, filterOnSizeIsLarge\}$$

How about and algorithm that identifies that creating notional sets might be useful, e.g. in this case processing $$filterOnSizeIsLarge$$ before computing $$setA'$$ and $$setB'$$ would be beneficial.

• There seems to be something missing like cost of applying filters depends linearly on size of input Jul 13, 2023 at 2:55
• @greybeard yeah, basically applying one (or multiple filters) is a function is $O(N)$ of the number of rows in $D$/set being filtered.
– foo
Jul 13, 2023 at 15:54

I suggest creating a DAG, as you suggest, with one vertex per set, and an edge from set $$S$$ to set $$T$$ if $$T$$ is guaranteed to be a subset of $$S$$ (i.e., the filters of $$T$$ are a superset of the filters of $$S$$).
Then do a topological sort on the DAG, and process the sets in topologically sorted order. When computing a set $$S$$, with predecessors $$Q_1,\dots,Q_k$$, I can see two options:
• Use a merge join to compute the intersection $$Q_1 \cap \cdots \cap Q_k$$, scan linearly through the items in the intersection, and check which items are in $$S$$ (i.e., which items additionally satisfy all filters that are associated with $$S$$ and aren't already associated with $$Q_1,\dots,Q_k$$).
• Pick whichever set $$Q_i$$ is smallest, scan linearly through the items in $$Q_i$$, and check which items are in $$S$$ (i.e., which items satisfy all filters that are associated with $$S$$ and aren't already associated with $$Q_i$$).
If you only have a single set, and the time to check $$k$$ filters is the sum of the times to check each of the filters separately (rather than the time to check $$k$$ filters at once being the same as the time to check a single filter), see What is the optimal strategy for filtering a large collection of items with multiple filter functions?.