An optimal multilevel signature file for large databases

Signature files have been studied extensively as an access method for document databases and for partial match retrieval in relational databases. Many approaches have been proposed for searching signatures files efficiently. The authors show that the two-level superimposed coding scheme, if stored in a transposed file, has an excellent performance compared to a single-level signature file. They introduce the multi-level superimposed coding method, which extends the two-level superimposed coding method to more than two levels and show that the two-level method is not optimal, instead, the optimal number of levels is dependent on the size of the text file