| 摘要 |
A method for probabilistically finding the connected components of an undirected graph. The method includes identifying a first edge, having a first and second vertex, and inserting information detailing the first and second vertex of the first edge into a bloom filter associated with a root node of a bloom filter data structure. A first node, connected to the root node, is created, comprising an associated bloom filter containing information associated with the first and second vertex of the first edge. The method includes identifying a second edge, having a first and second vertex, and inserting information detailing the first and second vertex of the second edge into a bloom filter associated with the root node of the bloom filter data structure. A second node, connected to the root node, is created, comprising an associated bloom filter containing information associated with the first and second vertex of the second edge. |
| 主权项 |
1. A method for probabilistically finding the connected components of an undirected graph, the method comprising:
identifying, by one or more computer processors, a first edge of the undirected graph, the first edge having a first vertex and a second vertex; inserting, by one or more computer processors, information detailing the first vertex and the second vertex of the first edge into a bloom filter associated with a root node of a bloom filter data structure; creating, by one or more computer processors, a first node, wherein the first node has a first associated bloom filter containing information associated with the first vertex and the second vertex of the first edge, connected to the root node; identifying, by one or more computer processors, a second edge of the undirected graph, the second edge having a first vertex and a second vertex; inserting, by one or more computer processors, information detailing the first vertex and the second vertex of the second edge into the bloom filter associated with the root node of the bloom filter data structure; creating, by one or more computer processors, a second node, wherein the second node has a second associated bloom filter containing information associated with the first vertex and the second vertex of the second edge, connected to the root node; and searching, by one or more computer processors, the first node having the first associated bloom filter and the second node having the second associated bloom filter, for information associated with a third vertex, wherein the third vertex is a member of a connected component of the undirected graph. |
