You are provided with the abstract of a scientific paper and the abstracts of the papers it references. Your task is to write a Related Work section for the main paper. This section should concisely summarize and integrate the key points from the cited abstracts, reflecting how they relate to the main paper's contributions and context. In your summary, use numerical citation markers like [1], [2], etc., to refer to the corresponding papers.

Main Abstract:
Simple tabulation dates back to Zobrist in 1970 who used it for game playing programs. Keys are viewed as consisting of c characters from some alphabet Φ. We initialize c tables h0, ... , hc-1 mapping characters to random hash values. A key x = (x0, ... , xc-1) is hashed to h0[x0]⊕· · ·⊕hc-1[xc-1], where ⊕ denotes bit-wise exclusive-or. The scheme is extremely fast when the character hash tables hi are in cache. Simple tabulation hashing is not even 4-independent, but we show here that if we apply it twice, then we do get high independence. First we hash to some intermediate keys that are 6 times longer than the original keys, and then we hash the intermediate keys to the final hash values. The intermediate keys have d = 6c characters from Φ. We can then view the hash function as a highly unbalanced bipartite graph with keys on one side, each with edges to d output characters on the other side. We show that this graph has nice expansion properties, and from that it follows that if we perform another level of simple tabulation on the intermediate keys, then the composition is a highly independent hash function. More precisely, the independence we get is |Φ|Ω(1 c). In our O-notation, we view both |Φ| and c is going to infinity, but with c much smaller than |Φ|. Our space is O(c|Φ|) and the hash function is evaluated in O(c) time. Siegel [FOCS'89, SICOMP'04] has proved that with this space, if the hash function is evaluated in o(c) time, then the independence can only be o(c), so our evaluation time is best possible for Ω(c) independence-our independence is much higher if c = |Φ|o(1 c). Siegel used O(c)c evaluation time to get the same independence with similar space. Siegel's main focus was c = O(1), but we are exponentially faster when c = ω(1). Applying our scheme recursively, we can increase our independence to |Φ|Ω(1) with o(clogc) evaluation time. Compared with Siegel's scheme this is both faster and higher independence. Siegel states about his scheme that it is “far too slow for any practical application”. Our scheme is trivial to implement, and it does provide realistic implementations of 100-independent hashing for, say, 32-bit and 64-bit keys.

Cited Abstract(s):
[1]: We describe a simple randomized construction for generating pairs of hash functions h 1 ,h 2 from a universe U to ranges V = [m] = (0,1,...,m-1) and W = [m] so that for every key set S ⊆ U with n = |S| ≤ m (1 + e) the (random) bipartite (multi)graph with node set V ∪ W and edge set (h 1 (x),h 2 (x))| x ∈ S exhibits a structure that is essentially random. The construction combines d-wise independent classes for d a relatively small constant with the well-known technique of random offsets. While keeping the space needed to store the description of h 1 and h 2 at O(nζ), for ζ < 1 fixed arbitrarily, we obtain a much smaller (constant) evaluation time than previous constructions of this kind, which involved Siegel's high-performance hash classes. The main new technique is the combined analysis of the graph structure and the inner structure of the hash functions, as well as a new way of looking at the cycle structure of random (multi)graphs. The construction may be applied to improve on Pagh and Rodler's "cuckoo hashing" (2001), to obtain a simpler and faster alternative to a recent construction of Ostlin and Pagh (2002 03) for simulating uniform hashing on a key set S, and to the simulation of shared memory on distributed memory machines. We also describe a novel way of implementing (approximate) d-wise independent hashing without using polynomials.

[2]: A tabulation-based hash function maps a key into d derived characters indexing random values in tables that are then combined with bitwise xor operations to give the hash. Thorup and Zhang (2004) presented d-wise independent tabulation-based hash classes that use linear maps over finite fields to map a key, considered as a vector (a,b), to derived characters. We show that a variant where the derived characters are a+b*i for i=0,..., q-1 (using integer arithmetic) yielding (2d-1)-wise independence. Our analysis is based on an algebraic property that characterizes k-wise independence of tabulation-based hashing schemes, and combines this characterization with a geometric argument. We also prove a non-trivial lower bound on the number of derived characters necessary for k-wise independence with our and related hash classes.

[3]: In the framework of Wegman and Carter, a @math -independent hash function maps any @math keys independently. It is known that 5-independent hashing provides good expected performance in applications such as linear probing and second moment estimation for data streams. The classic @math -independent hash function evaluates a degree 4 polynomial over a prime field containing the key domain @math . Here we present an efficient 5-independent hash function that uses no multiplications. Instead, for any parameter @math , we make @math lookups in tables of size @math . In experiments on different computers, our scheme gained factors of 1.8 to 10 in speed over the polynomial method. We also conducted experiments on the performance of hash functions inside the above applications. In particular, we give realistic examples of inputs that make the most popular 2-independent hash function perform quite poorly. This illustrates the advantage of using schemes with provably good expected performance for all inputs.
Siegel states [Abstract] siegel04hash about his scheme that it is far too slow for any practical application''. This and the @math evaluation time has lead researchers to seek simpler and faster schemes. Several works [1] [2] [3] have been focused on the case of smaller independence @math . These works have all been position sensitive like ours. Fix @math . We are looking at functions @math , to be composed with a simple tabulation hash function @math . The evaluation time is @math , so we want @math to be small.