Optimal multi-block read schedules for partitioned signature files

Queries on partitioned signature files, namely Quick Filter (QF), can lead to retrieve from disk a large number of blocks, depending on the specific query pattern. In order to reduce the overall retrieval time, we consider multi-block read schedules that, provided contiguous allocation of blocks of the file on disk surface is guaranteed by the storage system, transfer more than one block at a time. We show that, for any signature query and buffer size, there always exists an optimal schedule whose reads all have the same size, and that such a constant size (CS) schedule can be determined in a time logarithmic in the number of blocks to be retrieved. We then provide analytical results for the expected performance of QF using CS schedules and compare QF with other, sequential-based, signature file organizations. Finally, we suggest how our approach can also be of interest for other file organizations based on multi-attribute hashing.