Comments (4)
With TBFs it should be possible by doing bitwise OR on the levels, just like you surmise.
With MTCFs Union should also be possible. The key operation if iterating over an MTCF, performing the permutations in reverse, to reconstruct as many bits of the original key as possible.
from libfilter.
Even though it sounds nice, I would consider internal threading as an anti-feature. Threads don't scale modern applications use a task-based method for concurrency. That said, creating a library that can be acted upon in a concurrent fashion is very useful. But the mechanism shouldn't be threads. That should be up to the user. It would feel like jab from the side if a library spawns threads internally and I'm already running a thread pool that optimally pins its threads to cores.
For example, our use case of building a telemetry engine over structured data involves hundreds of filters being created and queried in parallel. The bottleneck is not making insertion or querying faster of each single filter instance. Given this embarrassingly parallel setup, much more important to us is a merge operation, so that we can roll up multiple filters—LSM-style. If this would be possible with Taffy filters, then you'd solve the number one challenge with tree-structured hierarchical filter structures, which is provisioning the size of the non-leaf instances.
from libfilter.
Thanks for your thoughts!
Taffy cuckoo filters do support a Union
operation - is that not what you're looking for?
from libfilter.
Taffy cuckoo filters do support a
Union
operation - is that not what you're looking for?
That's great, I wasn't aware of it. Looking at the implementation, it seems also that there are no strict requirements in terms of sizing, as it would be the case for Bloom filters.
Mechanically, TBFs should support union as well by performing it piece-wise, no? I would only be worried about the FP-rate getting out of control due to oversubscribing of bits in each component that would otherwise be prevented by "organic" growth.
And MTCFs? Would it be possible to support Union also? Or are the subtables making this impossible?
from libfilter.
Related Issues (20)
- Submit to conan.io
- Ensure binary compatibility between Java and C filters
- Rust bindings
- Sort coupled (aka static) filter before peeling
- SIMD for cuckoo filters
- SIMD for peeling filters
- API documentation
- In Java XorFilter, migrate from arrays of structs to structs of arrays
- Support Union and Intersection for more filter types
- serialization and cross language/platform support HOT 7
- Benchmark for different filters HOT 3
- split block bloom filters implementation HOT 1
- Save the filter to SSD
- Java Taffy Block Filter bug
- _mm256_testc_si256 performance is bad HOT 11
- [Java] Block filter has high fpp HOT 1
- Rename XorFilter to StaticFilter in Java
- Submit to PyPI HOT 1
- Submit to pkg.go.dev
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from libfilter.