Dynamic Set Intersection

Abstract. Consider the problem of maintaining a family F of dynamic sets subject to insertions, deletions, and set-intersection reporting queries: given S, S ′ ∈ F, report every member of S ∩S ′ in any order. We show that in the word RAM model, where w is the word size, given a cap d on the maximum size of any set, we can support set intersection queries in O ( d w / log2 w) expected time, and updates in O(1) expected time. Using this algorithm we can list all t triangles of a graph G = (V,E) in O(m+ mα w / log2 w + t) expected time, where m = |E | and α is the arboric-ity of G. This improves a 30-year old triangle enumeration algorithm of Chiba and Nishizeki running in O(mα) time. We provide an incremental data structure on F that supports inter-section witness queries, where we only need to find one e ∈ S ∩ S′. Both queries and insertions take O N w / log2 w expected time, wher