The use of simulated annealing for clustering data in databases

摘要

PDRT is a prototype design tool which is currently being developed for database workload capture and analysis with an emphasis on performance. A major feature of this tool is a clustering facility which can be used to optimise the proximity between inter-related tuples on a hierarchy of secondary storage devices in order to enhance retrieval performance. As a step towards obtaining a good clustering method we have previously shown that simulated annealing, which is a derivative of the Metropolis Monte Carlo optimisation algorithm, provides an effective solution to this NP-complete placement problem. In this paper we discuss and evaluate new “flavours” of this heuristic methodology found in the literature and investigate the effect of the initial configuration upon the final result.