TY - JOUR
T1 - Uniform deterministic dictionaries
AU - Ruzic, Milan
N1 - Paper id:: doi10.1145/1328911.1328912
PY - 2008
Y1 - 2008
N2 - We present a new analysis of the well-known family of multiplicative hash functions, and improved deterministic algorithms for selecting “good” hash functions. The main motivation is realization of deterministic dictionaries with fast lookups and reasonably fast updates. The model of computation is the Word RAM, and it is assumed that the machine word-size matches the size of keys in bits. Many of the modern solutions to the dictionary problem are weakly nonuniform, that is, they require a number of constants to be computed at “compile time” for the stated time bounds to hold. The currently fastest deterministic dictionary uses constants not known to be computable in polynomial time. In contrast, our dictionaries do not require any special constants or instructions, and running times are independent of word (and key) length. Our family of dynamic dictionaries achieves a performance of the following type: lookups in time O(t) and updates in amortized time O(n^{1/t}), for an appropriate parameter function t. Update procedures require division, whereas searching uses multiplication only.
AB - We present a new analysis of the well-known family of multiplicative hash functions, and improved deterministic algorithms for selecting “good” hash functions. The main motivation is realization of deterministic dictionaries with fast lookups and reasonably fast updates. The model of computation is the Word RAM, and it is assumed that the machine word-size matches the size of keys in bits. Many of the modern solutions to the dictionary problem are weakly nonuniform, that is, they require a number of constants to be computed at “compile time” for the stated time bounds to hold. The currently fastest deterministic dictionary uses constants not known to be computable in polynomial time. In contrast, our dictionaries do not require any special constants or instructions, and running times are independent of word (and key) length. Our family of dynamic dictionaries achieves a performance of the following type: lookups in time O(t) and updates in amortized time O(n^{1/t}), for an appropriate parameter function t. Update procedures require division, whereas searching uses multiplication only.
KW - multiplicative hash functions
KW - deterministic algorithms
KW - dynamic dictionaries
KW - Word RAM model
KW - amortized update time
U2 - 10.1145/1328911.1328912
DO - 10.1145/1328911.1328912
M3 - Journal article
SN - 1549-6325
VL - 4
SP - 1
EP - 23
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 1
ER -