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, Lopez-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.
展开▼
机译：考虑计算 k 排序集的交集的问题。在比较模型中，我们证明了一个新的下限，该下限取决于实例的不确定性，并暗示Demaine，Lopez-Ortiz和Munro [2]的算法通常在这种“自适应”意义上是最优的。我们将下界和算法扩展到 t-Threshold问题，该问题包括查找至少在 k 的 t 中的元素>集。这些问题是由文本数据库系统中的布尔查询引起的。
展开▼
