An algorithm for dynamic subset and intersection testing

Abstract

Consider a sequence of m operations, where each operation either creates a set, inserts (deletes) an element into (from) a set, queries whether a particular element is in a set, queries whether or not one set is a subset of another, or queries whether or not the intersection of two sets is empty. We show that for any integer k, one can implement subset and intersection testing in time O(m(k-1)/k log m) and all of the other operations in time O(m1/k log m). Our algorithm requires O(m(k+1)/k) space. With k=2, this yields a worst-case time complexity of O(ζm log m) per operation, and uses O(m 3 2) space. We also give an alternative implementation so that an operation at time t can be implemented in amortized time O(ζnt log nt), where nt is the size of the system of sets at time t. © 1994.