An Optimal Index for PAT Arrays
We study the problem of keeping in main memory an index for a
large PAT array stored in secondary storage. This index is used
to minimize the number of accesses to secondary memory, performing
the main part of the search in main memory. However, we have a
maximum allowed size for this index, and it is not clear which is
the optimum between keeping many short keys or few long keys.
We first derive the optimality criterion,
then develop and analyze an algorithm to find the optimum index while
building the PAT array, and finally show a probabilistic algorithm that
allows to trade efficiency for precision.