Key-Based Partitioned Bit-Sliced Signature File

A new signature file organization is proposed as a combination of two orthogonal partitioning strategies, the key-based and the bit-sliced, respectively. The design results from theoretical analysis of these elementary approaches in which performance is analytically studied respecting a simplified abstract storage structure model. The new organization is able to achieve very high search performance for queries containing arbitrary number of query terms - bit-sliced (key-based) organization is good only for queries containing few (many) terms, quite bad performance is obtained in the other cases. Update performance is also discussed and a generalization of the method, able to adjust the trade-off between the search efficiency and the maintenance costs, is put forward for consideration. The proposal is also compared with similar approaches in the field of signature files. © 1995, ACM. All rights reserved.