.png){kind=icon}
返回
A Rate-Compatible Solution to the Set Reconciliation Problem
.png){kind=icon}
OA
AI
DOI：10.1109/TCOMM.2023.3296630.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We consider a set reconciliation setting in which two parties hold similar sets that they would like to reconcile. In particular, we focus on set reconciliation based on invertible Bloom lookup tables (IBLTs), a probabilistic data structure inspired by Bloom filters. IBLT-based set reconciliation schemes have the advantage of exhibiting low computational complexity, however, the schemes available in the literature are known to be far from optimal in terms of communication complexity (overhead). The inefficiency of IBLT-based set reconciliation can be attributed to two facts. First, it requires an estimate of the cardinality of the difference between the sets, which implies an increase in overhead. Second, to cope with uncertainties in the estimation of the cardinality of the set difference, IBLT schemes in the literature oversize the data structures, thus further increasing the overhead. In this work, we present a novel IBLT-based set reconciliation protocol that does not require estimating the cardinality of the set difference. The proposed scheme relies on what we termed multi-edge-type (MET) IBLTs. The simulation results illustrate that the novel scheme outperforms state-of-the-art IBLT-based approaches to set reconciliation in terms of communication cost, i.e., in terms of the number of bits to be exchanged.
Keyword:
Source coding
distributed databases
data structures
protocols
iterative methods
channel codes
期刊
IF:
8.3
论文数:
1.2W
被引数:
3.6W
机构
引用论文
An Improved Moth-Flame Optimization Algorithm with Adaptation Mechanism to Solve Numerical and Mechanical Engineering Problems.png)
Entropy
OAAI
EntropyIF0
OAAI分享收藏分享收藏
查看更多内容