CommonSense: Efficient Set Intersection (SetX) Protocol Based on Compressed Sensing
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.
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}
}
EUVIMED