PulseExploreJournal ClubResearchersJournals
Instagram
HomeJournal ClubExplore
Synapse
⌘+K
Synapse
April 3, 2026ACM SIGMETRICS Performance Evaluation Review

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

View Full Paper
Ask AI
Bookmark
Share

Authors

JMJingfan MengTYTianji YangJXJun Xu

Discussion

Loading...

Member takes

Overview

This work develops a multi-round protocol to optimize set intersection, reducing communication costs significantly.

Key Points

  • The research aims to develop a dedicated protocol for efficient set intersection between two parties holding distinct sets.
  • Developed a multi-round SetX protocol, enabling iterative communication between two parties.
  • Utilized compressed sensing (CS) sketches to represent sets and facilitate efficient exchanges.
  • Alice sends a CS sketch of her set A to Bob for processing and identifying his unique elements.
  • Bob returns a CS sketch of the elements he cannot decode, enabling Alice to retrieve her unique elements.
  • Achieved an 8 to 10 times reduction in communication cost compared to existing IBLT-based SetR protocols.
  • Demonstrated that SetX is fundamentally cheaper and more efficient than SetR for set intersection tasks.

Cite This Study

Meng et al. (2026) studied this question.

synapsesocial.com/papers/69cf5dd55a333a821460bdf5https://doi.org/10.1145/3797823.3797837
View Full Paper
Ask AI
Bookmark
Share