The proliferation of the web presents an unsolved problem of automatically
analyzing billions of pages of natural language. We introduce a scalable
algorithm that clusters hundreds of millions of web pages into hundreds of
thousands of clusters. It does this on a single mid-range machine using
efficient algorithms and compressed document representations. It is applied to
two web-scale crawls covering tens of terabytes. ClueWeb09 and ClueWeb12
contain 500 and 733 million web pages and were clustered into 500,000 to
700,000 clusters. To the best of our knowledge, such fine grained clustering
has not been previously demonstrated. Previous approaches clustered a sample
that limits the maximum number of discoverable clusters. The proposed EM-tree
algorithm uses the entire collection in clustering and produces several orders
of magnitude more clusters than the existing algorithms. Fine grained
clustering is necessary for meaningful clustering in massive collections where
the number of distinct topics grows linearly with collection size. These
fine-grained clusters show an improved cluster quality when assessed with two
novel evaluations using ad hoc search relevance judgments and spam
classifications for external validation. These evaluations solve the problem of
assessing the quality of clusters where categorical labeling is unavailable and
unfeasible.

本研究提出了一种可伸缩的聚类算法，使用 EM-tree 算法在单个中型计算机上对数千亿个网页进行聚类，并在 ClueWeb09 和 ClueWeb12 上应用该算法，将 500 到 700 万个网页聚类成 50-70 万个聚类，进而提高了聚类质量的评价。