RoaringBitmap / RoaringBitmap/roaring-rs

Optimization: Reduce container search time complexity

Open
#149 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
957
Forks
119
Avg merge
3d 3h
Merged PRs (30d)
1

Description

let B1, B2 = some roaring bitmaps
let N1 = number of containers in B1
let N2 = number of containers in B2

Currently binary operations such as B1 | B2 have an N1 * log(N2) container lookups.

  1. For commutative & (!assignment) ops: We can flip B1 for B2 when N1 > N2.
    • In other words: Whenever it is possible to flip the order: let the log search be over the larger collection
  2. Given that containers are sorted. While iterating over containers in B1, searching for containers in B2:
    • If a container is found at iteration I: The idx at iteration I+1 will be strictly greater than idx at I
    • If a container is not found at iteration I: The idx at iteration I+1 will be greater than or equal to the insertion point at I
    • In either case, we can logarithmically reduce the search space for every subsequent iteration, so it becomes log(log(N))
  • For commutative & !assignment ops time complexity becomes: min(N1, N2) * log(log(max(N1, N2)))
  • For ops that are (!commutative) | assignment: time complexity becomes: N1 * log(log(N2))
  • Space complexity remains O(1)

Please check my math. 🙂

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Inspect the binary operation implementations and the sorted-container lookup logic described in the issue. Check whether commutative operations can safely swap operands and whether subsequent searches can narrow their bounds; done means validating the proposed complexity improvements while preserving O(1) space.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.