John Howat
We consider the problem of predecessor search over the universe {0,1,…,U-1 } when given a probability distribution over the possible queries to be made. We obtain several results that are related to the entropy of the probability distribution that are close to best-known current non-biased bounds. We present two main types of results: those with (nearly) optimal query time and those with linear space.
This is (ongoing) joint work with Prosenjit Bose, Rolf Fagerberg and Pat Morin.