For processing a signature in parallel, a declustering algorithm that must avoid data skew and execution skew is needed. In this paper we propose a new signature file declustering method, called MIN-entropy, that achieves balanced distribution for effective parallel processing. The MIN-entropy declusters a signature file based on a new dynamic measure of execution load, called signature-entropy, that is derived from the previously declustered signature. Since the MIN-entropy effectively declusters a signature file by using the dynamic measure, it can provide high performance for a variety of workloads and configurations. We show through the simulation experiments that the MIN-entropy improves performance under various data workloads. (C) 2000 Elsevier Science B.V. All rights reserved.