Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)

github.com

Post reply on HN
Print view View original

21–30 of 39 posts

Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)

#21

Post by pkhuong »

boyd wrote: post #20
pkhuong wrote: post #18

I'd expect a comparison with compact (or even succinct) constructions for arbitrary functions, like MWHC. Section 3.2 of https://vigna.di.unimi.it/ftp/papers/TheoryPracticeMonotone.... has a good overview. Given a set S of arbitrary hashable values, it's possible to represent a function from S to r bits in |S|r + o(|S|) bits (keys outside S are mapped to random r-bit values). More practical construction hit ~1.23 |S|…

My understanding is that a perfect hash function maps elements elements to a unique integer (i.e., it's a one-to-one mapping). I think PHF data structures will also always return a value. So if you look up an element not in the constructed PHF, you'll always get a "false positive" value. In contrast, a B-field lets you map a key to an arbitrary number of (typically non-unique) values. So I could map a million element…

The MWHC construction represents minimal (monotone!) perfect hash functions as arbitrary functions to the ceil(log(n)) bits needed to store the rank... where the value happens to be the rank, but could be anything.

Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)

#22

Post by boyd »

pkhuong wrote: post #21
boyd wrote: post #20

Earlier quoted context omitted.

My understanding is that a perfect hash function maps elements elements to a unique integer (i.e., it's a one-to-one mapping). I think PHF data structures will also always return a value. So if you look up an element not in the constructed PHF, you'll always get a "false positive" value. In contrast, a B-field lets you map a key to an arbitrary number of (typically non-unique) values. So I could map a million element…

The MWHC construction represents minimal (monotone!) perfect hash functions as arbitrary functions to the ceil(log(n)) bits needed to store the rank... where the value happens to be the rank, but could be anything.

... meaning it is an "injective" function that maps unique key-value pairs, correct? Genuinely asking, I have glancing familiarity via their use in assembly algorithms but (a) don't have a formal math/CS background; and (b) haven't read any of the papers recently.

Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)

#23

Post by pkhuong »

boyd wrote: post #22
pkhuong wrote: post #21

Earlier quoted context omitted.

The MWHC construction represents minimal (monotone!) perfect hash functions as arbitrary functions to the ceil(log(n)) bits needed to store the rank... where the value happens to be the rank, but could be anything.

... meaning it is an "injective" function that maps unique key-value pairs, correct? Genuinely asking, I have glancing familiarity via their use in assembly algorithms but (a) don't have a formal math/CS background; and (b) haven't read any of the papers recently.

No, it doesn't have to be injective. In theory, the range can be any group. It's k bits in practice (with addition mod 2^k or xor as the group operator), but k need not have any relationship with `lg(|S|)`.

Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)

#24

Post by esafak »

foota wrote: post #7

I wonder... The comparison here is against a bloom filter, but is this actually more similar to a sketch? Or... Actually this is sort of like a posting list (e.g., a list of places that a given document appears: https://en.m.wikipedia.org/wiki/Inverted_index )

It's a probabilistic associative array. A better benchmark is a Bloomier filter: https://en.wikipedia.org/wiki/Bloom_filter#Bloomier_filters

Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)

#25

Post by c0deb0t »

judofyr wrote: post #17

Very interesting and I'll have to read more to understand how it fully works, but _initially_ the space requirements doesn't seem too impressive? Am I missing something here? Is my calculation/assumption completely off? Maybe the solution here is more flexible? One alternative approach for many of these problems is to start with a perfect minimal hash function which hashes your key into a unique number [0, N) and the…

PTHash and other minimum perfect hash functions return an arbitrary value if the query key did not exist when building the MPHF, so they can be a lot smaller. B-field can identify query keys that don't exist in the set (with high probability?).

What I'm wondering is why the Kraken2 probabilistic hash table doesn't work. It uses 32 bits per element in an open addressing hash table. For 1 billion k-mers and 19 bits for the value, 32 - 19 = 13 bits of the key hash can be stored alongside the value, helping disambiguate hash collisions. If the load factor is 1.25x, then that's 4 * 10^9 * 1.25 = 5GB total, better than ~7GB. Also, this is only one cache miss (+ linear probing that can be SIMD accelerated) per lookup.

Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)

#26

Post by [deleted] »

judofyr wrote: post #17

Very interesting and I'll have to read more to understand how it fully works, but _initially_ the space requirements doesn't seem too impressive? Am I missing something here? Is my calculation/assumption completely off? Maybe the solution here is more flexible? One alternative approach for many of these problems is to start with a perfect minimal hash function which hashes your key into a unique number [0, N) and the…

[deleted]

Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)

#27

Post by ricardobeat »

judofyr wrote: post #17

Very interesting and I'll have to read more to understand how it fully works, but _initially_ the space requirements doesn't seem too impressive? Am I missing something here? Is my calculation/assumption completely off? Maybe the solution here is more flexible? One alternative approach for many of these problems is to start with a perfect minimal hash function which hashes your key into a unique number [0, N) and the…

One huge downside of your suggested approach is that adding a single entry requires rebuilding the entire hash.

Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)

#28

Post by foota »

boyd wrote: post #19
foota wrote: post #16

Earlier quoted context omitted.

Yes, that makes sense. Ooc, what do you think about the comparison to posting lists (aka bitmap indexes). Some searching shows ML folks are also interested in compressing KV caches for models, so if your technique is applicable there you can probably find infinite funding :P

So a bitmap index requires a bit per unique value IIRC (plus the key and some amount of overhead). So for ~32 unique values you're already at 4 bytes, 40 bytes per key-value pair for 320 values, etc. In comparison, a B-field will let you store 32 distinct values at ~3.4 bytes (27 bits) per key-value pair at a 0.1% FP rate.

Yes, I'm not claiming that they're going to perform as well, just that they're sort of similar in the space of problems.

There's different techniques used for compressing them, mostly around sorting the keys and e.g., run length encoding the values.

Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)

#29

Post by boyd »

c0deb0t wrote: post #25
judofyr wrote: post #17

Very interesting and I'll have to read more to understand how it fully works, but _initially_ the space requirements doesn't seem too impressive? Am I missing something here? Is my calculation/assumption completely off? Maybe the solution here is more flexible? One alternative approach for many of these problems is to start with a perfect minimal hash function which hashes your key into a unique number [0, N) and the…

PTHash and other minimum perfect hash functions return an arbitrary value if the query key did not exist when building the MPHF, so they can be a lot smaller. B-field can identify query keys that don't exist in the set (with high probability?). What I'm wondering is why the Kraken2 probabilistic hash table doesn't work. It uses 32 bits per element in an open addressing hash table. For 1 billion k-mers and 19 bits for…

> PTHash and other minimum perfect hash functions return an arbitrary value if the query key did not exist when building the MPHF, so they can be a lot smaller. B-field can identify query keys that don't exist in the set (with high probability?).

Yes, exactly.

> What I'm wondering is why the Kraken2 probabilistic hash table doesn't work.

I just skimmed the paper again (has been a while since a close reading), but my refreshed understanding is:

* Like the B-field, there are also false positives.

* When multiple hashed keys (k-mers) collide in the Kraken2 hash table, it has to store a "reduced" value for those key-value pairs. While there's an elegant solution for this issue for the problem of taxonomic classification (lowest common ancestor), it still results in a loss of specificity. There's a similar issue with "indeterminate" results in the B-field, but this rate can be reduced to ~0 with secondary arrays.

* The original Kraken2 paper describes using 17 bits for taxonomic IDs (~131K unique values). I don't know how many tax IDs current Kraken2 DB builds use offhand, but the error rate climbs significantly as you use additional bits for the value vs. key (e.g., to represent >=2^20 values, see Fig S4). I don't have a good sense for the performance and other engineering tradeoffs of just extending the hash code >32 bits. I also don't know what the data structure overhead is beyond those >32 bits/pair.

So, for a metagenomics classifier specifically, some subtle tradeoffs but honestly database quality and the classification algorithm likely matters a lot more than the marginal FP rates with either data structure -- we just happen to have come to this solution.

For other applications, my sense is a B-field is generally going to be much more flexible (e.g., supporting arbitrary keys vs. a specific fixed-length encoding) but of course it depends on the specifics.

Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)

#30

Post by esafak »

neutrinobro wrote: post #14

Ughh...the term B-field already has a very strong association with magnetic fields. I'm sure it sounded like a good name given the context, but these types of name-collisions generally makes searching for a specific topic more and more painful each year.

Old terms age out too, so it's not that bad. In the context of ML, for example, "generative models" meant something else twenty years ago. Nobody who's got into ML recently would even know what the old meaning is.
Post reply on HN