2
$\begingroup$

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve looping over every item in the collection and applying each filter to each item. An item will be rejected early if any one of the filters fails during this process.

Each filter has a runtime that varies significantly. And, we know a-priori what percent of the collection each filter will filter out. Given this, how do I find the ordering I should apply my filters to each item with the fasted expected run-time overall?

For example, filter A runs in 5 ms and filters out 50% of the collection on average. Filter B runs in 1 ms and filters out 25% of the collection on average. From this, we know that ordering A,B gives 5 + 0.5 * 1 = 5.5 ms average runtime, and B,A gives 1 + 0.75 * 5 = 4.75 ms average runtime. So B,A is our fastest ordering.

I think this admits a dynamic programming solution (since fastest ordering is runtime of first filter + (1 - filter fraction) * (optimal ordering of the rest), but I was wondering if this problem has a name and has been studied before? Could somebody point me to any papers?

EDIT: also, I forgot that the probability of filtering and the run-times will be correlated between filters, so my analysis above is wrong and the problem is harder. I think I can solve this with enough time but I want to catch up on prior-work before I start, if there is any (it seems like it could be a common problem). I haven't had any luck finding anything so far though.

$\endgroup$
  • $\begingroup$ 1. Are you guaranteed that the filters are independent? Your proposed approach involves multiplying probabilities, which is only correct to do if the events are independent (whether an item is filtered out is by filter X is independent of whether it's filtered out by filter Y). 2. Dynamic programming is unlikely to be applicable here, since you want to know the best order (out of all $n!$ possible orders). 3. What have you tried? If you're focused on the case where they are independent, have you tried a greedy algorithm? This smells like a problem where a greedy algorithm might work. $\endgroup$ – D.W. Dec 19 '14 at 1:10
  • $\begingroup$ I don't think the filters are independent so you're right about that. I haven't done much work on this yet, mostly I've been trying to find prior work to start off of but I haven't had any luck. $\endgroup$ – user3217070 Dec 19 '14 at 15:34
2
$\begingroup$

Independent filters

If the filters are independent, a greedy algorithm can be used to find the optimal order. Sort the filters by increasing value of $t/p$, where $t$ is the time to run the filter and $p$ is the fraction of items that are filtered out by the filter. This gives the optimal order.

To give some intuition for why this might be a plausible answer: ideally, we'd prefer filters that take less time; and ideally, we'd prefer filters that filter out a higher fraction of items. Intuitively, you can see how $t/p$ somehow incorporates both of those.

A formal proof of optimality involves an exchange argument. I won't detail the proof here, as it can be derived easily using standard techniques. For a detailed writeup of the proof, see Determine what is the best order for running filters on a dataset.


Correlated filters

If there can be correlations between the filters (i.e., they are not independent), the optimal order cannot be determined from the information provided without knowledge of the correlations.

Here's an example, based on making a small modification to your example. Suppose we have two filters, filter A and filter B. Suppose filter A runs in 4.5ms and filters out 50% on average; filter B runs in 1ms and filters out 25% on average. Also suppose that anything filtered out by filter B is also filtered out by filter A. Then the optimal order is to just do filter A. Your formulas give A,B: $4.5+0.5 \times 1 = 5.0$ and B,A: $1 + 0.75 \times 4.5 = 4.375$, so your formulas might make B,A look like the best choice -- but in fact just doing A alone is even better.


Unfortunately, in practice I would expect that filters might often be correlated. To deal with this, you'd need to know some information about the correlation structure. If you don't have any information on the correlation structure, one possible approach is to use the greedy strategy, recognizing that it might not be optimal for your particular situation. Another possible approach is to gather data on the correlation structure and then use that additional information to try to find a better order, though this may not admit as clean of an answer.

$\endgroup$
  • $\begingroup$ Great answer. I forgot about correlation. I think both the probability of filtering and the run-times can be correlated. The data I can get is the run-time and wether or not each filter passed or failed for every item. So I think I can get the correlation structure from that. Also, I forgot to mention an additional constraint that certain filters must run after others... so this could be an interesting problem to solve. I haven't found any prior work on this (maybe I don't know what to search for). Do you know of any? $\endgroup$ – user3217070 Dec 19 '14 at 15:30
  • $\begingroup$ @user3217070, OK. You could try adapting the greedy strategy (choose the one with smallest $t/p$, out of all that could appear next) and see if it is optimal. I don't know if it has been studied before. $\endgroup$ – D.W. Dec 20 '14 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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