Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries
DOI:
https://doi.org/10.7146/brics.v4i17.18813Resumé
We consider dictionaries of size n over the finite universe U ={0, 1}^w and introduce a new technique for their implementation: error correcting codes. The use of such codes makes it possible to replace the use of strong forms of hashing, such as universal hashing, with much weaker forms, such as clustering.We use our approach to construct, for any epsilon > 0, a deterministic solution to the dynamic dictionary problem using linear space, with worst case time O(n) for insertions and deletions, and worst case time O(1) for lookups. This is the first deterministic solution to the dynamic dictionary problem with linear space, constant query time, and non-trivial update time. In particular, we get a solution to the static dictionary problem with O(n) space, worst case query time O(1), and deterministic initialization time O(n^(1+epsilon)). The best previous deterministic initialization time for such dictionaries, due to Andersson, is O(n^(2+epsilon)). The model of computation for these bounds is a unit cost RAM with word size w (i.e. matching the universe), and a standard instruction set. The constants in the big-O's are independent upon w. The solutions are weakly non-uniform in w, i.e. the code of the algorithm contains word sized constants, depending on w, which must be computed at compile-time, rather than at run-time, for the stated run-time bounds to hold.
An ingredient of our proofs, which may be interesting in its own right, is the following observation: A good error correcting code for a bit vector fitting into a word can be computed in O(1) time on a RAM with unit cost multiplication.
As another application of our technique in a different model of computation, we give a new construction of perfect hashing circuits, improving a construction by Goldreich and Wigderson. In particular, we show that for any subset S of {0;1}w of size n, there is a Boolean circuit C of size O(w log w) with w inputs and 2 log n outputs so that the function defined by C is 1-1 on S. The best previous bound on the size of such a circuit was O(w log w log log w).
Downloads
Publiceret
1997-01-17
Citation/Eksport
Miltersen, P. B. (1997). Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries. BRICS Report Series, 4(17). https://doi.org/10.7146/brics.v4i17.18813
Nummer
Sektion
Artikler
Licens
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).