Pleated Ribbon Construction: Approximate Sorting Recovers the Locality of a Full Sort

Probabilistic membership filters let storage systems skip reads for keys that are not present. Ribbon filters use much less memory than Bloom filters at comparable false-positive rates, but their higher construction cost limits deployment. I reduce that cost for homogeneous ribbon filters by grouping keys into approximate start-position windows with a counting-sort partition: one counting pass followed by a scatter pass. At 100–400 million keys, this recovers 98.3–98.4% of the cache-miss reduction from a full sort at about one quarter of its reorder cost and makes sequential construction 2.05–2.24× faster than the reference build. The gain comes from reducing misses in dependent row-reduction chains; for the tested Bloom construction and filter queries, whose misses are independent, software prefetch already recovers most of what batching can. I give a proof sketch, supported by an exhaustive enumeration of small systems, that banding followed by back-substitution produces the same filter under any insertion order, for a fixed hash seed and table size, whenever the system is consistent, which a homogeneous ribbon system always is; reordered builds matched the arrival-order build in every measured run and had no false negatives. A slot-range parallel implementation takes 11.9 ns/key at 100 million keys with 16 threads. The method also transfers to RocksDB's shipped Standard128 ribbon builder, where filter construction is 1.8× faster at 100 million keys per filter, with no gain for filters that fit in cache, and measured false-positive rates match stock to six digits. In the evaluated compaction configuration, the total CPU reduction is within run-to-run variation. These results apply to the evaluated filters, parameters, and machines; they do not establish a general construction or deployment crossover with Bloom.