Show HN: High-Performance Wavelet Matrix for Python, Implemented in Rust

Posted by math-hiyoko 2 days ago

Counter91Comment10OpenOriginal

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!

Comments

Comment by koolala 2 days 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?

Comment by mrkeen 2 days 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.

Comment by yourdetect 1 day ago

Does this contain unsafe? Even the Linux kernel's Rust code have memory safety bugs. https://news.ycombinator.com/item?id=46309536

Comment by math-hiyoko 1 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.

Comment by simgt 1 day ago

> git clone https://github.com/math-hiyoko/wavelet-matrix.git && find wavelet-matrix -type f -name '*.rs' -exec grep 'unsafe' {} +

No.

Comment by kennykartman 1 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!

Comment by joshlk 1 day ago

What's a good reference to learn about Wavelet Matrices?

Comment by mrkeen 1 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.

Comment by atoav 1 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.

Comment by math-hiyoko 1 day 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.

Comment by heya1993 2 days ago

[flagged]