Many clustering algorithms, including k-means, require an access to the entire data set. When the data set is very large and does not fit into available memory one has to squash the dataset to make applications of k-means-like algorithms possible. The Balanced Iterative Reducing and Clustering algorithm (BIRCH) is a clustering algorithm designed to operate under the assumption the amount of memory available is limited, whereas the dataset can be arbitrary large [147]. The algorithm does the squashing, or generates a compact dataset summary minimizing I/O cost involved in clustering the dataset. BIRCH thus reduces the problem of clustering the original very large data set into the one of clustering the set of summaries which has the potential to be much smaller. In the next section we briefly describe the basic idea behind BIRCH, and then use this idea to describe a version of k-means that can be applied to partitions generated by BIRCH.

3.1. Balanced Iterative Reducing and Clustering Algorithm

For a data set = { a ₁ , , a _m} too large to fit into the available computer memory consider a partition ? = { ? ₁ , , ? _M} of . We would like to consider each cluster ? _i ? ? as a single feature in such a way that for each subset of p clusters in ? computation of

is possible. The question now is: what information concerning the partition