The search functionality is under construction.

Author Search Result

[Author] Daichi YUGAWA(1hit)

1-1hit
  • Finite Length Analysis on Listing Failure Probability of Invertible Bloom Lookup Tables

    Daichi YUGAWA  Tadashi WADAYAMA  

     
    PAPER-Coding Theory

      Vol:
    E97-A No:12
      Page(s):
    2309-2316

    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.