The vector quantization approach to clustering derives a set of representative or prototype points to represent the various clusters in a given collection of points. The points are, in general, vectors of a given length. Linde et al. [1] describe an algorithm, known as the generalized Lloyd algorithm or LBG algorithm, for identifying these prototype points (called codebook). The algorithm starts with a suitably initialized set of codewords. Viewing these as cluster centroids, the points are partitioned, and mean quantization error is computed, based on the distance of each point to the codeword of the partition in which it belongs. If the error is not acceptable, the codebook is revised, and the process is repeated.

The authors observe problems with this approach, in that codewords are not evenly distributed with regard to the density of points, and there may be empty partitions. To address these, this paper proposes a measure of the utility of a codeword, to capture these aspects, and revises the LBG algorithm by adding a stage in which some partitions are split or merged based on their utility values. A number of experimental results are reported, showing useful improvement in the final error, and in the number of iterations, as compared to LBG. Empirically, it has been shown that runtime overhead due to the revision is acceptably small.

Although the paper is generally well organized and fairly well written, I felt that the initial section could have done a better job of placing the current work in context. The usage of “D” was very confusing between the first and second half of the paper. Overall, this is a good paper.