I built a Rust-powered Wavelet Matrix library for Python.
There were surprisingly few practical Wavelet Matrix implementations available for Python, so I implemented one with a focus on performance, usability, and typed APIs. It supports fast rank/select, top-k, quantile, range queries, and even dynamic updates.
Feedback welcome!
koolalaa day ago
Can a wavelet be used with SIMD 128bit operations? Or are they used with 4x4 Matrix operators? Are wavelets good for that kind of math?
mrkeena day ago
> Can a wavelet be used with SIMD 128bit operations?
Popcount works great in this context, but that only gives you linear speedups. Doing rank/select in O(1) instead of O(N) is a bigger win, and you get that by precomputing superblocks.
> Or are they used with 4x4 Matrix operators? Are wavelets good for that kind of math?
Nope, different kind of matrix. Just refers to a nicer packing of a wavelet tree with space wasted by bookkeeping pointers between tree nodes.
kennykartmana day ago
Thank you for sharing! It's great to have more wavelet libraries. I don't often use those, but when I do the choice is scarce. It's great to have another option!
yourdetecta day ago
Does this contain unsafe? Even the Linux kernel's Rust code have memory safety bugs. https://news.ycombinator.com/item?id=46309536
math-hiyokoopa day ago
No, the library itself does not use unsafe Rust at all. The Python bindings are built using PyO3, which internally uses unsafe (as required to interface with the CPython C API), but that is fully encapsulated within PyO3. The core data structure and algorithms remain purely safe Rust.
simgta day ago
> git clone https://github.com/math-hiyoko/wavelet-matrix.git && find wavelet-matrix -type f -name '*.rs' -exec grep 'unsafe' {} +
No.
joshlka day ago
What's a good reference to learn about Wavelet Matrices?
mrkeena day ago
Start with Wavelet trees (much more intuitive): https://www.alexbowe.com/wavelet-trees/
The matrix version is just an implementation detail to store the tree in a less tree-like shape so you don't need as many pointers.
atoava day ago
Looks good to me. Have you considered adding a really practical realworld example? As someone who loves looking at examples I like your small examples in the readme, but it still leaves me wondering a bit what I actually would use this library for.
Many people don't know what you would use wavelets for or where they really shine. I for example know wavelets are used in image compression algorithms but that's about it. I am curious where else this could be applied.
math-hiyokoop20 hours ago
Thanks for the feedback! You're right, just listing features doesn't make the use cases very clear. I'm planning to add more concrete, real-world examples to the README and examples to better show where wavelet matrices really shine.
heya19932 days ago
[flagged]