Patent Document ID: 9805138
Application ID: 14616032
Patent Status: 1

Claim One:
1. An apparatus for performing clustering of documents, the apparatus comprising: a distance measure component configured to compute a path-based distance D ij path = min r ∈ ℛ ij ⁡ ( O ) ⁢ { max 1 ≤ l ≤  r  ⁢ e 1 } between a document i and a document j in an undirected graph (O, E) that includes one or more cycles, where O is a set of N documents including the document i and the document j and E is a set of edges connecting pairs of documents in the undirected graph with each edge having an edge weight, and where ij (O) is the set of all routes between the document i and the document j in the undirected graph , the route r comprises a sequence of edges l=1,. .. , |r|, and e l is the edge weight of the l th edge along the route, the distance measure component comprising an electronic data processing device programmed to compute the path-based distance D ij path by operations including (i) computing a minimum spanning tree over the undirected graph and (ii) computing a path-based distance between the document i and the document j in the minimum spanning tree and (iii) setting the path-based distance D ij path between the document i and the document j in the undirected graph equal to the path-based distance between the document i and the document j in the minimum spanning tree; and a clustering component configured to construct clusters comprising sub-sets of documents of the set of documents O, the clustering component comprising the electronic data processing device further programmed to perform a clustering process including the operations of invoking the distance measure component to compute path-based distances between pairs of documents of the set of documents O and grouping similar documents into said clusters based on the computed path-based distances.