NVIDIA / NVIDIA/cuvs

[FEA] Roaring Bitmap support

Open
#1,972 3 comments 2 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

feature request
Dominant language
Cuda
Stars
854
Forks
236
Avg merge
3d 3h
Merged PRs (30d)
62

Description

Is your feature request related to a problem? Please describe.
Filtered vector search optimization

Describe the solution you'd like
Adding Roaring Bitmap Support directly to cuVS.

Describe alternatives you've considered
Using the existing bitset implementation

Additional context
Original Roaring Bitmap paper: https://arxiv.org/abs/1402.6407
Follow on paper that introduced run encoding: https://arxiv.org/abs/1603.06549

Summary

I'd like to propose contributing https://roaringbitmap.org/ support on Exa's behalf as an alternative filter representation for cuVS's prefiltered search APIs (for CAGRA, IVF-Flat, brute-force, etc).

Motivation

cuVS currently supports bitset_filter for prefiltered search, backed by a flat bit array. This works, but has two
limitations:

  1. Memory scaling. A flat bitset for N vectors requires N/8 bytes regardless of how many bits are set. At 10M vectors
    this is 1.2 MB; at 100M it's 12 MB; at 1B it's 120 MB. For sparse filters (e.g., 1% pass rate at 100M scale), a
    compressed representation could reduce this by 10-100x or even more.
  2. Cache pressure. During CAGRA graph traversal and IVF-Flat list scanning, filter checks access random positions
    in the bitset. When the bitset exceeds L1 cache (128 KB per SM on Blackwell), every check incurs an L2 round-trip
    (~200 cycles vs ~28 cycles for L1). Roaring's two-level structure (small key index + 8 KB containers) keeps the
    working set in L1.
  3. Interoperability. Roaring Bitmaps are the standard compressed bitmap format across the database and search
    ecosystem (Lucene, Elasticsearch, Apache Spark, ClickHouse, Redis, etc.). Accepting roaring filters directly avoids a decompress-to-bitset step on the ingestion path and allows for the copying of a tiny roaring bitmap filter to the GPU, potentially one per query vector.

I have already prototype some of the parts of this and it performs extremely well in specific cases, sparse data, clustered or multitenant indexes. It can also work very well in cases where we can presort our data so common filters are contigous so Roaring Bitmap containers store them using run encoding

I spoke with @cjnolet, Nathan Stephens, and Manas Singh earlier today. Filing this PR to kick off the discussion and will share more details next week

Contributor guide

Open the contributing guide

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

Start by reading cuVS's existing bitset_filter implementation and the prefiltered search APIs for CAGRA, IVF-Flat, and brute-force. Compare the proposed Roaring Bitmap representation and prototype claims against sparse-filter behavior; done should include an agreed integration design and validation across the named search paths.

Written by the indexing model from the issue text.

Assessment

Domain
performance, search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.