Bounds on Storage for Consecutive Retrieval
Udaiprakash I. Gupta · Journal of the ACM · 1979
A file with m permissible queries (that are known a pnon) can be partitioned into 2 '~ -1 disjoint bins, each consisting of exactly those records that are pertinent to one specific set of queries, and not pertinent to the remaining queries A generalized venson of the consecutive retrieval organization (CRO) called f-graph CRO (one m which redundancy of records and explicit pointers are permitted) is examined Ehnch and Lipski have presented an acychcf-graph CRO which requires approximately 4~m2m-l bin occurrences We show that any fgraph CRO requires at least ½m2 m-~ bin occurrences With some additional restrictions on the structure of the acychc organization, we can tighten the lower bound to {m2 m-t Since Ehnch and Lipski's organization conforms to this restricted structure, this, m a sense, proves the optimality of their result We also exhibit an f-graph CRO which requires only ~m2 m-I bin occurrences, and show that with a broad class off-graph CRO's, it Is not possible to do any better This is the shortest f-graph CRO that we know of KEY WORDS AND PHRASES combinatorial problems, consecutive retrieval, file organization, f-graph consecutive retrieval organization, reformation retrieval, inverted files, redundant storage, storage space bounds CR CATEGORIES 3 70, 3.73, 3 7'1, 5 30