Zeno Filter: To Infinity in Tiny Steps

Filters are compact probabilistic data structures that answer ''have I seen this before?'' without storing everything they have seen so far. Databases rely on them to skip unnecessary storage lookups and save time. In many applications, the total data size is unknown in advance, creating the need for filters that can expand as the dataset grows. However, existing expandable filters suffer from two forms of space inefficiency. First, they double in size to prevent hash collisions, leaving 50% of space wasted immediately after expansion. Second, they expand out-of-place, temporarily keeping both the old and new filters in memory, further inflating space usage. We introduce Zeno Filter to resolve this wastage. It addresses the first problem by enabling expansions of less than 2×, achieved by stretching the distance between entries until hash collisions can be resolved. It addresses the second by expanding in-place, using a succinct and efficient indirection layer to relocate entries without duplication. The result is an expandable filter that cuts space by up to 60% while matching the speed and accuracy of existing designs.