EUVIMEDEUVIMED entdecken
Studienprotokoll

CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing

Jingfan Meng, Tianji Yang, Jun Xu

ACM SIGMETRICS Performance Evaluation Review · 31.03.2026 · 53 (4) · 30-31

DOI: 10.1145/3797823.3797837 ↗

Kurz gefasst

Studienprotokoll in der Zeitschrift ACM SIGMETRICS Performance Evaluation Review, online erschienen am 31.03.2026. Verfasst von Jingfan Meng und 2 weiteren Autor:innen. Die Arbeit nennt 7 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In the set reconciliation (SetR) problem, two parties Alice and Bob, holding sets A and B respectively, communicate to learn the symmetric difference A Δ B. In this work, we study a related but under-explored problem: set intersection (SetX) [7], where both parties learn A ∩ B instead. Existing solutions typically reuse SetR protocols due to the absence of dedicated SetX protocols and the misconception that SetR and SetX have comparable costs. Observing that SetX is fundamentally cheaper than SetR, we have developed a multi-round SetX protocol that outperforms the information-theoretic lower bound of SetR problem. In our SetX protocol, Alice sends Bob a compressed sensing (CS) sketch of A to help Bob identify his unique elements (those in B \ A). This solves the SetX problem, if A ⊆ 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 A \ B). As such, Alice and Bob communicate back and forth until both parties agree on A ∩ B. On real world datasets, experiments show that our SetX protocol reduces the communication cost by 8 to 10 times compared to the IBLT-based SetR protocol.

Zitieren

APA

Meng, J., Yang, T., & Xu, J. (2026). CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing. ACM SIGMETRICS Performance Evaluation Review, 53(4), 30-31. https://doi.org/10.1145/3797823.3797837

Vancouver

Meng J, Yang T, Xu J. CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing. ACM SIGMETRICS Performance Evaluation Review. 2026;53(4):30-31. doi:10.1145/3797823.3797837

BibTeX
@article{Meng2026,
  author = {Meng, Jingfan and Yang, Tianji and Xu, Jun},
  title = {CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing},
  journal = {ACM SIGMETRICS Performance Evaluation Review},
  year = {2026},
  volume = {53},
  number = {4},
  pages = {30--31},
  doi = {10.1145/3797823.3797837}
}
Kostenlos starten →