making deterministic signatures quickly
We present a new technique of universe reduction. Primary applications are the dictionary problem and the predecessor problem. We give several new results on static dictionaries in different computational models: the word RAM, the Practical RAM, and for strings - the cache-oblivious model. All algorithms and data structures are deterministic and use linear space. Representative results are: a dictionary with a lookup time of O (log log n ) and construction time of O ( n log log n ) on a word RAM, and a static predecessor structure for variable-length binary strings with a query performance of O (| s|/B + log | s | + log log n ) I/Os, for query argument s , in the cache-oblivious model.
perfect hashing deterministic algorithms