Optimal Performance of Inverted Files

Many managerial users of information systems require access to data based upon nonunique data record qualifications or classifications. A class of computer file organizations, called inverted files, has been devised to efficiently support such data retrieval. Fundamental to the use of such a file or database organization is the selection of data elements or keys for creation of nonunique key indexes. These indexes provide rapid access to data records which are qualified by logical key expressions. This paper formulates this selection problem as a zero-one, nonlinear programming problem with constraints and describes an optimization algorithm. The model recognizes both known and ad hoc uses of data; complex, Boolean key queries; and index storage capacity and query response time constraints. Computational experience is similar to previous algorithms, which consider more restricted problem formulations.