A threshold knows only its own block

A block the lookup can work out gave a blocked Bloom filter the balance of two choices without doubling its false positives. Each key hashes to two blocks, and each block carries a threshold on a third hash of the key. A key whose hash is below its first block’s threshold goes there, and otherwise to its second. A block’s threshold falls while keys are placed in order of that hash, closing as the block fills. A lookup reads the threshold, works out which block its key would have gone to, and reads only that one. A penalty set by the block found the design repays about a third of the penalty uneven block loads cost. The bits a second threshold costs found that the threshold table’s bits cost more than their resolution was worth. A four-bit threshold beat an eight-bit one by 9% at 512-bit blocks, because the table is paid for in blocks given up.

Its closing section took the next step in the same direction: not fewer bits a threshold, but fewer thresholds. A block’s threshold matters only to the keys that name that block first. The table holds one for every block, and blocks could share one in pairs or fours. A group’s threshold would close when its busiest block fills, and the table would shrink by the group’s size. The section predicted that sharing between two blocks would lose little balance, since the busier of two blocks closes the pair only slightly early, and would save half the table. It predicted the design would come within a few per cent of one block twice as wide with no table, which it called the ceiling a threshold design can reach. At eight blocks a group, the shared threshold should close too early for most of its blocks, and lose balance faster than the table’s bits are saved.

The first half of that is wrong from the first pair, and the ceiling it named is not one.

The design, and a group of one #

The filter is the earlier pages’: 8,192 keys at 16 bits a key, eight filters and a million absent queries for each setting, thresholds of four bits. Keys are placed in increasing order of their ordering hash, a tied group of keys at a time. A key goes to its first block if its hash is below the threshold of that block’s group of $g$ adjacent blocks, and otherwise to its second block. A group’s threshold closes at the current hash when any block in it would overflow with the first-choice keys waiting for it. The table costs $4/g$ bits a block and is paid for by giving up blocks, so every group size has the same total bits. A lookup reads the group’s threshold and one block. A group of one is the earlier page’s design, and no stored key is ever refused.

Sharing a threshold between two 512-bit blocks raises the false-positive rate from 0.0577% to 0.0650%, 13% worse, and sharing among sixteen reaches 0.0889%, worse than a filter with no threshold at all. At 256-bit blocks the order is the same: pairs cost 8%, and sixteen a group is again worse than none, 0.1482% against 0.1367%. The loss is not confined to large groups, as predicted; it begins at the first pair and continues at every step.

The rates come from one draw of keys at each width, shared by every group size so that the comparison is paired. On three more draws at 512 bits, pairs cost between 17% and 18%, so the first draw’s 13% is the mildest of four. At 256 bits the comparison is less steady. On one draw in four, a single four-bit threshold collapses, to 0.172%, while a shared pair on the same keys reaches 0.116%. The bits a second threshold costs met the same collapse with two four-bit thresholds on 256-bit blocks. Its cause was not traced here. What is clear is that it belongs to a threshold of four bits on a block that holds sixteen keys, where each of the threshold’s sixteen levels holds about one of each block’s keys, so a block that closes one level early turns away a sixteenth of its keys at once, and that sharing the threshold between two blocks damped it rather than caused it. The 512-bit results carry the argument here, and the 256-bit ones agree with it on three draws of four.

The ceiling the section named falls too. One four-bit threshold a block beats one block twice as wide with no table: 0.0577% against 0.0600% at 512 bits, and on every one of the four draws, by 4 to 11%. The earlier pages compared threshold designs with wider blocks as the thing to reach. With the table’s bits cut to four, the threshold design has passed it at 512 bits. The block twice as wide also pays for its balance in lines read: a lookup of a 512-bit block reads one line, and a 1,024-bit block two. At 256 bits the two are level within the draws, 0.0907% against 0.0875% on the first and the other way on two of the others.

What the table saves and what the spread costs #

The accounting is the earlier page’s, and it separates the two effects cleanly. The table’s cost lands in the floor, the rate the filter would have if every block held exactly the mean load. Sharing among pairs lowers the floor from 0.0493% to 0.0477% and doubles the spread’s cost, from 0.0084% to 0.0173%. Larger groups save nothing more in the floor, because a table of one four-bit threshold for every two 512-bit blocks is already so small that giving it up returns no further whole block. The spread’s cost keeps rising, to 0.0412% at sixteen. The table saving is real and small: four bits a block is under 1% of 512, and halving it returns 0.4% of the filter’s memory. The prediction weighed the same two quantities. For pairs the spread’s added cost is five and a half times the table’s saving, where the prediction had it the smaller of the two.

The memory at which sharing would pay #

The balance between the two parts moves with the filter’s memory, and the direction says when sharing could pay. At fewer bits a key the table is a larger share of the filter and its saving is larger. The false-positive rate is also higher, and a rate that is mostly floor has less to lose to spread.

At 8 bits a key, sharing a threshold between two 512-bit blocks costs 4%: a rate of 2.40% against 2.31%. At 12 bits it costs 5%, 0.376% against 0.359%, and at 16 bits 13%. At 8 bits a key the floor is 2.24% of the one-threshold design’s 2.31%, so the spread is only 3% of the rate, and even doubling it moves the rate little. At 16 bits the spread is 15% of the rate, and pairing doubles it. Sharing approaches break-even as a threshold becomes least worth having — a filter so full that its blocks’ balance hardly matters. At the memory where the threshold earns its keep, it is worth what it knows about its own block, and sharing throws that away.

That also bounds the saving any cleverer grouping could find. The table at 16 bits a key and four bits a threshold is under 1% of a 512-bit filter’s memory. Even removing it entirely would lower the floor by about twice what pairing saved, some 0.003 points, against the 0.008 points of spread that one threshold a block leaves and the 0.05 points a single choice costs. A threshold design’s remaining losses are in its spread, and they can only be reduced by giving keys better choices, not by storing their choices more cheaply.

Neighbours fill at unrelated moments #

The prediction’s reasoning was that the busier of two blocks closes the pair only slightly early. That would be true if two neighbouring blocks tended to fill at about the same point in the ordering. They do not.

With one threshold a block, 41% of 512-bit blocks never close at all, and the rest close anywhere from half the ordering hash to its top. Between adjacent blocks the correlation of closing points is 0.02: which block fills first is a matter of which keys named it, and hashing makes that independent from one block to the next. A shared threshold closed by its busiest block must close where the first of its group would have. For a pair that is the smaller of two independent draws from this spread, on average 0.86 of the hash against 0.91 for a block on its own. For eight it is 0.75. The 256-bit blocks show the same shape, 40% never closing and a pair’s minimum at 0.81 against 0.88. Every block in the group then refuses keys it had room for, from the moment its busiest neighbour filled.

The spread of closing points has a simple source. A 512-bit block here has a capacity of 32 keys, and on average 32.25 keys name it as their first choice. The number that do is close to a Poisson count with that mean, and a Poisson count at or under its own mean is nearly a coin toss: it stays at or under 32 with probability 0.53. A block whose first choices never exceed its capacity never closes. Overflow from other blocks’ refused keys adds load on top, which is why the measured share that never close is 41% rather than 53%. The other blocks close when their own demand passes their capacity, which happens at a point in the ordering set by how far over it runs. A hash is a family, not a function found that a hash drawn from a good family spreads keys as independent draws would. That independence is what makes the busiest of a group close so much earlier than the typical member.

The refused keys go somewhere, and where they go is the whole problem. A key turned away from its first block goes to its second, chosen by another hash, with no regard to that block’s load. That placement is exactly the one-choice filter’s, whose spread the threshold existed to avoid. The second choice measured how much the choice between two buckets flattens the load. A shared threshold hands a growing share of keys back to a single random choice.

At 512-bit blocks, a threshold of its own places 89% of keys in their first block; shared by a pair, 83%; by sixteen, 67%. Each lost point is a key sent to a random second block, and the load spread follows. Its standard deviation goes from 3.08 keys a block to 4.65 for pairs and 5.98 for sixteen, slightly more than the one-choice filter’s 5.79. The design’s value was the choice it gave each key, and sharing the threshold takes the choice away from the keys whose own block still had room.

The other way to close a shared threshold #

The busiest block closes the group too early. The obvious alternative is to close the group when its blocks’ total load would pass the group’s capacity, letting a busy block run over while a neighbour has room. It was measured beside the first rule.

Closing by the total is worse again for pairs: 0.0716% at 512-bit blocks against 0.0650%, and 0.1033% against 0.0978% at 256. A busy block that is allowed to run over its capacity carries more keys than a Bloom filter of its width can hold at the target rate. Its false positives grow faster than its neighbours’ shrink, because a filter’s rate rises steeply with load, the property two blocks and the chances they add found makes an overloaded block expensive. At 16 bits a key a lookup tests eleven positions, so a block’s rate is about the eleventh power of the share of its bits set, and the formula everybody sizes filters with is that curve. A few keys over capacity in one block cost more than the same few keys under it save in another. One rule closes too early for most of the group, and the other too late for its busiest block. No single threshold can close at the right moment for two blocks whose right moments are independent.

What was measured and what was not #

Four-bit thresholds, 8,192 keys, one draw a width. Every plate is at 16 bits a key, the earlier page’s setting, one draw of keys shared by every group size, eight filters a point. Three further draws were run for pairs against a threshold a block and against one block twice as wide, and they are what the ranges quoted above come from. The memory comparison is at 512-bit blocks, on the same draw.

Adjacent blocks. A group is $g$ consecutive blocks. Because block choice is by hash, adjacency has no meaning to the keys, and any fixed grouping would behave the same. A grouping chosen after the fact to pair blocks that filled at similar moments would do better. It would have to be stored, and that is the table the design was trying not to keep.

Absent queries only. The rates are false positives on keys never stored, a million of them a setting, so a rate near 0.06% rests on about six hundred false positives and has a sampling spread of about 4%. Every stored key is found in every setting: each filter is queried for all of its own keys once it is filled, and none is missed.

Lines read. Every design here reads one line for the threshold and one for the block. Sharing does not change that, although a smaller table fits more thresholds in a line and is more likely to be cached. Positions confined to one line counted a lookup’s lines as its cost; here the lines are equal and only the rate moves.

Still open: a table coded by where thresholds close #

The table was worth keeping block by block because each block’s threshold records something about that block alone. What sharing tried to save, the table’s bits, can be saved another way. The thresholds are not uniform over their sixteen levels: 40% of blocks never close, and the rest cluster in the upper half of the hash. Their entropy is 2.61 bits, against the four bits each is stored in. A table coded by the distribution of its own values — a short code for “never closed”, longer ones for early closings — would hold the same information in about two thirds of the bits.

The measurement that follows stores each threshold in a code built from the closing distribution of the filter’s own build. It pays for the table in blocks as before, and it measures the rate beside the plain four-bit table and the three-bit table the earlier page found too coarse. The prediction is that the coded table matches the four-bit rate while paying for less than three bits a block. It should gain a little over the plain table, since the returned memory is about half a per cent of the filter. The cost is a lookup. A variable-length code cannot be indexed directly, so the table must be read in chunks with an index of where each begins. The question is whether a threshold can be found in one line, or whether a coded table costs the second read the threshold design was built to avoid. The memory plate above bounds the prize: at 16 bits a key the whole table is 1.6% of the filter, and a third of it is half a per cent.