mikemccand opened a new issue, #16780:
URL: https://github.com/apache/lucene/issues/16780
### Description
I recently learned about binary fuse filters, which do the same thing as
bloom filters ("does the set contain X? ==> maybe or no" at a tunable
false-positive (maybe when it was really a no) rate), but more compactly and
less lookup cost (cache friendly locality, and maybe fewer memory accesses).
The big tradeoff is you cannot incrementally add to the set, i.e. binary
fuse filters are not an "online data structure": you must know the full set up
front, do the construction, and not change them. But this is a perfect match
for Lucene's write-once design!
It seems like we should cutover e.g. `BloomFilteringPostingsFormat` wrapper
(and change the name, sigh, naming is the hardest part, but Claude is pretty
good at it).
[Claude Opus 5.5 Medium does a succinct job comparing
them](https://claude.ai/share/92cde481-3edf-4eef-b192-0f4d2fa5de4b).
Daniel Lemire (creator/tester/publicizer of so many super fast low level
algorithms) has a [talk about binary fuse filters on
YouTube](https://youtu.be/UcbR7c4nyLU).
There is at least [one Apache licensed pure java
implementation](https://github.com/FastFilter/fastfilter_java), though probably
Claude could just bang one out from scratch in twelve seconds.
I don't have time to work on this! Just opening it in case anyone is
looking for a juicy low hanging fruit optimization dev challenge...
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
