Generalized Partitioning Scheme of Singnature File for Information Retrieval

Yong-Moo KWON  Yong-Jin PARK  

IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.2   pp.189-198
Publication Date: 1993/02/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Databases
signature file,  superimposed coding information retrieval,  partitioned signature file technique,  partitioning scheme of signature file,  

Full Text: PDF(720KB)>>
Buy this Article

Compared to multi-level signature file techniques, PSF (Partitioned Signature File) technique has less processing overhead by its characteristics of a simple file organization. In a multi-processor environment, the PSF technique also has an advantage that queries can be processed in parallel effectively by allocating one or more partitions to each processor. Main point of the PSF technique is a partitioning scheme based on a key selection. In this paper, an n-BFK (n-Bounded Floating Key) partitioning scheme is proposed, in which the number of segments for a key selection is bounded by n. The cost model is developed for the performance evaluation of the proposed scheme. By performance comparison with the existing schemes, the efficiencies of the proposed scheme are shown with respect to a disk access cost, a signature reduction ratio, and an uniformity of workload.