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

11–20 of 39 posts

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

#11

Post by boyd »

danking00 wrote: post #2

I think it might help readers to include a narrative about an example application. Perhaps I’m in the minority but I tend to think of Bloom filters as a way to reliably know something isn’t in a set (e.g. so as to not run an expensive disk read). This data structure seems to view them the dual way: “this is maybe the right value for this key”. I’ve seen that view work for visualizations like approximate CDFs and medi…

Ah, we need to clarify the language! The B-field will always return the correct value for an inserted key.

False positives are only returned for keys that have not been inserted. This is akin to a Bloom filter falsely returning that a key is in the set).

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

#12

Post by boyd »

ComputerGuru wrote: post #4

Curious idea. So it’s for cases where you have any key but associated with one of only (preferably few) discrete values. I.E. your url example is great with url as a key but subpar if url were to be the value (padded to length n with trailing nulls encoded as a fixed width int array)? With its interesting set of guarantees, I can’t see a case where you could use this unless you are 100% positive all keys have previou…

> So it’s for cases where you have any key but associated with one of only (preferably few) discrete values

We use it for a case with ~million unique values, but it's certainly more space efficient for cases where you have tens, hundreds, or thousands of values. The "Space Requirements" section has a few examples: https://github.com/onecodex/rust-bfield?tab=readme-ov-file#s... (e.g., you can store a key-value pair with 32 distinct values in ~27 bits of space at a 0.1% false positive rate).

> all the docs say “designed for in-memory lookups”

We use mmap for persistence as our use case is largely a build-once, read many times one. As a practical matter, the data structure involves lots of random access, so is better suited to in-memory use from a speed POV.

> fyi, you use temp::temp_file() but never actually use the result, instead using the hard-coded /tmp path

Thank you, have opened an issue and we'll fix it!

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

#13

Post by boyd »

alexbowe wrote: post #3

Interesting read, thanks for sharing! If you have some benchmark results, it'd be great to see how it compares to traditional data structures in practice, for different datasets and varying k-mer lengths

Thank you! The "Space Requirements" section in the README has a few examples, and your comment has made me realize our (micro-)benchmark link in the README is broken.

We'll get that fixed and maybe find the time to do a larger post with some benchmarks on both space/time tradeoffs and overall performance vs. other data structures.

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

#14

Post by neutrinobro »

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.

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

#15

Post by dpc_01234 »

boyd wrote: post #11
danking00 wrote: post #2

I think it might help readers to include a narrative about an example application. Perhaps I’m in the minority but I tend to think of Bloom filters as a way to reliably know something isn’t in a set (e.g. so as to not run an expensive disk read). This data structure seems to view them the dual way: “this is maybe the right value for this key”. I’ve seen that view work for visualizations like approximate CDFs and medi…

Ah, we need to clarify the language! The B-field will always return the correct value for an inserted key. False positives are only returned for keys that have not been inserted. This is akin to a Bloom filter falsely returning that a key is in the set).

I second that "The B-field will always return the correct or Indeterminate value for an inserted key." before listing classes of errors would clarify it by a lot.

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

#16

Post by foota »

boyd wrote: post #9
foota wrote: post #6

Earlier quoted context omitted.

It seems like this would be most suitable for a system aggregating data. As long as you aggregate enough data points that the error averages out, it wouldn't be an issue. I guess another use case could be as any kind of "hint" where you need to do an authoritative lookup regardless of the filter lookup. E.g., the file might be on this host, but you'll need to reach the host and check for the file either way, so if yo…

I think those are both good examples of where you can manage the cost of a false positive. In genomics, we're using this to map a DNA substring (or "k-mer") to a value. We can tolerate a very low error rate for those individual substrings, especially since any erroneous values will be random (vs. having the same or correlated values). So, with some simple threshold-based filtering, our false positive problem goes awa…

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

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

#17

Post by judofyr »

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 then have a packed array of size N where each element is of a fixed byte size. To look up the value you first use the hash function to get an index, and then you look up in the packed array. There's also no error rate here: This is exact.

PTHash (https://arxiv.org/abs/2104.10402) needs roughly ~4 bits per element to create a perfect minimal hash function.

> Store 1 billion web URLs and assign each of them one of a small number of categories values (n=8) in 2.22Gb (params include ν=8, κ=1, =0.1%; 19 bits per element)

Assuming that "n=8" here means "8 bits" we need 1GB (8 bits * billion) to represent all of the values, and then 500 MB for the hash function (4 bits * billion).

I also don't quite understand what "2.22Gb" here refers to. 19 bits * billion = 2.357 SI-giga bytes = 19 SI-giga bits = 2.212 gibi bytes.

> Store 1 billion DNA or RNA k-mers ("ACGTA...") and associate them with any of the ~500k bacterial IDs current described by NCBI in 6.93Gb (ν=62, κ=4, =0.1%; 59 bits per element)

"~500k bacterial ID" can be represented with 19 bits. 1 billion of these take ~2.3GB, and then we have the additional 500MB for the perfect hash function.

Another data structure which is even more fine-tuned for this problem space is Bumped Ribbon Retrieval (https://arxiv.org/abs/2109.01892) where they have EDIT: Aha! One thing I forgot about: The alternatives I mentioned above all have a construction cost. I've been playing with them in the 100k-1M range and they've all been pretty instant (<1s), but I don't have any experience in the billion range. Maybe it's too slow there?

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

#18

Post by pkhuong »

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|r, or even |S|(r + 1.23) bits. It should also be faster to evaluate than `r` bloom filter lookups for large datasets.

I think the main advantage of the bloom filter (or compressed bitmap) approach is it can be updated incrementally. MWHC-style representations are better suited to build once / read many workloads.

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

#19

Post by boyd »

foota wrote: post #16
boyd wrote: post #9

Earlier quoted context omitted.

I think those are both good examples of where you can manage the cost of a false positive. In genomics, we're using this to map a DNA substring (or "k-mer") to a value. We can tolerate a very low error rate for those individual substrings, especially since any erroneous values will be random (vs. having the same or correlated values). So, with some simple threshold-based filtering, our false positive problem goes awa…

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.

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

#20

Post by boyd »

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 elements to "1", another million to "2", etc.

I'm not especially current (or fluent!) in that literature though, so would love pointers to anything that doesn't have the above constraints.

Post reply on HN