Academic & Scientific Articles

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

Browse

Author: search.filters.author.Belazzougui, DjamalSubject: search.filters.subject.Hashing

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    A Concise Forwarding Information Base for Scalable and Fast Name Lookups
    (IEEE, 2017-11-30) Yu, Ye; Belazzougui, Djamal; Qian, Chen; Zhang, Qin
    Forwarding information base (FIB) scalability and its lookup speed are fundamental problems of numerous net- work technologies that uses location-independent network names. 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.
  • Thumbnail Image
    Item
    Fully Dynamic de Bruijn Graphs
    (Springer International Publishing, 2016-09-21) Belazzougui, Djamal; Gagie, Travis; Mäkinen, Veli; Previtali, Marco
    We present a space- and time-efficient fully dynamic implementation of de Bruijn graphs, which can also support fixed-length jumbled pattern matching.
  • Thumbnail Image
    Item
    Optimal Las Vegas reduction from one-way set reconciliation to error correction
    (Springer Varlag, 2016-03-28) Belazzougui, Djamal
    Suppose we have two players A and C, where player A has a string s[0..u−1] and player C has a string t[0..u−1] and none of the two players knows the other's string. Assume that s and t are both over an integer alphabet [σ]=[0,σ−1], where the first string contains n non-zero entries. We would wish to answer the following basic question. Assuming that s and t differ in at most k positions, how many bits does player A need to send to player C so that he can recover s with certainty? Further, how much time does player A need to spend to compute the sent bits and how much time does player C need to recover the string s? This problem has a certain number of applications, for example in databases, where each of the two parties possesses a set of n key-value pairs, where keys are from the universe [u]=[0,u-1] and values are from [σ] and usually n ≪ u. In this paper, we show a time and message-size optimal Las Vegas reduction from this problem to the problem of systematic error correction of k errors for strings of length Θ(n) over an alphabet of size 2^{Θ(log⁡ σ+log⁡(u/n))}. The additional running time incurred by the reduction is linear expected (randomized) for player A and linear worst-case (deterministic) for player C , but the correction works with certainty. When using the popular Reed–Solomon codes, the reduction gives a protocol that transmits O(k(log⁡ u+log ⁡σ)) bits and runs in time O(n⋅polylog(n)(log ⁡u+log ⁡σ)) for all values of k. The time is expected for player A (encoding time) and worst-case for player C (decoding time). The message size is optimal whenever k ≤ (u⋅σ)^{1−Ω(1)}.