IEICE TRANSACTIONS on Fundamentals
Finite Length Analysis on Listing Failure Probability of Invertible Bloom Lookup Tables
Summary :
An Invertible Bloom Lookup Tables (IBLT) is a data structure which supports insertion, deletion, retrieval and listing operations for the key-value pair. An IBLT can be used to realize efficient set reconciliation for database synchronization. The most notable feature of the IBLT is the complete listing operation of key-value pairs based on the algorithm similar to the peeling algorithm for low-density parity check (LDPC) codes. In this paper, we will present a stopping set (SS) analysis for the IBLT that reveals finite length behaviors of the listing failure probability. The key of the analysis is enumeration of the number of stopping matrices of given size. We derived a novel recursive formula useful for computationally efficient enumeration. An upper bound on the listing failure probability based on the union bound accurately captures the error floor behaviors.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.12 pp.2309-2316
- Publication Date
- 2014/12/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E97.A.2309
- Type of Manuscript
- Special Section PAPER (Special Section on Information Theory and Its Applications)
- Category
- Coding Theory
Authors
Daichi YUGAWA
Nagoya Institute of Technology
Tadashi WADAYAMA
Nagoya Institute of Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Daichi YUGAWA, Tadashi WADAYAMA, "Finite Length Analysis on Listing Failure Probability of Invertible Bloom Lookup Tables" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 12, pp. 2309-2316, December 2014, doi: 10.1587/transfun.E97.A.2309.
Abstract: An Invertible Bloom Lookup Tables (IBLT) is a data structure which supports insertion, deletion, retrieval and listing operations for the key-value pair. An IBLT can be used to realize efficient set reconciliation for database synchronization. The most notable feature of the IBLT is the complete listing operation of key-value pairs based on the algorithm similar to the peeling algorithm for low-density parity check (LDPC) codes. In this paper, we will present a stopping set (SS) analysis for the IBLT that reveals finite length behaviors of the listing failure probability. The key of the analysis is enumeration of the number of stopping matrices of given size. We derived a novel recursive formula useful for computationally efficient enumeration. An upper bound on the listing failure probability based on the union bound accurately captures the error floor behaviors.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.2309/_p
Copy
@ARTICLE{e97-a_12_2309,
author={Daichi YUGAWA, Tadashi WADAYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Finite Length Analysis on Listing Failure Probability of Invertible Bloom Lookup Tables},
year={2014},
volume={E97-A},
number={12},
pages={2309-2316},
abstract={An Invertible Bloom Lookup Tables (IBLT) is a data structure which supports insertion, deletion, retrieval and listing operations for the key-value pair. An IBLT can be used to realize efficient set reconciliation for database synchronization. The most notable feature of the IBLT is the complete listing operation of key-value pairs based on the algorithm similar to the peeling algorithm for low-density parity check (LDPC) codes. In this paper, we will present a stopping set (SS) analysis for the IBLT that reveals finite length behaviors of the listing failure probability. The key of the analysis is enumeration of the number of stopping matrices of given size. We derived a novel recursive formula useful for computationally efficient enumeration. An upper bound on the listing failure probability based on the union bound accurately captures the error floor behaviors.},
keywords={},
doi={10.1587/transfun.E97.A.2309},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - Finite Length Analysis on Listing Failure Probability of Invertible Bloom Lookup Tables
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2309
EP - 2316
AU - Daichi YUGAWA
AU - Tadashi WADAYAMA
PY - 2014
DO - 10.1587/transfun.E97.A.2309
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2014
AB - An Invertible Bloom Lookup Tables (IBLT) is a data structure which supports insertion, deletion, retrieval and listing operations for the key-value pair. An IBLT can be used to realize efficient set reconciliation for database synchronization. The most notable feature of the IBLT is the complete listing operation of key-value pairs based on the algorithm similar to the peeling algorithm for low-density parity check (LDPC) codes. In this paper, we will present a stopping set (SS) analysis for the IBLT that reveals finite length behaviors of the listing failure probability. The key of the analysis is enumeration of the number of stopping matrices of given size. We derived a novel recursive formula useful for computationally efficient enumeration. An upper bound on the listing failure probability based on the union bound accurately captures the error floor behaviors.
ER -
English
