We consider the following set intersection reporting problem. We have a collection of initially empty sets and would like to process an intermixed sequence of n updates (insertions into and deletions from individual sets) and q queries (reporting the intersection of two sets). We cast this problem in the arithmetic model of computation of Fredman and Yao and show that any algorithm that fits in this model must take time O(q + n√(q)) to process a sequence of n updates and q queries, ignoring factors that are polynomial in log n. We also show that this bound is tight in this model of computation, again to within a polynomial in log n factor, improving upon a result of Yellin. Furthermore, we consider the case q = O(n) with an additional space restriction. We only allow the use of m memory locations, where m is less than or equal to n1.5. We show a tight bound of O(n2/m(1/3)) for a sequence of n operations, again ignoring the polynomial in log n factors.
