Making deterministic signatures quickly
Milan Ružić · ACM Transactions on Algorithms · 2009
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 the cache-oblivious model. All algorithms and data structures are deterministic and use linear space. Representative results are: a dictionary with a lookup time ofO(log logn) and construction time ofO(n) on sorted input on a word RAM, and a static predecessor structure for variable- and unbounded length binary strings that in the cache-oblivious model has a query performance ofO(|s|/B+ log |s|) I/Os, for query arguments.