CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914108212772864 |
|---|---|
| author | Meng, Jingfan Yang, Tianji Xu, Jun |
| author_facet | Meng, Jingfan Yang, Tianji Xu, Jun |
| contents | 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} Δ\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_19725 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing Meng, Jingfan Yang, Tianji Xu, Jun Distributed, Parallel, and Cluster Computing Networking and Internet Architecture C.2.m; G.2.m 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} Δ\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. |
| title | CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing |
| topic | Distributed, Parallel, and Cluster Computing Networking and Internet Architecture C.2.m; G.2.m |
| url | https://arxiv.org/abs/2510.19725 |