Parallel streaming signature EM-tree: A clustering algorithm for web scale applications


Autoria(s): De Vries, Christopher M.; De Vine, Lance; Geva, Shlomo; Nayak, Richi
Data(s)

15/05/2015

Resumo

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.

Formato

application/pdf

Identificador

http://eprints.qut.edu.au/84386/

Publicador

Association for Computing Machinery

Relação

http://eprints.qut.edu.au/84386/1/frp0419-devries.pdf

http://www.www2015.it/documents/proceedings/proceedings/p216.pdf

DOI:10.1145/2736277.2741111

De Vries, Christopher M., De Vine, Lance, Geva, Shlomo, & Nayak, Richi (2015) Parallel streaming signature EM-tree: A clustering algorithm for web scale applications. In Preceedings of the 24th International World Wide Web Conference, Association for Computing Machinery, Florence, Italy, pp. 216-226.

Direitos

Copyright 2015 International World Wide Web Conference

Fonte

School of Electrical Engineering & Computer Science; Science & Engineering Faculty

Palavras-Chave #080107 Natural Language Processing #080109 Pattern Recognition and Data Mining #080306 Open Software #080704 Information Retrieval and Web Search #Document Clustering #Large Scale Learning #Parallel and Distributed Algorithms #Random Projections #Hashing #Document Signatures #Search Tree #Compressed Learning
Tipo

Conference Paper