Recap: Are Bitvectors Optimal?

In the paper "Are Bitvectors Optimal?" we aim to answer the static membership problem -- that is, given a Universe U = {1, 2, ..., m} and a set S of keys from U, we want to know whether an element u known to be in the universe is in S. This, of course, could be answered with a simple idea of lying out all elements and querying a large number of elements to find if u is among them; however, we aim to minimize storage space and use as few probes as possible. We look at two types of randomized schemes to implement this, each using only one bitprobe. One has one-sided error (where an answer of "Yes, u is in S" might be incorrect) and another has two-sided error (where either a "Yes" or a "No" answer might be incorrect).

We start by making a bipartite graph G=(U,V,E) where U is the Universe and V are locations in memory. For the two-sided error problem we seek a two-coloring of V such that ∀ u ∈ S, at least (1-ε)|Γ(u)| locations are colored 1, and ∀ u' ∉ S, at least (1-ε)|Γ(u)| locations are colored 0 (where 0 maps to an answer of "no" and 1 to "yes"). This is also referred to as being "(n,ε)-two-colorable." The general idea about how we go about this is to separate out those vertices which can be colored 0 and 1 and have no potential for error, and then show that the error on the remaining vertices is bounded by ε. In particular, we use specific properties of the graph as an expander, showing that V has the "(n,ε) Intersection Property," which in essense says that the number of sets of locations which would be "offending" a simple greedy 0/1 coloring is less than the original number of sets. Thus, we take this smaller set of offenders and inductively find a good (n,ε)-two-coloring for it, then adding back in the original non-offender sets which were already properly colored.