Method for transmitting a bloom filter from a transmitter unit to a receiver unit
AssigneeDeutsches Zentrum für Luft- und Raumfahrt e.V.
InventorFrancisco Lázaro Blasco
Life of this patent
Estimating the term…
Abstract
The invention relates to a method for transmitting a Bloom filter from a transmitter unit to a receiver unit. The method includes the following steps of providing a Bloom filter by the transmitter unit; compressing the Bloom filter by the transmitter unit, the compression of the Bloom filter being performed based on a Slepian-Wolf encoding method; and transmitting the Bloom filter compressed using the Slepian-Wolf encoding method from the transmitter unit to the receiver unit.
Claims13
A method for synchronizing sets of data with a Bloom filter between a transmitter unit and a receiver unit, the method comprising the following steps:
- generating, by the transmitter unit, a Bloom filter representing a first set of data items stored at the transmitter unit, the Bloom filter comprising a bit array of length m and generated using at least two independent hash functions;
- compressing, by the transmitter unit, the Bloom filter using a distributed source coding technique based on Slepian-Wolf encoding to generate a syndrome;
- and
- transmitting, by the transmitter unit, the syndrome to the receiver unit;
- reconstructing, by the receiver unit, an approximation of the Bloom filter using the received syndrome and a locally generated Bloom filter constructed by the receiver unit from a second set of data items;
- and
- determining, by the receiver unit, differences between the first set of data items and the second set of data items based on the reconstructed Bloom filter.
A method for reconstructing a Bloom filter by a receiver unit, the method comprising the following steps:
- receiving, by a receiver unit, a syndrome generated by a transmitter unit from a Bloom filter representing a first set of data items, the Bloom filter compressed using a distributed source coding technique based on Slepian-Wolf encoding;
- generating, by the receiver unit, a second Bloom filter representing a second set of data items, using at least two independent hash functions;
- and
- reconstructing, by the receiver unit, an approximation of the Bloom filter representing the first set of data items using the received syndrome and the second Bloom filter.
A transmitter unit comprising a processor unit, a memory unit and a communication unit, the transmitter unit being configured to:
- generate a Bloom filter representing a first set of data items, the Bloom filter comprising a bit array of length m and constructed using at least two independent hash functions;
- compress the Bloom filter, the compression of the Bloom filter using a distributed source coding technique based on Slepian-Wolf encoding to generate a syndrome;
- transmit the syndrome to a receiver unit;
- and
- initiate a synchronization process with the receiver unit based on differences between the Bloom filter and a Bloom filter generated by the receiver unit from a second set of data items.
A receiver unit comprising a processor unit, a memory unit and a communication unit, the receiver unit being configured to:
- receive a syndrome generated by a transmitter unit from a Bloom filter representing a first set of data items, the Bloom filter being compressed using a distributed source coding technique based on Slepian-Wolf encoding;
- generate a second Bloom filter representing a second set of data items, using at least two independent hash functions;
- and
- reconstruct an approximation of the Bloom filter representing the first set of data items using the received syndrome and the second Bloom filter.
Dependencies are inferred from the claim text.