Determination of the Optimal Window Size for the Spatial XOR Filter

ABSTRACTIntroductionAn XOR filter is a probabilistic data structure representing a set of keys for membership queries. Given a set of keys, and hash functions , the filter relies on filling in an array such that, for all , equals a special value, called the fingerprint of . A common approach to fill in is by using a greedy algorithm, which may or may not succeed, and whose probability of failing increases as the load factor increases. The Spatial XOR filter is a variant proposing that the hash functions map each key only into a smaller contiguous portion of , called window, and empirical results show that it is possible to achieve a larger for the same chance of succeeding in filling in using the greedy approach. A result in the literature conjectures that the optimal window size is for .MethodsIn this work, we comprehensively test this conjecture, considering various values of and . Using the leave‐one‐out validation process of machine learning, and Occam's razor principle, to determine the optimal window size and maximum load factor as a function of .ResultsWe find that the optimal window size of is confirmed by our methodology, and we provide the concrete function behind the asymptotic notation; as a byproduct of the methodology, we suggest alternative candidate functions for this window optimal size. We also propose the maximum load factor function possible to achieve in terms of .ConclusionsUsing the optimal window size empirically provided by our methodology, the results show that the Spatial XOR filter is competitive among its peers. Other filters have very close space savings compared to the Spatial XOR filter. The derived functions extrapolated well in the experiments, although the theoretical optimal window size remains an open problem.