In the set reconciliation (\textsf{ SetR}) problem, two parties Alice and Bob, holding sets $\mathsf{ A}$ and $\mathsf{ B}$, communicate to learn the symmetric difference $\mathsf{ A} \Delta \mathsf{ B}$. In this work, we study a related but under-explored problem: set intersection (\textsf{ SetX})~\cite{ Ozisik2019}, where both parties learn $\mathsf{ A} \cap \mathsf{ B}$ instead. However, existing solutions typically reuse \textsf{ SetR} protocols due to the absence of dedicated \textsf{ SetX} protocols and the misconception that \textsf{ SetR} and \textsf{ SetX} have comparable costs. Observing that \textsf{ SetX} is fundamentally cheaper than \textsf{ SetR}, we developed a multi-round \textsf{ SetX} protocol that outperforms the information-theoretic lower bound of \textsf{ SetR} problem. In our \textsf{ SetX} protocol, Alice sends Bob a compressed sensing (CS) sketch of $\mathsf{ A}$ to help Bob identify his unique elements (those in $\mathsf{ B \setminus A}$). This solves the \textsf{ SetX} problem, if $\mathsf{ A} \subseteq \mathsf{ B}$. Otherwise, Bob sends a CS sketch of the residue (a set of elements he cannot decode) back to Alice for her to decode her unique elements (those in $\mathsf{ A \setminus B}$). As such, Alice and Bob communicate back and forth %with a set membership filter (SMF) of estimated $\mathsf{ B \setminus A}$. Alice updates $\mathsf{ A}$ and communication repeats until both parties agrees on $\mathsf{ A} \cap \mathsf{ B}$. On real world datasets, experiments show that our $\mathsf{ SetX}$ protocol reduces the communication cost by 8 to 10 times compared to the IBLT-based $\mathsf{ SetR}$ protocol.
Categories: cs.DC cs.NI