Algorithms for record clustering and file reorganization
Edward R. Omiecinski · 1984
The problem of record clustering is to determine a placement of the records of a file on pages of a secondary storage device such that we minimize a specified cost function. The problem of optimal record clustering is computationally difficult, i.e. NP-complete. Consequently, we develop heuristics whose time and space requirements are efficient and whose solution is good. We compare our heuristics with an alternate method to show an average improvement of 30% over the alternative. After determining a good record clustering, we must efficiently reorganize the database to bring it into the new state. We propose two schemes, one using a static cost and the other a dynamic cost. Both fall within the category of incremental reorganization. Like record clustering, our reorganization problem is also NP-complete and we apply a heuristic for the traveling salesman problem in our scheme. A comparison of our method with another approach shows that our combined clustering and reorganization methods produce a smaller overall cost, i.e. a 70% improvement.