Flow Algorithms for Two Pipelined Filtering Problems

We give related algorithms for two problems, both motivated by query optimization in databases. This work is also related to sequential testing, minimum-sum set cover, and learning with attribute costs. The first problem concerns throughput maximization of selection (filter) ordering in a distributed setting. There are n predicates with selectivities p_1, ..., p_n. Each predicate s_i is evaluated by a separate processor which can process r_i tuples per second. Each tuple is routed through the processors until either (1) it is found not to satisfy a predicate or (2) it is found to satisfy all predicates. The problem is to route tuples through processors so as to maximize the throughput of tuple processing. We present an algorithm that solves this problem in time O(n^2), improving on an earlier $O(n^3 \log n)$ algorithm of Kodialam. The second problem can be described abstractly in terms of the following two-person zero-sum game. There are n boxes. One box contains a prize; the others are empty. It costs c_i to open box i. One player, a seeker, opens boxes until the prize is found. The goal of the seeker is to minimize ``multiplicative regret,'' the ratio between total cost incurred, and the cost that would have been incurred if the seeker had opened the box containing the prize first. The second player, the hider, chooses which box will contain the prize. The problem is to determine, given c_1, ..., c_n, an optimal (mixed) strategy for the seeker. A variant of the algorithm for the first problem solves this problem in time O(n^2). This is joint work with Anne Condon, Amol Deshpande, and Ning Wu (PODS 2006).