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^{'} i n F

, report every member of

S c a p 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 (f r a c d w / l o g^{2} w)

expected time, and updates in

O (l o g w)

expected time. Using this algorithm we can list all

t

triangles of a graph

G = (V, E)

in

O (m + f r a c m a l p h a w / l o g^{2} w + t)

expected time, where

m = | E |

and

a l p h a

is the arboricity of

G

. This improves a 30-year old triangle enumeration algorithm of Chiba and Nishizeki running in

O (m a l p h a)

time. We provide an incremental data structure on

F

that supports intersection {em witness} queries, where we only need to find {em one}

e i n S c a p S^{'}

. Both queries and insertions take

O p a r e n s q r t f r a c N w / l o g^{2} w

expected time, where

N = s u m_{S i n F} | S |

. Finally, we provide time/space tradeoffs for the fully dynamic set intersection reporting problem. Using

M

words of space, each update costs

O (s q r t M l o g N)

expected time, each reporting query costs

O (f r a c N s q r t l o g N s q r t M s q r t o p + 1)

expected time where

o p

is the size of the output, and each witness query costs

O (f r a c N s q r t l o g N s q r t M + l o g N)

expected time.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Dynamic set intersection