Dynamic Construction of Signature Files based on Frame Sliced Approach

Abstract

Many works on the signature file methods have been made in the past, but they are mainly for static environments. However, many recent applications in practice require a dynamic information storage structure that effectively supports insertions, deletions and updates. Though there are a few signature file techniques for dynamic environments, they suffer from serious performance degradation when query signature weights are light. In this paper, we propose a new dynamic signature file organization based on a frame sliced approach, called the hierarchical signature (HS) file. The HS file alleviates the problem of light query signature weights. We derive analytic performance evaluation models of the existing dynamic signature file methods and the proposed HS file. We also perform extensive experiments with various data distributions such as uniform, normal and exponential distributions. The relationships among various performance parameters are thoroughly investigated. We show through performance comparison based on analytic models and experiments that regardless of data distribution, the HS file significantly improves performance in both the retrieval time and the storage overhead over the other dynamic signature file methods proposed earlier.