Polynomial Complete Consecutive Information Retrieval Problems

A set of queries Q is said to have the consecutive retrieval property with respect to a set of records R if there exists an organization of the record set (without duplication of any record) such that for every $q_i \in Q$, all relevant records can be stored in consecutive storage locations [5]. In practice, this property does not appear very often. Hence, either duplication of records is allowed so that pertinent records corresponding to any query are always stored consecutively or storing the pertinent records corresponding to a query in several blocks of consecutive storage locations is necessary so that each record is stored only once. The former gives rise to the problem of minimizing the duplication of records and the latter gives rise to the problem of minimizing the number of blocks of consecutive storage of relevant records. The computational complexity of each of these two problems is studied in this paper and both of these problems are shown to be polynomial complete in the sense of Cook [2] an...