Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

implement efficient set intersection + iteration for RLE bitsets #396

Open
lukevalenty opened this issue Oct 18, 2023 · 1 comment
Open
Labels
enhancement New feature or request

Comments

@lukevalenty
Copy link
Contributor

No description provided.

@lukevalenty lukevalenty added the enhancement New feature or request label Oct 18, 2023
@AshleyRoll
Copy link
Contributor

AshleyRoll commented Nov 2, 2023

I'll start tackling this issue next.

Plan is to build a variadic template that will take N rle_indexs and walk though the RLE data and apply bit-wise and operation. This means that we should be able to:

  • Take the maximal length of 0 bits from the N RLE streams
  • If no 0s are present, we take the minimal length of 1s
  • Then increment each of the RLE stream states by the decided number of bits and repeat

This should then give us a fairly efficient way to combine the RLE data streams into an overall intersection. And then I should be able to turn that into an efficient iteration for running callbacks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants