What is a bitset (bitmap)?

A bitset, also called a bitmap, represents membership in a collection using a single bit per possible item, packed tightly together in memory, and it’s a far more compact alternative to a hash set, covered elsewhere in this glossary, whenever the collection’s items can be identified by small, dense numeric positions the way vectors in an HNSW index typically are.

How does a bitset actually manage to represent an entire collection using just individual bits?

A bitset reserves one single bit of memory for every possible item a collection could contain, setting that bit to 1 if the item is present in the collection and leaving it as 0 if it isn’t, which means checking whether a specific item is present just means looking at that one specific bit directly. Because a bit is the smallest possible unit of memory a computer can address, packing membership information down to a single bit per item makes a bitset extraordinarily compact compared to storing full entries the way a hash set, covered elsewhere in this glossary, typically does, provided the collection’s possible items correspond to small, predictable numeric positions rather than arbitrary, spread-out values.

Why is HNSW’s own vector data specifically well-suited to this bitset approach?

Vectors stored inside an HNSW index are typically assigned dense, sequential internal positions as they’re inserted, meaning the full set of vectors corresponds naturally to a compact range of small numbers starting from zero, exactly the situation a bitset is built to handle efficiently. This makes a bitset a natural fit for tracking which vectors have already been visited during a single search, covered elsewhere in this glossary as a task otherwise handled by a hash set, since the search process can simply check or set the bit corresponding to a vector‘s internal position directly, without needing a hash set’s more general-purpose but comparatively heavier hashing mechanism.

Why would an implementation choose a bitset over a hash set for this exact same visited-tracking task, given that both can answer the same question?

A bitset’s fixed, predictable memory layout, one bit per possible position packed tightly together, tends to use meaningfully less memory than a hash set for this specific use case, and also plays more favorably with a computer’s memory caching behavior, covered in this site’s coverage of memory layout for performance, since checking or setting a nearby bit tends to be cheaper than a hash set’s more scattered access pattern. The trade-off is that a bitset only works efficiently when the range of possible items is known in advance and reasonably compact, which is exactly true for HNSW‘s internal vector positions but wouldn’t hold for a more general, unpredictable set of arbitrary keys, which is precisely the situation a hash set remains better suited for instead.

A bitset’s compact, position-based representation is a natural, more memory-efficient alternative to a hash set specifically because HNSW’s internal vector positions are dense and predictable rather than arbitrary. From here, the pages on hash set and on array round out the picture of the different structures a real implementation might choose between for this same underlying tracking need.