  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.
