AdaBool: Adaptive Sparse Boolean Matrix Processing on GPU (SIGMOD 2027)

Background: Sparse Boolean Matrix Multiplication in Ad Filtering

In Tencent's advertising system, real-time targeting filtering requires matching online query conditions against tens of millions of static candidates. This core operation—finding candidates that satisfy a set of attributes—can be modeled as Sparse Boolean Matrix Multiplication (SpBMM) : a boolean matrix A (attributes × candidates) multiplied by a boolean query matrix Q (queries × attributes) yields a result matrix R (queries × candidates). Each row of A corresponds to an inverted list (posting list). The computation involves only logical AND/OR (bitwise operations), no floating-point arithmetic.

Problem: Memory-Bound Bottleneck and Power-Law Distribution

On GPUs, SpBMM is memory-bound : performance is limited by global memory bandwidth, access coalescing, and load balance across warps/thread blocks. Real-world data exhibits extreme power-law distributions. In the production AdsFilter dataset (100K rows × 10M columns, density 0.001%), row densities span 6 orders of magnitude —a few hot attributes link to hundreds of thousands of candidates while long-tail attributes link to only a few. A single fixed compression format (e.g., CSR offset arrays or bitmaps) cannot simultaneously serve sparse and dense regions efficiently:

Offset arrays (ARRAYn) skip zeros, ideal for sparse blocks, but waste space in dense blocks.

Bitmaps (BITSET) are space-efficient for dense blocks but allocate space for zeros and waste scan bandwidth in sparse blocks.

Moreover, mixing formats within a warp causes severe warp divergence and unaligned memory accesses. Online query densities also vary widely (0.1% to 10%+), so a single traversal strategy cannot adapt to both sparse and dense queries.

AdaBool Design: Adaptive Block-Level Encoding

Fine-Grained Element Blocks

The matrix is partitioned along columns into fixed-size windows of W = 256 columns. Each row is split into Element Blocks ; only windows containing at least one non-zero create a block (empty windows are skipped). Within a block, column indices share a high-order base address, so relative offsets need only 8 bits .

Two Encoding Formats per Block

Based on the number of non-zeros nnz in a block, AdaBool chooses:

ARRAYn (offset array) for sparse blocks: a header (base column) + fixed-length offset array. To guarantee 32-bit aligned loads, array lengths are multiples of 4: ARRAY0 (nnz=1, header only), ARRAY4, ARRAY8, ARRAY16, ARRAY32. Offsets are stored as 8-bit values; full column = base | offset.

BITSET for dense blocks: header + 256-bit bitmap (1 bit per column).

The switch threshold is nnz > 32 → BITSET. This threshold derives from space-cost equality ( 8*nnz + 32 = 256 + 32) and 32-bit alignment constraints (W=256 is a power-of-two divisor of 32). Blocks of the same type are grouped into contiguous memory pools (ARRAY0 pool, ARRAY4 pool, BITSET pool, etc.) for coalesced GPU access.

GPU Execution Model

AdaBool employs three key execution techniques:

Static Pre-Indexing : The large, reusable right-hand matrix (candidate-index) is built offline into the adaptive AdaBool index; build cost is amortized over millions of online queries. The left-hand query matrix and output matrix use simple bitmaps, avoiding online format conversion.

Encoding-Aware Kernels : Separate kernels for each encoding type eliminate warp divergence. ARRAY0: direct column write. ARRAYn: vectorized load (e.g., uint4 for ARRAY4), loop fully unrolled (compile-time constant trip count), column reconstruction via bitwise OR. BITSET: load header + 256-bit bitmap, split into eight 32-bit words, merge directly into output bitmap via bitwise OR—no column reconstruction needed.

Density-Aware Scheduling : Two complementary schedulers:

AdaBool-T (Traversal-based) for medium/dense queries: evenly distributes fixed-size block chunks across thread blocks; each thread checks query bitmap for its block's row. Load-balanced, latency stable.

AdaBool-C (Candidate-based) for highly sparse queries: two-phase—Preparation scans query non-zeros, uses prefix-sum of per-row block counts to locate active rows, partitions active blocks into balanced task segments; Execution processes only those segments. Avoids scanning inactive blocks.

System-Level Memory Optimizations

Interleaved Shared Memory Layout : In batch-mode AdaBool-T, query bitmap slices are stored in shared memory in column-major interleaved order so that threads in a warp reading the same column across different queries hit the same bank (broadcast) or adjacent banks (conflict-free), eliminating bank conflicts.

Aggregated Row Indexing : Row IDs for blocks in each pool are compressed via Row Index Groups : a base row ID + 8/16/32-bit deltas, reducing row-index storage overhead (especially for tiny ARRAY0 blocks).

Production Deployment in Tencent Ads

AdaBool powers the real-time targeting filter for million-level ads and ten-million-level creatives . Key deployment details:

Periodic index rebuild : Ad/creative library updates trigger rebuild every few minutes; build time ~221 ms on AdsFilter, amortized over hundreds of thousands of queries.

Full GPU pipeline : Output filter bitmap stays in GPU memory for downstream set operations, coarse ranking, and TopK, avoiding CPU-GPU transfers.

Generalized GPU inverted index : The adaptive block structure (Key → 256-value Block) is reused for recall feature matching (e.g., replacing bitwise OR with weighted accumulation for cross-feature scoring).

Experimental Results

AdsFilter (Production Dataset, RTX 4090 D)

Dataset: 100K rows × 10M cols, density 0.001%, avg query activates ~1% filters.

Single-query latency comparison (ms):

Themis: avg 11.391, std 10.080, P90 34.900, P95 35.700, P99 36.500

Genie: avg 7.996, std 6.228, P90 7.800, P95 7.826, P99 13.044

cuBool: avg 1.334, std 0.378, P90 1.421, P95 1.432, P99 1.501

cuSPARSE: avg 1.170, std 0.062, P90 1.204, P95 1.209, P99 1.244

AdaBool-T : avg 0.158 , std 0.082 , P90 0.203 , P95 0.207 , P99 0.235

Single-query : AdaBool-T avg 0.158 ms → 7.4× faster than cuSPARSE , 8.4× faster than cuBool ; P99 0.235 ms → 5.3× better than cuSPARSE .

Batch throughput (Batch=16): cuSPARSE drops from 1,113 to 192 QPS; AdaBool-T scales to 12,279 QPS → 63.9× cuSPARSE , 12.8× cuBool .

RTX A6000 : avg latency 0.215 ms → 16.3× speedup over cuSPARSE .

Index build : 221 ms vs cuSPARSE 444 ms (2× faster) vs cuBool 16,688 ms (~75× faster).

Public Datasets (Sparse Queries)

On Email-Enron (avg density 0.0001%), AdaBool-C achieves 0.014 ms single-query latency and >1M QPS at Batch=32 → 264× cuBool . AdaBool-T wins on AdsFilter, AdaBool-C on Email-Enron, validating complementary schedulers.

Memory Footprint

vs. cuBool (Reduced CSR), AdaBool reduces VRAM to 21%–65% (1.55×–4.86× savings). On synthetic data, as density rises, more blocks auto-switch to BITSET, reaching 7.9× savings over cuSPARSE with latency improvements tracking compression ratio.

Memory usage (MB) comparison:

AdsFilter: COO 783.3, CSR 548.5, cuSPARSE 703.6, cuBool 293.4, AdaBool 149.1 (1.97× vs cuBool)

Email-Enron: COO 4.2, CSR 2.9, cuSPARSE 4.2, cuBool 1.7, AdaBool 1.1 (1.55× vs cuBool)

pdb1HYS: COO 49.7, CSR 33.3, cuSPARSE 36.1, cuBool 17.0, AdaBool 3.5 (4.86× vs cuBool)

Human-Gene1: COO 282.3, CSR 188.3, cuSPARSE 198.4, cuBool 94.4, AdaBool 25.2 (3.75× vs cuBool)

Ablation Study (AdsFilter)

Starting from baseline CSR, modules stacked incrementally:

Base CSR : SpBMV 2.63 ms, SpBMM 9.80 ms.

+AdaRep (adaptive encoding) : 0.46 ms (5.7×), 2.84 ms (3.5×) — main gain from reduced memory traffic.

+AdaExec (encoding-aware kernels + block scheduling) : 0.31 ms, 0.69 ms (SpBMM +4.1×) — eliminates warp divergence and load imbalance.

+RowIndex (aggregated row indexing) : 0.19 ms, 0.46 ms (+1.6×).

+Interleave (shared memory interleaving) : 0.16 ms (overall 16.7×), 0.37 ms (overall 26.6×).

Conclusion

AdaBool demonstrates that for sparse boolean matrix workloads, matching data representation to local sparsity and coupling it with encoding-aware execution and density-adaptive scheduling yields order-of-magnitude gains in latency, throughput, and memory efficiency. The framework has run stably in Tencent's ad serving stack for years and serves as a general GPU inverted-index substrate for broader retrieval scenarios.