Since 2014
Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries
|
|
| Creator |
Miltersen, Peter Bro
|
|
| Description |
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).
|
|
| Publisher |
Aarhus University
|
|
| Date |
1997-01-17
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/18813
10.7146/brics.v4i17.18813 |
|
| Source |
BRICS Report Series; No 17 (1997): RS-17 Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries
BRICS Report Series; Nr. 17 (1997): RS-17 Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/18813/16458
|
|