Academic & Scientific Articles

Permanent URI for this communityhttp://dl.cerist.dz/handle/CERIST/3

Browse

Has files: YesSubject: search.filters.subject.Data structures

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Better Space-Time-Robustness Trade-Offs for Set Reconciliation
    (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024-07) Belazzougui , Djamal; Kucherov, Gregory; Walzer, Stefan
    We consider the problem of reconstructing the symmetric difference between similar sets from their representations (sketches) of size linear in the number of differences. Exact solutions to this problem are based on error-correcting coding techniques and suffer from a large decoding time. Existing probabilistic solutions based on Invertible Bloom Lookup Tables (IBLTs) are time-efficient but offer insufficient success guarantees for many applications. Here we propose a tunable trade-off between the two approaches combining the efficiency of IBLTs with exponentially decreasing failure probability. The proof relies on a refined analysis of IBLTs proposed in (Bæk Tejs Houen et al. SOSA 2023) which has an independent interest. We also propose a modification of our algorithm that enables telling apart the elements of each set in the symmetric difference.
  • Thumbnail Image
    Item
    Memory-Efficient and Ultra-Fast Network Lookup and Forwarding Using Othello Hashing
    (IEEE, 2018-04-11) Yu, Ye; Belazzougui, Djamal; Qian, Chen; Zhang, Qin
    Abstract: Network algorithms always prefer low memory cost and fast packet processing speed. Forwarding information base (FIB), as a typical network processing component, requires a scalable and memory-efficient algorithm to support fast lookups. In this paper, we present a new network algorithm, Othello hashing, and its application of a FIB design called concise, which uses very little memory to support ultra-fast lookups of network names. Othello hashing and concise make use of minimal perfect hashing and relies on the programmable network framework to support dynamic updates. Our conceptual contribution of concise is to optimize the memory efficiency and query speed in the data plane and move the relatively complex construction and update components to the resource-rich control plane. We implemented concise on three platforms. Experimental results show that concise uses significantly smaller memory to achieve much faster query speed compared to existing solutions of network name lookups.