Intersection joins under updates

Abstract In an intersection join, we are given t sets R 1 , . . . , R t of axis-parallel rectangles in R d , where d ≥ 1 and t ≥ 2 are constants, and a join topology which is a connected undirected graph G on vertices 1 , . . . , t . The result consists of tuples ( r 1 , . . . , r t ) ∈ R 1 × . . . × R t where r i ∩ r j ≠ ∅ for all i , j connected in G. A structure is feasible if it stores O ˜ ( n ) words, supports an update in O ˜ ( 1 ) amortized time, and can enumerate the join result with an O ˜ ( 1 ) delay, where n = ∑ i | R i | and O ˜ ( . ) hides a polylog n factor. We provide a dichotomy as to when feasible structures exist: they do when t = 2 or d = 1 ; subject to the OMv-conjecture, they do not exist when t ≥ 3 and d ≥ 2 , regardless of the join topology.