Invertible Bloom Lookup Tables with Less Randomness and Memory
arxiv.org
arxiv.org
Our implementation communicates a difference of <=N b-bit entries with exactly N*b bits with 100% success. The cost for this communications efficiency and reliability is that the decoder takes CPU time quadratic in N, instead of IBLT's linear decoder. However, when N is usually small, if the implementation is fast this can be fine -- especially since you wouldn't normally want to use set recon unless you were communications limited.
For the sketch sizes (both low N and low bits per entry) we were interested in for relaying transactions in the Bitcoin network pinsketch/minisketch is more than a dozen times more communications efficient than low failure rate iblt. The concrete efficiency of this paper isn't yet clear to me-- though at a glance I think it also will not be great for small sizes only asymptotically (which is, of course, also where the computational costs are also an issue).
Pinsketches and iblt can also be combined-- one can use pinsketches as the cells of an iblt and one can also use a small pinsketch to improve the failure rate of an iblt (since when a correctly sized IBLT fails, it's usually just due to a single undecodable cycle) which can be corrected using pinsketch by only a tiny amount of data.
Just append a new salt to each input. For input ‘abc’ hashed say 8 times you simply construct abc-1, abc-2, abc-3, etc. up to abc-8 and hash each one and there you have 8 hash values that are no more prone to collisions than values produced by 8 independent hash functions.
Concerned that abc-n might appear naturally in the input? Fine, append an odd string that’s unlikely to appear in the input if that really is your genuine concern. Or pass the salt in as a second parameter instead.
And if your one hash function is so bad that abc-n is entangled with abc-n’, find a better hash function.
I admit this is not my field so this may be a naive take. What am I missing?
I’m just glad im not the only one to wonder this. Perhaps that’s the issue. It feels wrong for some reason despite not being an issue in practice.
I guess that hash function outputs aren't perfectly uniformly distributed. E.g. if a toy hash function (a) produces a 2-bit output for a gajillion random inputs, you wouldn't get a quarter of the values in each bucket. Maybe you'd get 30% in 00, 20% in 01, and 25% in both buckets 10 and 11. Salting the inputs wouldn't help with that. It'd only make similar inputs less likely to collide, but collisions would still be more likely in the worst case.
By combining different a hash function (b) with different "lumps", I suppose that the lumps would even out so that you'd approach a probability of .25 in each bucket.
00 01 10 11
a .30 .20 .25 .25
b .22 .22 .25 .31
a+b .26 .21 .25 .28
[1] https://www.eecs.harvard.edu/%7Emichaelm/postscripts/tr-02-0... [2] https://stackoverflow.com/questions/70963247/bloom-filters-w...
Yes, it's about randomness and probability of collisions. Adding two characters might be OK or not, it depends on the hash function and the use case. For example, the Java "String.hashCode" method return "abc-1": 92597638, "abc-2": 92597639; the hash code of the "-2" is (almost) always one greater than the "-1" variant. So the two are not independent. Anyway 32-bit hash functions might not be good and you need 64 bit. Then you should use something like MurmurHash.
But you don't need to compute MurmurHash twice. It is probably enough to compute one MurmurHash, and then hash this hash code using an integer hash function [1]: h1=integerHash(hash + 1), h2=integerHash(hash + 2). This is almost twice as fast for string data.
For certain use cases, for example for Bloom filters, you need more hash "functions". For Bloom filters, it is even simpler: you can split a 64-bit hash code into a 32-bit start, and a 32-bit offset. And then use: h(x)=start+x*offset. That means h(3)=h(2)+offset and so on. It is really fast.
https://stackoverflow.com/questions/664014/what-integer-hash...
I come from cheminformatics, where we've used a form of superimposed coding very similar to a Bloom filter. In one incarnation, developed in the 1980s, enumerate all linear structures of up to length 7, determine a unique order based on atom and bond characteristics, convert that into a PRNG seed, and generate (typically) 4 values, each used to set a bit in a bitstring of size ~1024 bits.
I write similar because (1) in some cases the number of bits is not fixed, eg, it may vary depending on the structure, and (2) it uses a PRNG instead of `n` different independent hash functions.
I'm therefore curious if PRNGs have been examined in a Bloom filter context, or for MinHash, which also has `n` different hash functions. Then I can drop (2) from my list of differences.
I'm not, because that would turn in to "abc-n-1", "abc-n-2", etc.
> Each of the arrays has its own hash function h_i
If that's what you're objecting to, isn't it just that your 'append a new salt and then hash' is a hash function h_i where i is the salt and h the 'original'/underlying hash function?
I don't think it means go looking for an array of well-known named hash functions like [md5, sha1, sha224, sha256, ...].
But there's more to this. This is a theoretical paper, the algorithm has to work for any N. Even if the N is larger than the number of particles in the known universe. That's how theory works, you need guarantees and theorems.
Then it becomes clear that no "practical" hash function can actually work for this, by a simple pigeonhole argument: you have only 64 bits (or 128 bits, ...) of output, so at some point you'll get too many collisions for anything to work.
Then you can start wondering: if I use "salt" (that is, a parameter), how many bits should that salt have, depending on N? How do you guarantee that the parametric family you have always guarantee sufficient independence, and you don't start seeing weird correlations when you start having enough hash functions and running out of entropy?
In practice, these considerations are not made, because we don't even know why the hash functions we use actually work. There is very little theory behind them: their quality is mostly empirically assessed by enormous batteries of statistical tests.
They don't mean that you should use several different hash algorithms.
(Although, granted, most Bloom filter papers do draw m functions from a k-wise independent family. That brings me to 2…)
2. The target audience is different. CS theory papers often limit their scope to a smaller result. In a bloom filter context, they don’t want to concern themselves with whether a particular hash function like SHA256 behaves k-wise independently when random characters are appended to the input. They only care that a k-wise independent hash family is needed. A different paper can analyze SHA256 or whatever other hash function.
why not just use like... `N` or `K`, or like... words lol why do we still use greek letters for variable names? Why make this arbitrarily more difficult for me, a programmer who might actually be interested in implementing this data structure?
Anyway I hate to be That Guy but I'm about to read the paper and I just immediately see "symbol I don't know the name of, is that important to know?".
Every letter in Greek and English already have multiple conventional meanings that could appear in the same papers as it is. It's just a crowded space that benefits from having more symbols. And using words instead of symbols for everything would make most expressions illegible.
No, that's epsilon. In this area, delta is usually a probability. Epsilon-delta statements are usually of the time "error > epsilon with probability < delta"
Maybe there's a way in which your sense is an example of the above sense, but it's too early for me to think about that. In any case, in your sense, typically delta is implicitly meant to be thought of as small.
Anyway, point is mathematics is a language. Like all languages, it's inseparable from its culture. The symbols often carry conventional meaning and aren't purely formal/arbitrary. This helps the speakers of that language communicate more efficiently, but it means outsiders need to learn the culture too in order to properly understand "native" level speakers. And like other languages, many parts of written mathematics just don't translate correctly to another language.
Yes, and like any language there is context-dependence. In calculus you're right, epsilon and delta are usually small variations (for example in the definition of a limit).
In randomized algorithms, if you say epsilon-delta anybody will immediately associate delta with an error probability.
Yeah that sucks. All of what you're saying is true and sucks.
> You don't have to spend brain energy finding and remembering what the author said K means.
I don't believe this is true, I believe it is the opposite. A small group of people, people who are often not the ones building the libraries from this research, know what these symbols are likely to mean.
Adding a simple glossary at the top of what 'Ω' means, etc, would help.
> Every letter in Greek and English already have multiple conventional meanings that could appear in the same papers as it is.
Yes, that's one of the many reasons why it's a terrible practice. The same symbols can mean different things across papers.
And again, with something like Ω, if you don't understand it, a glossary will not help you. It's not going to help to see "f = Ω(g) means `lim inf n->infinity f(n)/g(n) > 0`". Keep in mind this is a paper, not a tutorial on complexity theory.
> Yes, that's one of the many reasons why it's a terrible practice. The same symbols can mean different things across papers.
They can just like homonyms in other languages, but the meaning is usually clear from context. If you see "probabilitly 1-δ", you can expect that means "close to 100%", and probably "as close as you'd like" by tweaking some parameter that affects δ. Where there is ambiguity, the author typically spells it out. In longer works like books, authors often have an intro chapter/section where they list all of their notation even if it's completely standard with no ambiguity.
> So I'd expect that someone building libraries for data structures does understand it (or could refresh their memory).
Why? It's not related to the same skillset. I can and have built data structures from papers and I don't think that memorizing the greek alphabet is a useful prerequisite.
> And again, with something like Ω, if you don't understand it, a glossary will not help you.
No one is asking for a wikipedia quote. Just "Ω: Referring to the asymptotic complexity bound" or something like that would be fine and provide plenty of context.
> If you see "probabilitly 1-δ", you can expect that means "close to 100%"
How nice for you but I can not do that.
If you're writing libraries to implement novel data structures fresh from academia, you can read the math.
It's just like programming in a sense. I wouldn't say that it's a terrible practice to use symbols like > & | in code because they have different meanings in C and Bourne shell. You just gotta learn the context.
These are just the arbitrary norms we have collectively settled on. If it had been other symbols, you would have complained just as much.
We can write it out in words, sure, but then you get a sort of COBOL equivalent: wordy, hard to skim, annoying and inefficient to write and deal with once you have programming experience, but hey, at least it seems easy and accessible to beginners right?
With any user interface, including syntax, including symbols chosen, there's gonna be a group that's going to be impeded. And we collectively settled on impeding novices in favour of empowering those with experience.
it makes absolutely zero sense to complain about a community's internally created, primarily internally consumed, language. this complaint is basically the same thing (but of course much less significant) as english-speaking tourists traveling to non-predominantly-english-speaking countries and demanding that english be spoken.
if the language here doesn't speak to you directly, you are free to create your own language and culture around that language and then if your ideas are good you will develop a community that suits your needs.
>Anyway I hate to be That Guy but I'm about to read the paper and I just immediately see "symbol I don't know the name of, is that important to know?".
the solution is glaringly obvious: just like you shouldn't expect to read Война и миръ without first learning the russian language, you shouldn't expect to read this paper without first learning the language (i.e., math).
With the key difference being that math is an artificial and constructed language which can be improved. Criticising it makes sense. But while there are improvements to be in math syntax, I don't think that's the main problem here and I agree that you should be expected to learn the notation of a field before being able to understand a paper.
The problem is that academia has a culture of making papers needlessly complicated. If you try to use simple wording and explain things to the reader, you will get rejected by journals. They could easily structure it as something like "let δ be the probability of failure from 0 to 1, O(x) is big-O notation indicating the upper bound of the growth rate" etc. defining and explaining all the variables and notation first and only after that beginning to use them.
Lots of programmers would like mathematicians to define everything in their papers so that programmers don't have to learn math notation. At first glance this seems reasonable, but consider the reverse scenario.
If I were a mathematician who didn't know much about programming, I wouldn't go into a GitHub project and ask the maintainers to add little comments to explain the syntax and functions that they're using. "Looks like you're using a function called 'fold'. I don't know what that does. Can you please write a quick explanation of what it does before you use it in your code? This is too complicated for the layman to understand." The maintainer might reply that you can look up what fold means, and that they don't have time to annotate all of their code just to spell out everything to people who don't program.
Aside from that, there are references that will tell you what these symbols mean. You just have to look them up. “What does capital omega mean in algorithms?” will get you what you need here.
The comparison with programming languages doesn’t quite hold in this sense. There are glossaries for programming symbols and terms, but they are not collocated with the code. Just as we don’t expect someone to put a glossary in every GitHub repo, we also don’t expect people to put a glossary in every math paper. Like code on GitHub, the paper is written primarily for people who understand the language. If you want to learn what something means, you can look it up somewhere.
In an ideal world it would be both. But the worst case scenario is definitely greek letters that are assumed to be known.
> You just have to look them up. “What does capital omega mean in algorithms?” will get you what you need here.
lol yeah? Do that with δ and you'll get numerous unrelated results + tons of indecipherable maths. Even with Omega you'll get a wikipedia page that's full of other mathemetical symbols.
I've done this all, I've got index cards of category theory symbols so that I can read this sort of thing and it's an utter waste of time.
The thing is that programmers aren't writing code for the audience of academics and I think that's very reasonable. Why are academics not writing for the audience of programmers? That feels far less reasonable.
I think this is the core of the issue. The audience here is researchers in the field of random algorithms. Why do you think that it should also be readable by a layman programmer without any study or background knowledge in random algorithms? 99.999% of programmers will never implement invertible Bloom lookup tables. The few that will have studied the math. Seems like a fine arrangement to me
> 99.999% of programmers will never implement invertible Bloom lookup tables.
I have actually gone through a bloom filter paper in order to implement it before, with zero math background. I had to teach myself a bunch of irrelevant shit and build my own glossary - absolutely waste of time and it made the whole thing far more daunting.
More programmers would likely implement the constructs described in papers were they more approachable.
> Seems like a fine arrangement to me
To my knowledge, it is a well known problem that academic papers rarely turn into practical applications. I believe that the approachability of papers is a major component.
what does this actually mean? what do you think it actually means? conlangs like esperanto are indeed designed/constructed by some committee/body/BDFL/etc. as far as i am aware, there is no such body for mathematical notation/syntax/jargon. it is figuratively and literally a language with conventions, jargon, slang, etc. that evolves over time and varies by subgroup/community (try reading euler's papers and see how much you can parse even if you're notation-literate today).
> Criticising it makes sense.
Irrespective of whether it's a conlang or not, criticizing something you don't understand never makes sense.
> The problem is that academia has a culture of making papers needlessly complicated.
this is true and i wholly agree with you but that's structural and not individual. so criticizing these authors, that labor under these same policies/expectations, for the sins of the establishment/institution does not make sense. you want to effect (yes with the e) change along these aspects? go write emails to conference committees or journal committees or whatever. or write your own papers that buck the trend (and thereby put your own research career at risk). but don't blame someone that's on the receiving end.
You're right that they both developed over time, I was more referring to the fact that one is more open to change and less ingrained in people's minds because of its more artificial nature. If you tell people that the way they're speaking a language is bad and needs to be corrected, they take it as an insult to their culture and will likely refuse. If you say that math notation can be made simpler and more comprehensible, then it's a lot more likely that some authors will agree with you and use a revised notation in their papers, even if it means having to explain that notation to readers. Or even better, leaders in education will modify syllabi to teach the new notation.
To your other two points: I am not trying to criticize these authors, nor am I criticizing their notation. I am just pointing out the underlying reason behind the lack of comprehensibility. I don't have a solution here.
There's some fluency with the language required to understand what a free variable is, and that a sentence structure like "with probability at most δ, our thing does X" is introducing δ as a free variable. There's also some background "cultural" knowledge required to quickly parse out the fact that probabilities are between 0 and 1, so correctness probability 1-δ is the same as failure probability δ. Maybe they could've been intentional about avoiding that, but it's also normal (and even considered good style!) in natural language to phrase the same idea slightly differently from one sentence to another.
It's also pretty clear what Ω means in context even if not explicitly spelled out. They say an existing thing needs Ω(...) space and fully random hashes, and their thing needs O(...) space and O(...)-wise independent hash functions. Clearly they're talking about bounds on things, and Ω and O have standard uses in that context.
is this a serious question?
Obviously I assume academics would also be a part of that audience, but not exclusively so.
lemme ask you something: do the projects on your github have complexity bounds on the functions? i'm betting no. and if i came to you as a mathematician and asked you why your work doesn't speak to me and my community (as a potential audience) you would say to me what?
I'll go one further - I think this paper is surprisingly approachable for its content. But I'm not talking about one paper - this one happened to put some terms in its abstract without a glossary but it does later define them in a more helpful way. That's pretty rare to the point where I almost never expect it.
> lemme ask you something: do the projects on your github have complexity bounds on the functions?
I just explained that programmers don't write code for the audience of researchers. Further, programmers who publish to Github are generally not publishing for any audience but instead for resilience purposes. Otherwise, yes, programmers comment their documents in English all the time. Not the complexity because...
> why your work doesn't speak to me and my community (as a potential audience) you would say to me what?
That I've never ever had a mathematician reach out to me about my code because that almost never actually happens? Whereas programmers read research papers, or want to, all the time. Hence the paper showing up on a forum that is primarily populated by software engineers.
Ω represents: an asymptotic lower bound notation related to big O notation
\delta represents: a variation in the calculus of variations