EFFICIENT SIGNATURE FILE METHODS FOR TEXT RETRIEVAL

Signature files have been studied extensively as an access method for textual databases. Many approaches have been proposed for searching si gnatures files efficiently. However, different methods make different assumptions and use different performance measures, making it difficul t to compare their performance. In this paper, we study three basic me thods proposed in the literature, namely, the indexed descriptor file, the two-level superimposed coding scheme, and the partitioned signatu re file approach. The contribution of this paper is two-fold. First, w e present a uniform analytical performance model so that the methods c an be compared fairly and consistently. The analysis shows that the tw o-level superimposed coding scheme, if stored in a transposed file, ha s the best performance. Second, we extend the two-level superimposed c oding method into a multilevel superimposed coding method, we obtain t he optimal number of levels for the multilevel method and show that fo r databases with reasonable size the optimal value is much larger than 2, which is assumed in the two-level method. The accuracy of the anal ytical formula is demonstrated by simulation.