2
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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$).

I suggest you do some benchmarking to determine which of these two strategies is faster on your dataset. My guess is that the first strategy will be faster, because it requires fewer queries to the filters.


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?.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.