Partitioned signature files: design issues and performance evaluation

Reviewer: Esen A. Ozkarahan

The search of very large databases requires special hardware and software architectures to achieve acceptable performance. Text (document) databases are among the largest, which further complicates the search problem. In order to achieve efficient searching, many systems use fast access paths such as indices, partitioning, and signatures. This paper discusses efficient organization and search of signatures. As the authors point out, the compression factor of signature techniques (due to hash coding and superimposing) is 10–20 percent of the size of the original database. Such low compression would not mean much for a database size of 300 gigabytes, and the gigabyte range is common for document databases. The authors recognize this fact and propose the partitioning of signature files and their sequential or parallel search, which is a relevant goal. Partitions must be generated so that they cannot be searched for irrelevant queries, and the sizes of the partitions must be unskewed in order to balance loads in case of parallel processing. Randomly assigning signatures to partitions would defeat the first goal. Also, in the proposed partitioning schemes, a partition key with all binary ones should participate in every query search because such a key would include all possible query keys regardless of the relevance of the corresponding documents. The authors propose three partitioning schemes—fixed prefix, extended prefix, and floating key. All are based on extracting a subset of the signature bits and grouping signatures on the basis of matching keys. The goal is to further reduce the search space and the number of signatures searched. An even signature distribution is important, especially when partitions are searched in parallel. Fixed prefix partitioning is the simplest approach, and floating key partitioning gives the best results. Incoming queries should be processed for signature generation and query key extraction and query keys should be extracted in the same way that partition keys are generated. Any partition whose key includes the query key is further processed, otherwise, it is unqualified for further search. The paper gives detailed performance comparisons of the proposed partitioning methods (with respect to the aforementioned criteria) as well as proofs of the correctness of the proposed methodologies. The definition of n and the query and signature weights are carelessly omitted. The argument that all signatures must be searched in the bit-sliced (transposed) organization of signatures is imprecise. Such an organization resembles an inverted index with hashing. An inverted index is not exhaustively searched. The authors should have compared the execution performance of the transposed organization with that of the sequential search of the proposed partitioned approach. Several recent studies have established that the signature methodology does not yield high quality information retrieval in terms of recall and precision. Also, a document with a longer signature has a better chance of being retrieved. One cannot easily assign nonbinary term weights to documents and queries. On the other hand, the signature methodology addresses the needs of office information systems for fast searching of unformatted texts.