Module bps_scan 

BPS (Block Projection Sketch) L1 Distance Kernel

This implements the vertical SIMD approach for computing L1 distances between a query sketch and many vector sketches stored in SoA layout.

Algorithm

For each query sketch Q[0..n_blocks]: For each vector V[i] in SoA layout: distance[i] = Σ |Q[slot] - V[slot * n_vec + i]|

Memory Layout

The BPS data uses Structure-of-Arrays (SoA) layout:

• bps[slot * n_vec + vec_id] gives the sketch value for vector vec_id at slot

SIMD Strategy

• AVX2: Process 32 vectors per iteration using 256-bit registers
• NEON: Process 16 vectors per iteration using 128-bit registers
• Scalar: Fallback for unsupported platforms

Math

The L1 distance uses the identity:

|a - b| = max(a - b, 0) + max(b - a, 0) = (a ⊖ b) ∨ (b ⊖ a)

where ⊖ is saturating subtraction and ∨ is bitwise OR.

Functions

bps_scan

Compute BPS L1 distances between query and database vectors.

bps_scan_u32

Compute BPS L1 distances with u32 output.