THE FOLD / LOOT / THE HOARD / THE SUCCINCT RANK
THE SUCCINCT RANK
three touches, wherever you ask
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
How many 1s appear before position i in a bit array? Answering it by counting is linear. Answering it instantly usually costs a word per bit. There is a third option that costs a fraction, and answers in a fixed number of touches.
LIT verified live. over 1,048,576 bits containing 524,772 ones, a two-level index of 256 superblock counters and 16,384 block counters occupies 270,336 bits — 25.8% of the data. Every query is answered in exactly 3 memory touches: one superblock, one block, one masked popcount, regardless of where i falls. Checked against a naive running count at every one of the 1,048,576 positions: 0 mismatches.
LIT verified live. over 1,048,576 bits containing 524,772 ones, a two-level index of 256 superblock counters and 16,384 block counters occupies 270,336 bits — 25.8% of the data. Every query is answered in exactly 3 memory touches: one superblock, one block, one masked popcount, regardless of where i falls. Checked against a naive running count at every one of the 1,048,576 positions: 0 mismatches.
2 HOW IT WAS WEAVED · AI + HUMAN
Two-level rank indexes are Jacobson (1989) and Clark (1996); the whole succinct-structures programme follows from them.
AVAN (AI) reports the overhead as 25.8% rather than calling this succinct, because at this size it is not. The o(n) result needs the block size to grow with
AVAN (AI) reports the overhead as 25.8% rather than calling this succinct, because at this size it is not. The o(n) result needs the block size to grow with
log n, and at 220 bits the constant factors are still in charge — the asymptotics are real and this measurement does not demonstrate them. What it does demonstrate is the part that is true at every size: 3 touches, verified at every position rather than sampled, because an index that is right at 99.99% of positions is not an index.3 ONE DIMENSION
1,048,576 positions checked. Three touches each.
4 TWO DIMENSIONS · INTERACTIVE
Change the block size and watch space trade against nothing.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that a clever index buys constant-time rank cheaply. The inverse is that it is not the index that is clever, it is the popcount. The two levels only get you to within one block; the last step is counting the bits of a single word, and that is O(1) solely because the hardware has an instruction for it. Read backwards, this data structure is a negotiation with a particular machine — move the block size away from the word size and the ‘constant’ grows a loop — and a great deal of what is called algorithmic constant time is an instruction somebody put in silicon.
LIT over 1,048,576 bits containing 524,772 ones, a two-level index of 256 superblock counters and 16,384 block counters occupies 270,336 bits - 25.8% of the data - and every query is answered in exactly 3 memory touches, one superblock, one block and one masked popcount, regardless of where i falls; checked against a naive running count at every one of the 1,048,576 positions, 0 mismatches
FIG Two-level rank indexes are Jacobson (1989) and Clark (1996). AVAN reports the overhead as 25.8% rather than calling this succinct, because at this size it is not: the o(n) result needs the block size to grow with log n, and at 2^20 bits the constant factors are still in charge, so the asymptotics are real and this measurement does not demonstrate them. What it does demonstrate is true at every size - 3 touches, verified at every position rather than sampled, because an index that is right at 99.99% of positions is not an index.
FIG Two-level rank indexes are Jacobson (1989) and Clark (1996). AVAN reports the overhead as 25.8% rather than calling this succinct, because at this size it is not: the o(n) result needs the block size to grow with log n, and at 2^20 bits the constant factors are still in charge, so the asymptotics are real and this measurement does not demonstrate them. What it does demonstrate is true at every size - 3 touches, verified at every position rather than sampled, because an index that is right at 99.99% of positions is not an index.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HOARD · David Lee Wise (ROOT0), with AVAN