Computing Dense Clusters On-line for Information Organization
Javed Aslam, Katya Pelekhov, Daniela L. Rus · 1997
We present and analyze the off-line star algorithm for clustering static information systems and the online star algorithm for clustering dynamic information systems. These algorithms partition a document collection into a number of clusters that is naturally induced by the collection. We show a lower bound on the accuracy of the clusters produced by these algorithms. We use the random graph model to show that both star algorithms produce correct clusters in time \\Theta(V +E). Finally, we provide data from extensive experiments. 1 Introduction Modern information systems have vast amounts of unorganized data that changes dynamically. Consider, for example, the flow of information that arrives continuously on news wires, or is aggregated by a news organization such as CNN. Some stories are brand new. Other stories are follow-ups of previous stories. Yet another type of stories make previous reportings obsolete. The news focus changes regularly with this flow of information. In such dyn...