Adaptive intersection and t-threshold problems
Jérémy Barbay, Claire Kenyon · 2002
Consider the problem of computing the intersection of k sorted sets. In the comparison model, we prove a new lower bound which depends on the non-deterministic complexity of the instance, and implies that the algorithm of Demaine, L'opez-Ortiz and Munro [2] is usually optimal in this "adaptive" sense. We extend the lower bound and the algorithm to the t-Threshold Problem, which consists in finding the elements which are in at least t of the k sets. These problems are motivated by boolean queries in text database systems. 1