[deleted]
Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)
31–39 of 39 posts
Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)
#32There's another library unrelated to the data structure but is from the same field - an interval tree structure - Lapper[1][2]
Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)
#33IIRC with a bloom filter if returns false you can be sure it is not in the set but if it returns true it probably is in the set but might be a clash giving a false positive?
Is the same true with this data structure.
I guess you could mitigate this by storing an additionally hash or the original key in it’s entirety as the value?
Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)
#34Is somewhere out there a non-rust version, please?
Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)
#35Is somewhere out there a non-rust version, please?
As in, any other language at all..?
Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)
#36Earlier quoted context omitted.
... 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|)`.
I think we're somewhat talking past one another -- in any case, we'll add more in the README on minimal perfect hash functions and the differences. In short, you'd need to also have a data structure (e.g., a Bloom filter) for checking if the key is in your MPHF and then also a mapping of 1..n MPHF values to your actual values.
Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)
#37Earlier quoted context omitted.
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|)`.
I think we're somewhat talking past one another -- in any case, we'll add more in the README on minimal perfect hash functions and the differences. In short, you'd need to also have a data structure (e.g., a Bloom filter) for checking if the key is in your MPHF and then also a mapping of 1..n MPHF values to your actual values.
There's a classic solution to detecting most missing entries: make your value a pair of a signature and the actual value. m signature bits result in a 2^-m false match rate for keys not in the input map.
Again, the MWHC construction does not need to map the hashed keys to ranks, they can map to the values directly.
Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)
#38Ughh...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.
I don't think Maxwell's equations are going anywhere anytime soon.
Re: Show HN: B-field, a novel probabilistic key-value data structure (`rust-bfield`)
#39Curious 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 wi…
Sure, but I wouldn’t expect the api to force you to use an mmap when a slice of bytes would accomplish the same when unpersisted (and the user could choose to persist via a different mechanism if you have a .into() method that decays self into a Vec/Box/etc)
If I were to design this library, I would internally use an enum { Mapped(mmap), Direct(Box) } or better yet, delegate access and serialization/persistence to a trait so the type becomes BField where the impl trait provides as_slice() and load()/save().
This way you abstract over the OS internals, provide a pure implementation for testing or no_std, and probably improve your codegen a bit.