A method and system for generating threads of documents from a collection C of documents containing terms. Each document of C has a timestamp and an associated timestamp index. The timestamp indexes are ordered in accordance with an ordering of the associated timestamps. A relevance graph G generated from C is an acyclic directed graph. Each node of G denotes a document of C. Each edge of G connects a pair of directed nodes pointing from a node having an earlier timestamp to a node having a later timestamp. At least one thread of G is determined by executing a matching-based algorithm or a dynamic programming algorithm. Each thread is a path through G originating at a first node and terminating at a second node and including one or more contiguous edges from the first node to the second node. The at least one thread is outputted.