On Search Performance For Conjunctive Queries In Compressed, Fully Transposed Ordered Files

A new file organization method, providing very high performance for a large class of associative queries, is abstractly defined. The organization may be viewed both as a development of the fully transposed file as a generalized trie. Its average search performance is modelled under some simplifying assumptions. Also, the model´s predictions are compared with measurement results obtained from a prototype system, and a qualitative agreement is found. For purpose of comparison, analytical and measured cost curves for fully transposed file search are also given.