Analyzing the Performance Characteristics of Dynamic Signature File Methods

Abstract

With rapid increase of information requirements from various application areas, there has been much research on dynamic information storage structures that effectively support insertions, deletions and updates. In this paper we evaluate the performance of the existing dynamic signature file methods such as the S-tree, Quick Filter and HS file and provide guidelines for the most effective usage to a given operational environment. We derive analytic performance evaluation models of the storage structures based on retrieval time, storage overhead and insertion time. 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 S-tree and Quick Filter.