Adaptive set intersections
Loading...
Files
Date
1998
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We introduce a new data structure, corresponding to a fully persistent SET ADT, motivated by the efficient evaluation of boolean queries in text retrieval systems. We
then focus on a key operation required by the ADT, namely the problem of efficiently evaluating an intersection expression over a static collection of integer sets. We present an optimal nondeterministic algorithm for computing the shortest proof of nonintersection for disjoint sets in the comparison model. Then we propose an adaptive algorithm for computing such proofs in deterministic fashion. The number of comparisons performed by this algorithm falls within a small multiplicative factor of the theoretical best. This algorithm is generalized to compute the intersection of nondisjoint collections of sets with the same competitive factor.