Unit-Time Predecessor Queries on Massive Data Sets.

New data structures are presented for very fast predecessor queries on integer data sets stored on multiple disks. A structure is presented that supports predecessor queries in one disk seek performed in parallel over multiple disks, no matter how large the data set. For truly massive data sets, the space requirement of this structure approaches twice the space needed to simply store the data on disk. A second structure is presented that supports predecessor queries in the time it takes to perform two disk seeks, but has more moderate space requirements. Its space usage approaches the space needed to store the data on disk, and has manageable space requirements for smaller massive data sets. [ABSTRACT FROM AUTHOR]