search

tomarrell / rust-elias-fano

Elias-Fano encoding implementation in Rust
MIT License
29 stars 5 forks source link

Skip to a specific value #4

Open fulmicoton opened 6 years ago

fulmicoton commented 6 years ago

Recently Elias Fano has become more popular to represent posting lists in search engine.

In order to intersect two positng lists efficiently, it is then required to have an efficient implementation of skipping to a specific document.

In tantivy, the interface is as follows.

One of the main benefits of Elias Fano is that it makes it easy to skip rapidly by counting zeroes and ones in the unary encoded high bits bit sequence.

tomarrell commented 6 years ago

Hi, thanks for the issues.

Just so I'm clear on what your requirement for this one is, you would like to given a particular value, skip the internal iterator to the position in the struct which is equal to or greater than the provided value?

If that's the case, I'll get to work on the implementation.

Thanks!

fulmicoton commented 6 years ago

That's the use case yes... Just to be clear I will not be able use your crate either way. I had plans to try using Elias-Fano in tantivy to represent positions, but that probably won't happen any time soon. I believe skipping is a very common requirement for elias fano clients however.

tomarrell commented 6 years ago

No worries, I'm glad to just build out the core functionality for anyone in the future that might find it useful.