The housekeeping processing is usually performed to optimize the I/O costs of spatial join refinement step.The problems in housekeeping phase have been shown NP-hard

and most methods solve them with high computation complexity.We reduce the page-clustering problem and cluster-sequencing problem to

k

-way partition and maximum length of graph respectively

and solve the problems with improved genetic algorithm and approximation algorithm based on maximum-span-tree.To satisfy the constraint of page cluster partition

we make some correction on the classical genetic algorithm.The solution of approximation algorithm is greater than half of optimal solution.Theoretical analysis and simulation experiment shows the feasibility and effectiveness.