elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

Irregular Invertible Bloom Look-Up Tables

Lazaro, Francisco und Matuz, Balazs (2021) Irregular Invertible Bloom Look-Up Tables. In: 11th International Symposium on Topics in Coding, ISTC 2021. International Symposium on Topics in Coding 2021, 2021-08-30 - 2021-09-03, Montreal, Canada. doi: 10.1109/ISTC49272.2021.9594198. ISBN 978-166540943-8.

[img] PDF
276kB

Kurzfassung

We consider invertible Bloom lookup tables (IBLTs) which are probabilistic data structures that allow to store keyvalue pairs. An IBLT supports insertion and deletion of key-value pairs, as well as the recovery of all key-value pairs that have been inserted, as long as the number of key-value pairs stored in the IBLT does not exceed a certain number. The recovery operation on an IBLT can be represented as a peeling process on a bipartite graph. We present a density evolution analysis of IBLTs which allows to predict the maximum number of key-value pairs that can be inserted in the table so that recovery is still successful with high probability. This analysis holds for arbitrary irregular degree distributions and generalizes results in the literature. We complement our analysis by numerical simulations of our own IBLT design which allows to recover a larger number of keyvalue pairs as state-of-the-art IBLTs of same size.

elib-URL des Eintrags:https://elib.dlr.de/148301/
Dokumentart:Konferenzbeitrag (Vortrag)
Titel:Irregular Invertible Bloom Look-Up Tables
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Lazaro, FranciscoFrancisco.LazaroBlasco (at) dlr.dehttps://orcid.org/0000-0003-0761-7700NICHT SPEZIFIZIERT
Matuz, BalazsBalazs.Matuz (at) dlr.dehttps://orcid.org/0000-0002-0133-6564NICHT SPEZIFIZIERT
Datum:2021
Erschienen in:11th International Symposium on Topics in Coding, ISTC 2021
Referierte Publikation:Ja
Open Access:Ja
Gold Open Access:Nein
In SCOPUS:Ja
In ISI Web of Science:Ja
DOI:10.1109/ISTC49272.2021.9594198
ISBN:978-166540943-8
Status:veröffentlicht
Stichwörter:Bloom filters, Data structures, set reconciliation, density evolution
Veranstaltungstitel:International Symposium on Topics in Coding 2021
Veranstaltungsort:Montreal, Canada
Veranstaltungsart:internationale Konferenz
Veranstaltungsbeginn:30 August 2021
Veranstaltungsende:3 September 2021
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Raumfahrt
HGF - Programmthema:keine Zuordnung
DLR - Schwerpunkt:Raumfahrt
DLR - Forschungsgebiet:R - keine Zuordnung
DLR - Teilgebiet (Projekt, Vorhaben):R - keine Zuordnung
Standort: Oberpfaffenhofen
Institute & Einrichtungen:Institut für Kommunikation und Navigation > Satellitennetze
Hinterlegt von: Lazaro, Francisco
Hinterlegt am:14 Jan 2022 10:01
Letzte Änderung:07 Jun 2024 11:05

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.