An Optimal Index for PAT Arrays

Gonzalo Navarro

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.