(data structure)
Definition: Algorithms and an array of cells to store key/value pairs. Each cell has a count of how many pairs are mapped to the cell, the sum of the keys mapped to it, and the sum of the values mapped to it. Using k hash functions, each pair is mapped to T[h1(k)], T[h2(k)], ..., T[hk(k)].
Also known as IBLT.
Generalization (I am a kind of ...)
dictionary plus a listEntries() operation and the ability to handle duplicate keys with some implementations.
Aggregate child (... is a part of or used in me.)
array, hash function.
See also Bloom filter.
Note: The implementation details guarantee that with high probability, each key/value pair has at least one cell to itself, which has a count of 1. The value and key can be retrieved from that cell.
Special care must be taken to either (a) not insert keys multiple times or delete keys that are not present or (b) elaborate the algorithms and data structure.
listEntries() reports the key/value pair in each cell with a count of 1, and then removes that key/value pair.
Author: PEB
Michael T. Goodrich and Michael Mitzenmacher, Invertible Bloom Lookup Tables, 2011. (V3 is October 2015.) Available at https://arxiv.org/pdf/1101.2245.pdf.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 8 June 2018.
HTML page formatted Wed Mar 13 12:42:46 2019.
Cite this as:
Paul E. Black, "invertible Bloom lookup table", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 8 June 2018. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/invertibleBloomTable.html