US 9,805,138 B2Granted

Efficient calculation of all-pair path-based distance measures

AssigneeXerox Corporation

InventorMorteza Haghir Chehreghani

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method is disclosed for computing a path-based distance between a pair of nodes in an undirected graph comprising a set of nodes and a set of edges connecting pairs of nodes in the undirected graph with each edge having an edge weight. The method includes: computing a minimum spanning tree (MST) over the undirected graph; computing a path-based distance between the pair of nodes in the MST; and setting the path-based distance between the pair of nodes in the undirected graph equal to the path-based distance between the pair of nodes in the MST. The path-based distance between the pair of nodes in the MST is computed as the largest edge weight along the only path between the pair of nodes in the minimum spanning tree. A similarity matrix may be constructed from the path-based distances, and used for spectral clustering.

Claims18

Dependent claims

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 el is the edge weight of the lth edge along the route, the distance measure component comprising an electronic data processing device programmed to compute the path-based distance Dijpath 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 Dijpath 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.

28 more elements

A method of performing clustering of documents, the method comprising:

computing path-based distances between pairs of documents in an undirected graph (O, E) where O is a set of N documents and E is a set of edges connecting pairs of documents in the undirected graph with each edge having an edge weight and the path-based distance Dijpath between a document i and a document j is defined as:
D
ij
path
=
min
r
∈
ℛ
ij
⁡
(
0
)
⁢
{
max
1
≤
l
≤

r

⁢
⁢
e
l
}
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 el is the edge weight of the lth edge along the route, the computing of the path-based distance Dijpath comprising:
(i) computing a minimum spanning tree over the undirected graph ;
(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 Dijpath 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
constructing clusters comprising sub-sets of documents of the set of documents O by performing a clustering process operating to group similar documents into said clusters based on the computed path-based distances;
wherein the operations (i), (ii), and (iii) and the clustering are performed by an electronic data processing device programmed to perform the operations (i), (ii), and (iii) and the clustering.

34 more elements

A non-transitory storage medium encoding instructions readable and executable by an electronic data processing device to perform a method for performing clustering of documents, the method comprising:

computing path-based distances
D
ij
path
=
min
r
∈
ℛ
ij
⁡
(
O
)
⁢
{
max
1
≤
l
≤

r

⁢
e
1
}
between pairs of nodes i and j in an undirected graph (O, E) having at least one cycle and comprising a set of nodes O representing documents and a set of edges E connecting pairs of nodes in the undirected graph with each edge having an edge weight, and where ij(O) is the set of all routes between the node i and the node j in the undirected graph , the route r comprises a sequence of edges l=1, . . . , |r|, and el is the edge weight of the lth edge along the route, the computing of the path-based distances comprising:
(i) computing a minimum spanning tree over the undirected graph;
(ii) computing a path-based distance between the pair of nodes in the minimum spanning tree;
and
(iii) setting the path-based distance between the documents represented by the pair of nodes i and j in the undirected graph equal to the path-based distance between the pair of nodes in the minimum spanning tree;
and
constructing clusters comprising sub-sets of the documents represented by the set of nodes O by performing a clustering process operating to group similar nodes into said clusters based on the computed path-based distances.

32 more elements

Dependencies are inferred from the claim text.