AdaBool: Sparse Boolean Matrix Processing with Adaptive Data Representation

1 Introduction

• Sparse Boolean matrices encode whether relationships exist, making SpBMM a natural abstraction for data-processing workloads such as filtering, recommendation, and graph reachability.Unlike general SpMM, Boolean processing replaces numerical arithmetic with logical operations.Source: §1 · p. 1
• Fixed, monolithic representations constrain later optimization, while real-world Boolean matrices vary sharply in sparsity across regions.Compression choice depends on local density: offset-style encodings suit highly sparse regions, whereas bitmaps suit denser ones.Source: §1 · p. 2
• AdaBool partitions each matrix row into fixed-size blocks, counts each block’s nonzeros, and selects offset-based arrays or a bitmap to match local sparsity.This adapts the representation at block granularity rather than committing the whole matrix to one format.Source: §1 · p. 2
• AdaBool groups blocks by encoding type and processes them with matching GPU paths, enabling fine-grained scheduling across execution units.The type-aware organization makes each kernel’s workload homogeneous and supports more efficient, coalesced memory access.Source: §1 · p. 2
• AdaBool’s end-to-end system outperforms prior designs by more than an order of magnitude across its experiments.The reported benefits of adaptive representation, GPU execution, and system optimizations compound in practice.Source: §1 · p. 2

2.1 Boolean Matrix Multiplication

• In attribute filtering, A maps attributes to documents, B represents queries over attributes, and the product BA returns documents matching each query.Boolean matrix multiplication uses OR and AND in place of arithmetic addition and multiplication.Source: §2.1 · p. 2
• Boolean matrices are often extremely sparse, with density around 10^-4, while Email-Enron and AdsFilter row densities range from 10^-6 to 10^-2.The datasets exhibit highly non-uniform row densities, consistent with hub entities and long-tail rows.Source: §2.1 · p. 3

2.2 Sparse Matrix Multiplication in GPUs

• SpMM GPU performance depends heavily on sparse-data storage and indexing because loading matrix data can consume substantial time and bandwidth.General-purpose CSR-based systems retain arithmetic values, while Boolean-specific approaches can remove them but still preserve CSR metadata and homogeneous execution.Source: §2.2 · p. 3

2.3 Challenges and Opportunities

• Offset arrays compactly encode highly sparse regions, whereas bitmaps are more effective in denser regions, so neither structure is optimal everywhere.Real-world spatially varying sparsity motivates combining formats across matrix regions.Source: §2.3 · p. 4
• Regions with different encodings can be grouped and mapped to matching GPU processing paths rather than forced through one homogeneous execution model.This allows type-specific memory-access patterns and optimizations.Source: §2.3 · p. 4

2.4 System Overview

• AdaBool adaptively encodes fine-grained blocks of A, groups like-encoded blocks for GPU execution, and uses bitmap as the runtime interface for dynamic B and output C.Lower-level memory-layout and metadata-indexing optimizations further improve data movement and access efficiency.Source: §2.4 · p. 4

3.1 Adaptive Boolean Data Representation

• AdaBool chooses among offset-based ARRAYn formats and bitmap-based BITSET for each block, matching the encoding to that block’s local sparsity.ARRAYn serves sparse blocks; BITSET is intended for denser blocks.Source: §3.1 · pp. 4–5
• Element blocks are formed on demand from fixed-length column windows containing nonzeros, so empty windows between nonzero clusters require no blocks.Each block consolidates nonzeros in its window.Source: §3.1 · pp. 4–5
• ARRAYn stores a starting column index and relative offsets, while BITSET represents the block’s columns with one bit per position.For a block length of 256, offsets can use 8 bits instead of 32-bit indices.Source: §3.1 · p. 5

3.2 Configuring the Data Representation

• AdaBool sets m=8 and block length l=256, favoring ARRAYn through n≤32 and switching to BITSET above 33 nonzeros.The parameter choice is derived to balance space efficiency and GPU access patterns; the stated switching threshold is t=33.Source: §3.2 · p. 5

4.1 Executing the Data Representation

• AdaBool groups blocks by encoding and assigns each type a dedicated GPU kernel, while all paths share matching and specialize block loading and output updates.ARRAYn reconstructs indices from offsets, whereas BITSET can be written to the bitmap output without per-element decoding.Source: §4.1 · p. 6, Figure 8 · p. 6

4.2 Scheduling the GPU Execution

• AdaBool-T balances fixed-size chunks of element blocks across GPU thread blocks, avoiding row-based partitioning when rows contain differing numbers of blocks.Threads decode row-index groups and process equal numbers of blocks, balancing work without runtime rescheduling.Source: §4.2 · p. 7, Figure 9 · p. 7
• AdaBool-C uses nonzeros in B to identify active rows and prepare balanced task segments, pruning irrelevant blocks before execution for sparse inputs.A precomputed prefix-sum array over per-row block counts supports locating the relevant blocks.Source: §4.2 · p. 7, Figure 10 · p. 7
• AdaBool-T is the default for robust performance across workload regimes, while AdaBool-C is preferable when B is sparse enough for pruning to outweigh preparation cost.The better strategy can be selected from workload characteristics; an automatic selector is left to future work.Source: §4.2 · p. 7

5.1 Interleaved Memory Layout

• AdaBool caches B in column-major shared-memory layout so warp threads access consecutive addresses or broadcast a shared word, avoiding row-major bank conflicts.The layout suits batches whose block row indices are clustered, making concurrently probed columns tend to be close.Source: §5.1 · p. 8

5.2 Aggregated Row Indexing

• Aggregated row indexing stores a 32-bit base row per group and compact relative offsets for the remaining rows, with offset width chosen by the group’s range.Runtime decompression reconstructs each row index from its base and offset, reducing memory traffic without substantial computation overhead.Source: §5.2 · p. 8

6.1 Micro-Benchmark

• At n=90K, AdaBool completes in 290 ms—7.9× and 3.2× faster than cuBool and cuSPARSE, respectively; it scales to n=200K with a 7.7× advantage over cuBool.Under uniform and Gaussian distributions at n=100K, AdaBool-T averages 390 ms and 388 ms, respectively, while cuSPARSE runs out of memory.Source: Figure 17 · p. 10, §6.1 · p. 10

6.2 Sources of Performance Advantage

• At matrix density 10−2, AdaBool uses 7.9× less GPU memory than cuSPARSE and completes in 0.058 ms versus cuSPARSE’s 1.812 ms.Profiling also finds that cuBool’s scheduling phase grows from 4% to 92% of total time as query density rises.Source: §6.2 · pp. 10–11, Figure 18 · p. 11

6.3 Production Workload: Attribute Filtering

• 0.158 ms: AdaBool-T’s average AdsFilter single-query latency is 7.4× faster than cuSPARSE and 8.4× faster than cuBool.On the A6000, AdaBool achieves a 16.3× speedup over cuSPARSE.Source: Table 1 · p. 11, §6.3 · pp. 11–12, Table 2 · p. 12
• 12,279 QPS: AdaBool-T peaks at batch size 16, a 63.9× improvement over cuSPARSE and a 12.8× speedup over cuBool.Throughput continues to improve as batch size increases.Source: Figure 19 · p. 11, §6.3 · p. 11

6.4 Public Benchmarks: Real-World Datasets

• 4.9×–32.3× speedups: AdaBool-C achieves the lowest completion time on all three public datasets, with 0.017–0.021 ms latency overall.Both AdaBool scheduling methods outperform the major baselines on these matrix multiplication workloads.Source: Table 4 · p. 12, §6.4 · p. 12

6.5 Ablation Study

• 16.7× for SpBMV and 26.6× for SpBMM: the complete +Interleave system’s speedups over CSR reflect the combined design, not one isolated optimization.The offset-bitmap representation contributes the largest individual gain; execution, row indexing, and interleaved addressing add further improvements.Source: Figure 21 · p. 13, §6.5 · p. 13

• cuSPARSE and Sputnik are prominent GPU SpMM baselines, while spECK and GE-SpMM improve CSR memory efficiency through workload repartitioning.ELLPACK-Block uses uniform blocks for SpMV but is limited to matrices with moderate, relatively uniform row densities.Source: §7 · p. 13
• Tensor Core sparse methods rely on hardware specialized for small dense tiles and algorithmic computation, which the paper says mismatches SpBMM’s large sparse inputs and logical operations.The paper describes this as a constraint on broader applicability.Source: §7 · p. 13
• cuBool is the closest related GPU SpBMM library; other systems target graph analytics, retrieval, or database execution rather than fundamental SpBMM backend optimization.The paper names Bit-GraphBLAS, GraphBLAS, Griffin, LiNR, Themis, and Genie among these domain-focused systems.Source: §7 · pp. 13–14
• CPU libraries and adaptive CPU methods exploit hardware characteristics that the paper says do not directly transfer to GPUs because of differences in memory hierarchy, parallelism, and execution models.Source: §7 · p. 14

• AdaBool partitions matrices into regions and selects each region’s representation according to its local sparsity.Source: §8 · p. 14
• Its execution model combines role-aware encoding, type-based execution, and block-level scheduling, alongside system optimizations for GPUs.Source: §8 · p. 14
• Extensive evaluations report significant performance improvement over representative baselines across diverse workloads.Source: §8 · p. 14