Chunked integer sets: switch sparse arrays to dense bitmaps

Last updated: 4 Oct 20269 min read

tutorial

A chunked integer set splits each 16-bit alert ID into an eight-bit high chunk key and an eight-bit low offset. Sparse chunks store sorted low offsets; dense chunks store a 256-bit integer mask. When an array passes 32 entries it promotes to a mask, and when a mask falls to 16 entries it demotes to an array. The two thresholds create hysteresis, avoiding representation switches on every insert/delete near one cutoff. Exact membership checks either binary-search the array or test a mask bit. Intersection visits chunk keys present in both sets, combines local masks, and emits exact IDs. This is a small explanatory hybrid, not a compatible serialized bitmap format or a benchmarked production library. It omits run containers, SIMD operations, rank/select, and cardinality-wide metadata.

Operational case

The active set holds alert 47, 61, 83, and forty consecutive IDs starting at 512. A reviewed set holds 47, 129, 515, 516, and 517. Their intersection is 47, 515, 516, 517; the chunk for IDs 512 through 767 has promoted to a dense mask. A duplicate insertion changes nothing, and deleting an absent ID raises an error. During a long removal sequence, the dense chunk converts back to a sorted array only after its population reaches 16. That later threshold prevents a stream alternating around 32 from repeatedly allocating two different representations.

Working Python program

from bisect import bisect_left


class ChunkedAlertBitmap:
    CHUNK_WIDTH = 256
    PROMOTE_AT = 32
    DEMOTE_AT = 16

    def __init__(self):
        self.containers = {}
        self.counts = {}

    @staticmethod
    def _parts(alert_id):
        if not 0 <= alert_id < 65536:
            raise ValueError("alert ID outside 16-bit domain")
        return alert_id >> 8, alert_id & 255

    def add(self, alert_id):
        high, low = self._parts(alert_id)
        container = self.containers.setdefault(high, [])
        if isinstance(container, list):
            position = bisect_left(container, low)
            if position < len(container) and container[position] == low:
                return
            container.insert(position, low)
            self.counts[high] = len(container)
            if len(container) > self.PROMOTE_AT:
                self.containers[high] = sum(1 << item for item in container)
        elif not (container >> low) & 1:
            self.containers[high] = container | (1 << low)
            self.counts[high] += 1

    def remove(self, alert_id):
        high, low = self._parts(alert_id)
        if high not in self.containers:
            raise KeyError(alert_id)
        container = self.containers[high]
        if isinstance(container, list):
            position = bisect_left(container, low)
            if position == len(container) or container[position] != low:
                raise KeyError(alert_id)
            container.pop(position)
            self.counts[high] = len(container)
        else:
            if not (container >> low) & 1:
                raise KeyError(alert_id)
            container &= ~(1 << low)
            self.counts[high] -= 1
            if self.counts[high] <= self.DEMOTE_AT:
                self.containers[high] = [item for item in range(self.CHUNK_WIDTH)
                                         if (container >> item) & 1]
            else:
                self.containers[high] = container
        if self.counts[high] == 0:
            del self.counts[high]
            del self.containers[high]

    def contains(self, alert_id):
        high, low = self._parts(alert_id)
        container = self.containers.get(high, [])
        if isinstance(container, list):
            position = bisect_left(container, low)
            return position < len(container) and container[position] == low
        return bool((container >> low) & 1)

    @staticmethod
    def _mask(container):
        return sum(1 << item for item in container) if isinstance(container, list) else container

    def intersection(self, other):
        matches = []
        for high in sorted(self.containers.keys() & other.containers.keys()):
            common = self._mask(self.containers[high]) & self._mask(other.containers[high])
            while common:
                lowest = common & -common
                matches.append((high << 8) | (lowest.bit_length() - 1))
                common ^= lowest
        return matches

    def values(self):
        values = []
        for high in sorted(self.containers):
            container = self.containers[high]
            if isinstance(container, list):
                values.extend((high << 8) | low for low in container)
            else:
                bits = container
                while bits:
                    lowest = bits & -bits
                    values.append((high << 8) | (lowest.bit_length() - 1))
                    bits ^= lowest
        return values


active = ChunkedAlertBitmap()
reviewed = ChunkedAlertBitmap()
for alert_id in [47, 61, 83, *range(512, 552)]:
    active.add(alert_id)
for alert_id in [47, 129, 515, 516, 517]:
    reviewed.add(alert_id)
print("shared=", active.intersection(reviewed),
      " dense-chunk=", isinstance(active.containers[2], int), sep="")

Output

shared=[47, 515, 516, 517] dense-chunk=True

Time, space, and tradeoff

Let K be the number of common chunks, A the maximum sparse-array population, and R the number of intersection results. Sparse membership costs O(log A), but insertion/removal shifts O(A) list entries. Dense bit tests and updates work on one bounded 256-bit integer, treated as O(1) in this fixed-domain model. Intersection converts sparse common chunks to masks in O(KA), performs bounded-width bit operations, and emits R IDs; sorting chunk keys adds O(K log K). Stored data is O(N + D * 256) conceptual bits across N sparse entries and D dense chunks, plus Python dictionary, list, and integer overhead. No compression ratio is promised for Python objects.

Common Mistakes

Do not confuse this two-container model with a full bitmap file format.
Do not promote and demote at the same occupancy threshold.
Do not count duplicate insertions twice.
Do not return a chunk match before testing the low offset.

Connected lessons

Compare its storage and lookup contract with Elias–Fano: split sorted IDs into low parts and high bits, Gap-encoded postings: add checkpoints to bytewise seeks, Level-order unary degree tries: encode child runs as bits, then run the index audit and contract quiz.

Van Emde Boas trees: successor in a bounded integer universe adds a distinct structure contract to compare.

Run-length bitmaps: union, intersect, and subtract alert spans adds a related structure with a different operation boundary.

Bit-sliced indexes: filter and sum fixed-width sensor readings examines a related structure with a different operation boundary.

data structures

range-query-structures