8 ms·

Invertible Bloom Lookup Tables (2011)

92 points by mhlakhani 12y ago

jbyers 12y ago
(2011)
- mhlakhani 12y ago
  Thanks for that. I've updated the title accordingly.
- mcherm 12y ago
  It may be 2011, but I had never heard about it, so I'm certainly happy that it got posted.
  - dang 12y ago
    I'm sure jbyers didn't mean that it shouldn't have been posted. Older posts are more than welcome here. It's just the convention to add the year in parens (and for commenters to mention when we missed one). Hacker News is "news" in the sense that a used clothing store near my house is called "New To You" :)
notastartup 12y ago
When would be a good reason to use such invertible bloom lookup tables, in my knowledge, isn't a bloom filter's purpose is to store large amount of data and give very quick replies as to whether a piece of data is in the basket but not with 100% accuracy?
- natrius 12y ago
  A real-world use is a recent proposal to make Bitcoin block propagation faster: https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2 https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2
- ChuckMcM 12y ago
  I like to think of it as giving a quick 'not in this basket' with 100% accuracy sort of tool :-)
  - yayadarsh 12y ago
    Yes, that is the primary use-case for a bloom filter, generally. I think parent is asking more about the added value of "invertible" bloom filters.
- dolzenko 12y ago
  From the paper: 1.3 Applications and Usage Cases * Database Reconciliation * Tracking Network Acknowledgments * Oblivious Selection from a Table
mrfusion 12y ago
Could this replace a python dictionary? Assuming you're ok with losing some entries now and then?
- jerf 12y ago
  That's a huge "assuming".
- mcherm 12y ago
  No, not even if you were willing to put up with arbitrary loss of some entries. For example, one of the required behaviors of a Python dictionary is that one can iterate through it, but this data structure can only be iterated if the size is small enough.
  - deleted 12y ago
    [deleted]
colmmacc 12y ago
This paper is needlessly hard to read (4 pages in before there's even an explanation!) so first a refresher: A traditional bloom filter sets k bits to 1, using k hash functions to determine which bits. So for input 'i', we might get something like: h1(i) = 0 h2(i) = 5 h3(i) = 7 and upon insertion, the bloom filter would resemble: 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 to check if an item is the bloom filter, you check the corresponding bits. After you add items to a bloom filter there's some probability that the corresponding bits for items that haven't been added are also set. So it can sometimes lie to you and say something is included, even when it's not. IBLTs replace the bits with counts of items added, and a sum of the key and value. So where Cs is the count sum, Ks is the Key sum and Vs is the value sum, the filter might look like; Cs=1 Ks=10 Vs=20 | Cs=0 Ks=0 Vs=0 | ... the positions in the table are computed just as before; the count in the count increments for every item added, and the key and value "sums" are a union of the keys and values that have been added (this might be a simple rolling count of a small checksum, or an xor). Items can be removed from the table individually, by subtracting them from the relevant counts (just like a counting bloom filter) and rolling sums. A "dump" of the table can be derived by iterating through all possible values (you need to know what they might be) and deleting them one by one, and it takes trickery to support duplicate entries. This seems like a big downside; if the input set is constrained and there is so small a finite set of inputs that you can just iterate over them, then I think it is easier to use composite numbers as your invertible lookup table. Here's how; for each potential input element, assign it a unique prime number, keep this assignment in a static lookup table. Start the table with the value "1". To store an element, multiply the current table value by the element's value. A composite number will be generated that is the product of all elements inserted into the table. To check for element presence; just use mod. Duplicates work; if the value is still congruent, then the element is still there. To remove an element, just divide by its value. A surprisingly large number of elements can be represented this way in a 64k-sized composite number. A good example of this this technique is to model Internet AS paths; give every AS number a unique prime number (there are only about 100k of them) and model AS path as the composite of its component ASes; using vectorized DIV/MOD instructions it is incredibly fast to large graph operations.
- pradn 12y ago
  Excellent explanation. Thank you! If academics want their work to be used, writing with the utmost clarity is necessary.
mhlakhani 12y ago
Note that there's a Python implementation here: https://github.com/jesperborgstrup/Py-IBLT https://github.com/jesperborgstrup/Py-IBLT
msane 12y ago
I was recently looking at bloom filters as a possible piece of a permissions system in a typical database object model. Imagine: - users have various permissions - other objects in the system require one or more permissions to be viewable by those users you can accomplish this easily with joins alone, but it becomes a performance issue rather quickly. I have a large-scale system and my intuition was that supplemental indexes based on bloom filters could help me solve this problem. i haven't figured out an exact way to apply them however.
lqdc13 12y ago
If you just want insertion, deletion, resizing and merging with better data locality and roughly same performance as Bloom Filter, also consider Quotient Filter http://arxiv.org/pdf/1208.0290.pdf http://arxiv.org/pdf/1208.0290.pdf
robmccoll 12y ago
Why use this instead of putting a bloom filter in front of a fixed hash table? In the unlucky case that two pairs have total hash collision with the IBLT you can't recover anything. Iteration cost is the same. If you need delete just use a count in the filter instead of a hash. If the table fills up, drop entries. I guess the IBLT would be able to recover info if the number of insertions crossed the threshold and deletions brought the count back down.

92 points by mhlakhani 12y ago

jbyers 12y ago

(2011)

mhlakhani 12y ago
Thanks for that. I've updated the title accordingly.
mcherm 12y ago
It may be 2011, but I had never heard about it, so I'm certainly happy that it got posted.
- dang 12y ago
  I'm sure jbyers didn't mean that it shouldn't have been posted. Older posts are more than welcome here. It's just the convention to add the year in parens (and for commenters to mention when we missed one). Hacker News is "news" in the sense that a used clothing store near my house is called "New To You" :)

notastartup 12y ago

When would be a good reason to use such invertible bloom lookup tables, in my knowledge, isn't a bloom filter's purpose is to store large amount of data and give very quick replies as to whether a piece of data is in the basket but not with 100% accuracy?

natrius 12y ago
A real-world use is a recent proposal to make Bitcoin block propagation faster: https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2 https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2
ChuckMcM 12y ago
I like to think of it as giving a quick 'not in this basket' with 100% accuracy sort of tool :-)
- yayadarsh 12y ago
  Yes, that is the primary use-case for a bloom filter, generally. I think parent is asking more about the added value of "invertible" bloom filters.
dolzenko 12y ago
From the paper: 1.3 Applications and Usage Cases * Database Reconciliation * Tracking Network Acknowledgments * Oblivious Selection from a Table

mrfusion 12y ago

Could this replace a python dictionary? Assuming you're ok with losing some entries now and then?

jerf 12y ago
That's a huge "assuming".
mcherm 12y ago
No, not even if you were willing to put up with arbitrary loss of some entries. For example, one of the required behaviors of a Python dictionary is that one can iterate through it, but this data structure can only be iterated if the size is small enough.
- deleted 12y ago
  [deleted]

colmmacc 12y ago

This paper is needlessly hard to read (4 pages in before there's even an explanation!) so first a refresher: A traditional bloom filter sets k bits to 1, using k hash functions to determine which bits. So for input 'i', we might get something like: h1(i) = 0 h2(i) = 5 h3(i) = 7 and upon insertion, the bloom filter would resemble: 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 to check if an item is the bloom filter, you check the corresponding bits. After you add items to a bloom filter there's some probability that the corresponding bits for items that haven't been added are also set. So it can sometimes lie to you and say something is included, even when it's not. IBLTs replace the bits with counts of items added, and a sum of the key and value. So where Cs is the count sum, Ks is the Key sum and Vs is the value sum, the filter might look like; Cs=1 Ks=10 Vs=20 | Cs=0 Ks=0 Vs=0 | ... the positions in the table are computed just as before; the count in the count increments for every item added, and the key and value "sums" are a union of the keys and values that have been added (this might be a simple rolling count of a small checksum, or an xor). Items can be removed from the table individually, by subtracting them from the relevant counts (just like a counting bloom filter) and rolling sums. A "dump" of the table can be derived by iterating through all possible values (you need to know what they might be) and deleting them one by one, and it takes trickery to support duplicate entries. This seems like a big downside; if the input set is constrained and there is so small a finite set of inputs that you can just iterate over them, then I think it is easier to use composite numbers as your invertible lookup table. Here's how; for each potential input element, assign it a unique prime number, keep this assignment in a static lookup table. Start the table with the value "1". To store an element, multiply the current table value by the element's value. A composite number will be generated that is the product of all elements inserted into the table. To check for element presence; just use mod. Duplicates work; if the value is still congruent, then the element is still there. To remove an element, just divide by its value. A surprisingly large number of elements can be represented this way in a 64k-sized composite number. A good example of this this technique is to model Internet AS paths; give every AS number a unique prime number (there are only about 100k of them) and model AS path as the composite of its component ASes; using vectorized DIV/MOD instructions it is incredibly fast to large graph operations.

pradn 12y ago
Excellent explanation. Thank you! If academics want their work to be used, writing with the utmost clarity is necessary.

mhlakhani 12y ago

Note that there's a Python implementation here: https://github.com/jesperborgstrup/Py-IBLT https://github.com/jesperborgstrup/Py-IBLT

msane 12y ago

I was recently looking at bloom filters as a possible piece of a permissions system in a typical database object model. Imagine: - users have various permissions - other objects in the system require one or more permissions to be viewable by those users you can accomplish this easily with joins alone, but it becomes a performance issue rather quickly. I have a large-scale system and my intuition was that supplemental indexes based on bloom filters could help me solve this problem. i haven't figured out an exact way to apply them however.

lqdc13 12y ago

If you just want insertion, deletion, resizing and merging with better data locality and roughly same performance as Bloom Filter, also consider Quotient Filter http://arxiv.org/pdf/1208.0290.pdf http://arxiv.org/pdf/1208.0290.pdf

robmccoll 12y ago

Why use this instead of putting a bloom filter in front of a fixed hash table? In the unlucky case that two pairs have total hash collision with the IBLT you can't recover anything. Iteration cost is the same. If you need delete just use a count in the filter instead of a hash. If the table fills up, drop entries. I guess the IBLT would be able to recover info if the number of insertions crossed the threshold and deletions brought the count back down.