Adaptive record clustering

Reviewer: Donald Harris Kraft

This paper defines the problem under consideration as the appropriate assignment of physical records (clustering) in a database to blocks so as to minimize the expected number of blocks accessed in response to a query. The average is taken over all possible queries. Since the problem has been shown to be NP-hard, heuristic clustering algorithms have been developed. One can totally sort the records on the basis of a concatenated sort key. This sort key is formed by concatenating each record's values for the various attributes in order of the frequency of use of the attributes. A partial sort modification sorts all the records in a buffer but does not bother to merge the buffers in the interest of efficiency. The algorithm presented here, however, allows the records to be clustered adaptively. First, each record is assigned an arbitrary position on the real line. Then, as each query occurs, those records deemed relevant to the query are moved closer to their centroid by an amount proportional to their distances from the centroid. The centroid is the average position of the relevant records. Moreover, as part of the query processing mechanism, an identical number of records is chosen at random, and each record is moved away from its centroid. Over time, a clear pattern of clustering will emerge. An analysis of the algorithm shows conditions for a proper constant of proportionality for moving similar records closer together towards their centroid. The objective is to decrease the sum of the squared distances of records in a cluster from their centroid summed over all clusters, while increasing the sum of the squared distances of cluster centroids from the centroid of all records. An Appendix gives the gory details of this analysis. The algorithm is then refined to take into account the relative cost, in terms of the expected number of blocks accessed, of the minimum clustering mechanism. This is done by adjusting the distance each record is moved. Of course, the final step is the assignment of clustered records to blocks. The authors present an impressive array of experimental results. They conclude that adaptive clustering can yield significant improvement over random assignment and even over total sorting. This is explained by the uneven access distribution (20 percent of the records are retrieved in response to 80 percent). The ability of this algorithm to yield improvement makes this paper necessary reading for those interested in retrieval issues.