ABSTRACT Introduction An 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 . Methods In 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 . Results We 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 . Conclusions Using 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.

A graph is an interval graph if its vertex set corresponds to a family of intervals on the real line, called a model, such that two distinct vertices are adjacent in the graph if and only if their corresponding intervals intersect each other. The minimum number of interval lengths that suffices to represent a model of a given interval graph is its interval count. The use of mathematical optimization techniques for solving interval count problems was first explored by Joos et al.[1]. In more detail, given a bipartition of vertices into classes of lengths, the authors propose an efficient linear programming based algorithm for solving the interval count two problem. However, so far, no mathematical formulation exists in the literature for general interval count. As a contribution in that direction, we introduce a mixed integer programming formulation for the exact value of interval count, parameterized by the largest interval length. Additionally, we also propose a quadratic formulation for a valid upper bound on interval count. Solution algorithms for these formulations were tested on interval count instances found in the literature. As an outcome of these experiments, the algorithm for the upper bound formulation was shown to run much faster than its exact solution counterpart. Furthermore, the upper bounds thus obtained were frequently certified as optimal by the exact algorithm.

We are interested in embedding trees T with ∆(T) ≤ 4 in a rectangular grid, such that the vertices of T correspond to grid points, while edges of T correspond to non-intersecting straight segments of the grid lines. Such embeddings are called straight models. While each edge is represented by a straight segment, a path of T is represented in the model by the union of the segments corresponding to its edges, which may consist of a path in the model having several bends. The aim is to determine a straight model of a given tree T minimizing the maximum number of bends over all paths of T. We provide a quadratic-time algorithm for this problem. We also show how to construct straight models that have k as its minimum number of bends and with the least number of vertices possible. As an application of our algorithm, we provide an upper bound on the number of bends of EPG models of VPT ∩ EPT graphs.

Abstract We revisit the deadlock‐prevention problem by focusing on priority digraphs instead of the traditional wait‐for digraphs. This has allowed us to formulate deadlock prevention in terms of prohibiting the occurrence of directed cycles even in the most general of wait models (the so‐called AND‐OR model, in which prohibiting wait‐for directed cycles is generally overly restrictive). For a particular case in which the priority digraphs are somewhat simplified, we introduce a Las Vegas probabilistic mechanism for resource granting and analyze its key aspects in detail. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 203–210 2014