Roaring Bitmap: How the Internet Manages Billions of User Tags

A user-tagging system sounds simple at first. Each user can have labels such as sports_fan, premium_customer, mobile_user, or recent_buyer. A marketing team may then ask questions like:

• Which users are both premium customers and sports fans?
• Which users are interested in travel but have not purchased recently?
• Which users belong to at least one of several target audiences?
• Which users match one group while being excluded from another?

The difficulty appears when the system contains millions or billions of user-tag relationships. A straightforward collection of sets can become expensive in memory and slow during combination queries. Roaring Bitmap is a data structure designed for this kind of problem: storing large collections of integer identifiers while making set operations such as union, intersection, and difference efficient.

This article explains the core idea behind Roaring Bitmap, how its containers represent data, how tag-combination queries work, and why the structure is useful in a marketing segmentation scenario.

The user-tagging problem​

Suppose every user has a numeric identifier. Instead of storing a long string for every relationship, the system can represent a tag as a set of user IDs.

For example:

sports_fan = {2, 5, 8, 13, 21}
premium     = {5, 8, 34, 55}
mobile_user = {1, 5, 13, 34}

A query for users who are both sports fans and premium customers is an intersection:

sports_fan ∩ premium = {5, 8}

A query for users who are sports fans or premium customers is a union:

sports_fan ∪ premium = {2, 5, 8, 13, 21, 34, 55}

A query for sports fans who are not premium customers is a difference:

sports_fan − premium = {2, 13, 21}

These operations are naturally modeled as set operations. The challenge is representing the sets so that they use reasonable memory and can be combined quickly.

Why ordinary representations can become expensive​

One possible representation is a bitset. If user ID i is present in a tag, bit i is set to one. This makes set operations very direct: intersection becomes a bitwise AND, union becomes a bitwise OR, and exclusion becomes a bitwise AND with the complement of another bitmap.

The disadvantage is that a bitset reserves space across the entire identifier range. If the largest possible user ID is extremely large but a particular tag belongs to only a small number of users, a full bitset may waste a great deal of memory.

Consider a tag associated with users near IDs 10, 20, and 30 while the global ID space extends to billions. A full bitmap must still account for the positions between those IDs. The representation is simple, but its size is related to the universe of possible IDs rather than the number and distribution of actual members.

Another option is a sorted array of user IDs:

[2, 5, 8, 13, 21]

This is compact when a tag contains relatively few users. However, combining two sorted arrays requires scanning their values. That can be efficient for small sets, but it may become costly when a tag contains a very large population or when many combinations are evaluated repeatedly.

Roaring Bitmap combines the useful properties of both approaches. It stores integer values in partitions and chooses a suitable representation for the values inside each partition.

The central idea: divide IDs into chunks​

Roaring Bitmap is commonly described using a 32-bit integer space divided into two parts. The high portion identifies a chunk, while the low portion identifies a position inside that chunk.

Conceptually, an integer can be split like this:

user ID = high part + low part

For the commonly used 32-bit layout, the high 16 bits select a chunk and the low 16 bits represent a position within that chunk. Each chunk therefore covers a fixed range of possible IDs. The bitmap maintains a mapping from high parts to containers, and each container stores the low parts that are present.

This arrangement avoids allocating a full bitmap for the complete identifier universe. Empty chunks need no container at all. A tag containing users spread across a few regions of the ID space stores only those regions. A tag with many users in one region can use a dense representation for that region.

For example, imagine that users are grouped into two chunks:

Chunk A: user IDs 0 through 65,535
Chunk B: user IDs 65,536 through 131,071

If a tag contains several IDs in Chunk A and no IDs in Chunk B, only Chunk A needs a container. If the tag later gains members in Chunk B, a second container can be added. The top-level structure remains sparse when the data is sparse.

The exact internal layout and implementation details can vary by library, but the important design principle is stable: partition the integer universe and select a representation separately for each partition.

What is a container?​

A container stores the low portions of IDs belonging to one high-partition. Roaring Bitmap implementations generally use multiple container forms, with the choice depending on the local density and pattern of values.

Array containers​

An array container stores the present low values in a sorted array. For example:

[3, 18, 44, 900]

This is suitable when the chunk contains relatively few values. It avoids storing bits for positions that are not present, and sorted values support efficient combination operations.

Array containers are especially useful for sparse chunks. If only a small number of users fall into a particular ID range, the array can be much smaller than a fixed-size bitmap for that range. The trade-off is that operations on arrays require scanning or binary search, which is acceptable when the array is small.

A typical threshold might be around 4,096 values. Below that, an array is more compact than a bitmap. Above that, a bitmap becomes more efficient. The exact threshold depends on the implementation and the operations being performed.

Bitmap containers​

A bitmap container stores a bit for every possible low value in the chunk. A set bit means that the corresponding low value is present.

Bitmap containers are useful when a chunk is dense. Once many positions are present, listing every value individually may require more space and more work than storing a dense bit representation. Bitwise operations are also natural for bitmap containers:

• AND computes a local intersection.
• OR computes a local union.
• AND NOT computes a local difference.

The operation is performed within matching chunks, so a large global operation can be broken into smaller local operations. For a 16-bit chunk, a bitmap container uses exactly 8 kilobytes (65,536 bits), regardless of how many values are actually present. This fixed size is acceptable when the chunk is dense, but wasteful when it is sparse.

Run containers​

Some implementations also support run containers. A run represents a consecutive interval of values, such as:

100 through 150

If a tag contains long consecutive ranges of IDs, storing the start and length of each range can be compact. Run-oriented storage is useful when the data has that particular pattern. For example, if a tag applies to all users in a particular ID range, a run container can represent that with just two numbers instead of thousands of individual entries.

The general lesson is that no single representation is ideal for every chunk. A sparse chunk, a dense chunk, and a chunk containing long runs have different characteristics. Roaring Bitmap adapts locally rather than forcing the entire set to use one global format.

Why local adaptation matters​

A user-tag set is rarely uniform. One tag might apply to almost every user, another might apply to a small experimental audience, and a third might contain users added in blocks. Their distributions can differ dramatically even though all of them are sets of integers.

A global representation would have to choose one compromise for all tags. A partitioned representation can make independent choices:

Tag: travel_interest
- Chunk 10: array container (sparse)
- Chunk 11: bitmap container (dense)
- Chunk 12: run-oriented container (consecutive)

This does not mean every implementation will expose exactly these labels or choices, but it illustrates the design. Each part of the data can be represented according to its local density and structure.

This flexibility is one reason Roaring Bitmap is attractive for large collections of integer IDs. It is not merely a compressed bitset and not merely a sorted list. It is a hybrid structure that switches among compact forms while preserving efficient set operations.

Consider the memory implications. A tag with 100 million users spread uniformly across a 32-bit space might use:

• Full bitset: 512 megabytes (one bit per possible ID)
• Sorted array: 400 megabytes (4 bytes per user ID)
• Roaring Bitmap: potentially 50-100 megabytes (depending on distribution)

The Roaring Bitmap saves space because it does not allocate storage for empty regions and uses the most efficient representation for each populated region.

Combining tags with set operations​

A tag can be viewed as a bitmap containing the IDs of all users assigned that tag. A query engine can translate logical conditions into set operations.

AND: users matching every condition​

The logical expression:

premium AND sports_fan

becomes an intersection:

premium ∩ sports_fan

Only IDs present in both bitmaps remain. At the container level, the system compares containers with the same high-partition key. If a key exists in only one operand, it cannot contribute to the intersection. If it exists in both, the corresponding container representations are combined.

For an intersection, the smaller or more selective sets are often valuable starting points because the result cannot contain more elements than the smallest input. A practical query planner may therefore consider set sizes or estimated cardinalities when deciding how to evaluate a complex expression.

For example, if premium has 5 million users and sports_fan has 500,000 users, starting with sports_fan and filtering to only those who are also premium is more efficient than the reverse.

OR: users matching at least one condition​

The logical expression:

sports_fan OR travel_interest

becomes a union:

sports_fan ∪ travel_interest

Every ID present in either input is included. Matching chunks are merged, while chunks present in only one operand can be copied into the result.

Union is useful for building a broad audience, such as users interested in sports or travel. It can also combine multiple campaign eligibility groups into one delivery set. The result of a union is typically larger than either input, so memory usage can grow accordingly.

AND NOT: include one group and exclude another​

The expression:

premium AND NOT recent_buyer

can be represented as:

premium − recent_buyer

The system starts with the premium set and removes IDs found in the recent-buyer set. This is useful for suppression lists, such as excluding users who have already received an offer or purchased the promoted product.

The result size depends on the overlap. If there is little overlap between the two sets, the result is nearly as large as the first set. If there is significant overlap, the result is much smaller.

More complex expressions​

Real targeting rules often combine several operators:

(premium AND sports_fan) AND NOT recent_buyer

A reasonable evaluation sequence is:

1. Intersect premium with sports_fan.
2. Remove the IDs in recent_buyer.
3. Use the remaining bitmap as the target audience.

The order can matter for performance. Intermediate results that become small early may reduce later work. The best order depends on the sizes and distributions of the participating sets, so a production system may use metadata such as estimated cardinality to guide evaluation.

Another possible order might be:

1. Remove recent_buyer from premium.
2. Intersect the result with sports_fan.

Which order is better depends on the actual sizes. If recent_buyer is very large, removing it first might create a smaller intermediate result. If sports_fan is very selective, intersecting it first might be better. A query optimizer would measure or estimate these sizes to make the decision.

A marketing segmentation case study​

Consider a marketing platform that assigns tags to users. The tags might represent product preferences, engagement states, subscription levels, or campaign history. The marketing team wants to create an audience with a rule such as:

interested_in_travel AND premium_customer AND NOT contacted_recently

The data model can store one bitmap per tag:

interested_in_travel: 2.5 million users
premium_customer: 8 million users
contacted_recently: 1.2 million users

The audience computation is then conceptually:

interested_in_travel
∩ premium_customer
− contacted_recently

A reasonable evaluation order might be:

1. Intersect interested_in_travel (2.5M) with premium_customer (8M). Result: approximately 1.5M users (assuming some overlap).
2. Remove contacted_recently (1.2M) from the result. Final result: approximately 0.5M users.

The resulting bitmap contains the user IDs that satisfy the campaign rule. A downstream process can iterate over those IDs and send them to an advertising, messaging, or analytics workflow.

The important point is that the segmentation rule is expressed as operations on sets rather than as a scan through every user record. This can be particularly useful when the system must evaluate many combinations of existing tags. Instead of querying a database for each combination, the system can perform fast bitmap operations in memory.

A marketing case study may also involve comparing audiences. For example, a team might want to measure the overlap between two campaigns:

campaign_A ∩ campaign_B

Or it may want to find users eligible for one campaign but not another:

campaign_A − campaign_B

These are the same fundamental bitmap operations, applied to a different business question.

Another practical scenario is audience expansion. A marketing team might want to find users similar to an existing audience:

base_audience ∩ (interest_A OR interest_B OR interest_C)

This finds users in the base audience who have at least one of three interests. The union of the three interests is computed first, then intersected with the base audience.

Complexity and performance considerations​

The exact complexity depends on the implementation, the container types, the number of nonempty chunks, and the distribution of values. It is therefore better to describe the behavior structurally rather than promise one universal runtime.

At a high level, an operation must inspect relevant chunks and combine their containers. Empty regions do not need to be materialized. Sparse chunks can be processed as arrays, while dense chunks can use word-level bitmap operations. This allows the work to reflect the stored data instead of always scanning the entire possible integer universe.

Memory usage also depends on the data. Sparse regions can use compact arrays, dense regions can use bitmap containers, and consecutive regions may benefit from run-oriented storage. There is overhead for the top-level mapping and container metadata, so the structure is not automatically optimal for every tiny set.

For a typical intersection operation:

• If both sets have nonempty chunks at the same high-partition key, those chunks are combined.
• If a key exists in only one set, it is skipped (it cannot contribute to an intersection).
• The work is proportional to the number of nonempty chunks in the smaller set, not the total ID space.

For a union operation:

• All nonempty chunks from both sets are included in the result.
• Chunks present in only one set are copied.
• Chunks present in both sets are merged.
• The work is proportional to the total number of distinct nonempty chunks.

For a difference operation:

• Chunks present only in the first set are copied.
• Chunks present in both sets are processed to remove elements from the second set.
• Chunks present only in the second set are ignored.

The practical performance questions are:

• How many distinct IDs are present?
• How many chunks are nonempty?
• Are the chunks sparse or dense?
• Do the values contain long runs?
• How many tag combinations are evaluated?
• Is the result kept in memory or materialized elsewhere?
• Are the same tags combined repeatedly, allowing caching of intermediate results?

These factors matter more than simply saying that a bitmap is "fast." A good engineering decision measures representative workloads rather than relying only on the data structure's name.

Design considerations for a tagging service​

Use stable numeric identifiers​

Roaring Bitmap is built around integer values. A tagging service therefore needs a reliable mapping from application-level user identities to numeric IDs. The mapping should be stable enough that a user's identifier does not change unexpectedly, because changing IDs would require rewriting bitmap membership.

Many systems use a database primary key as the numeric ID. This is stable by design. Other systems might use a hash of a user's email or username, which is also stable as long as the hash function does not change.

Separate tag metadata from membership data​

The name and description of a tag are ordinary application metadata. The bitmap stores membership. Keeping these concepts separate makes it easier to manage tag names, ownership, creation time, and business definitions without mixing them into the integer set representation.

For example, a tag record might look like:

Tag ID: 42
Name: "premium_customer"
Description: "Users with active premium subscriptions"
Created: 2024-01-15
Owner: "marketing_team"
Membership bitmap: <Roaring Bitmap>

The metadata can be updated without touching the bitmap. The bitmap can be updated without changing the metadata.

Plan update behavior​

A system should consider how often users are added to or removed from tags. Roaring Bitmap supports set updates, but the surrounding service still needs to decide how updates are persisted, synchronized, and made visible to queries. A design optimized only for batch construction may have different trade-offs from one receiving continuous membership changes.

For example, a system might:

• Rebuild tags nightly from source data (batch).
• Update tags in real-time as events occur (streaming).
• Use a hybrid approach with periodic rebuilds and incremental updates.

Each approach has different implications for consistency, latency, and resource usage.

Consider serialization and interoperability​

Large bitmaps may need to move between processes, be stored, or be cached. The selected library and storage format should support the required serialization behavior. Compatibility, versioning, and recovery are operational concerns in addition to the in-memory algorithm.

Roaring Bitmap libraries typically provide serialization methods. The serialized format is usually compact, often smaller than the in-memory representation. This makes it suitable for storage and transmission.

Keep query semantics explicit​

A tag may represent a current state, a historical event, or eligibility for a particular campaign. Bitmap operations are precise, but they cannot resolve ambiguous business definitions. Before implementing a query, clarify whether "recently contacted" means a current tag, a time window, or an event-derived audience.

For example:

• "contacted_recently" might mean "contacted in the last 7 days" (time-based).
• "contacted_recently" might mean "contacted in the current campaign" (campaign-based).
• "contacted_recently" might mean "contacted by any channel in the last 30 days" (aggregated).

The bitmap stores the result of that definition, but the definition itself must be clear and documented.

When Roaring Bitmap is a good fit​

Roaring Bitmap is a strong candidate when:

• The values are integer identifiers.
• The application performs frequent unions, intersections, and differences.
• Some sets are sparse while others are dense.
• The identifier universe is large enough that one full bitmap per set would be wasteful.
• The system benefits from keeping sets in memory or processing them in compact form.
• The sets are relatively static or updated in batch, rather than changing constantly.
• Multiple sets need to be combined in various ways.

It may be less suitable when:

• The data is not naturally represented by integer IDs.
• Each set is tiny and operations are rare.
• The primary requirement is a different query model such as arbitrary text search or complex relational filtering.
• Updates are extremely frequent and must be immediately visible.
• The system needs to support range queries or other operations beyond basic set algebra.

In those cases, another index or storage structure may be more appropriate.

Practical takeaways​

The most important ideas are straightforward:

1. Model each user tag as a set of numeric user IDs. This transforms the problem into set algebra, which is well-understood and efficient.

2. Translate AND, OR, and exclusion rules into intersection, union, and difference. Business logic becomes mathematical operations.

3. Partition the ID space so empty regions do not consume unnecessary storage. This is the key insight that makes Roaring Bitmap practical for large ID spaces.

4. Use different container forms for sparse, dense, or run-like regions. Adaptation to local data patterns improves both memory usage and speed.

5. Evaluate complex expressions in an order that limits unnecessary intermediate work. Query planning matters, especially when combining many sets.

6. Treat cardinality, update patterns, persistence, and query semantics as engineering concerns around the core structure. The algorithm is only part of the solution.

Roaring Bitmap is valuable because it aligns the representation with the operations that a tagging system needs. A marketing audience is fundamentally a set of users, and many marketing questions are fundamentally set expressions. By storing those sets in adaptive containers, a system can represent large audiences compactly and combine them without treating the entire user universe as one enormous undifferentiated bitmap.

The result is not a magic solution to every scaling problem. Data layout, identifier distribution, update frequency, query planning, and operational requirements still matter. But for large-scale integer sets and tag-combination queries, the container-based design offers a practical bridge between compact storage and efficient set algebra. When implemented well, it enables systems to manage billions of user tags while keeping memory usage reasonable and query performance fast.