Back to results
US 10,706,103 B2Granted
System and method for hierarchical distributed processing of large bipartite graphs
AssigneeMicrosoft Technology Licensing, LLC
InventorsManoj Kumar Agarwal, Rohit Jain, Amey Satish Gade
Life of this patent
Estimating the term…
Abstract
Systems, methods, and apparatuses for implementing a distributed, hierarchical, and iterative data graph processing strategy are disclosed. A large data graph is partitioned and the partitions are clustered. Sets of keys and hashes are generated for each cluster and distributed to a plurality of processing machines. The processing machines recreate the partitions, based on received hashes and keys of the clusters of the first partitions, and the graph. Thereafter, the partitioning, clustering and processing is repeatable for the recreated graphs. The disclosed strategy enables processing of large and dynamic data graphs, including bipartite query-Uniform Resource Locator graphs.
Claims19
A method of processing a bipartite graph, the method comprising:
- partitioning a bipartite graph into a plurality of first partitions;
- generating one or more clusters of nodes of each first partition;
- generating a set of keys for each cluster of nodes of each first partition, each key being based on similarities between nodes of the cluster for which the key was generated;
- encoding each cluster of nodes of each first partition with a hash;
- distributing the hashes and the keys to processing machines of a network, based on the keys;
- recreating, at the processing machines, both the first partitions, based on received hashes and keys of the clusters of the first partitions, and the bipartite graph;
- partitioning, at the processing machines, the recreated bipartite graphs into second partitions;
- generating one or more clusters of nodes of each second partition;
- generating a set of keys for each cluster of nodes of each second partition, each key being based on similarities between nodes of the cluster for which the key was generated;
- encoding each cluster of nodes of each second partition with a hash;
- recreating, at the processing machines, the second partitions, based on the hashes and keys of the clusters of the second partitions;
- and
- merging the recreated second partitions using a hierarchical merge process to yield a recreated bipartite graph.
10 more elements
A graph processing method, comprising:
- dividing a bipartite query-URL graph of nodes that include queries and URLs into a plurality of first order subgraphs;
- generating one or more first order clusters for each first order subgraph;
- distributing first order hashes and first order keys for each first order cluster, the first order keys being based on similarities between nodes of the first order cluster, and being generated based on the URLs;
- recreating the first order subgraphs, based on the received first order hashes and first order keys;
- recreating the input graph, based on the recreated first order subgraphs;
- processing a recreated input graph by
- dividing the recreated input graphs to yield next order subgraphs;
- generating one or more second order clusters for each next order subgraph;
- generating a next order key for each next order cluster, the next order keys being based on similarities between nodes of the next order cluster;
- encoding each next order cluster with a hash;
- recreating both the next order subgraphs, based on the next order hashes and next order keys, and the input graph, based on the recreated next order partitions;
- and
- merging the recreated next partitions using a hierarchical merge process to yield a recreated bipartite graph.
10 more elements
A system, comprising:
- a first computing machine that
- divides an input graph of nodes into a plurality of first order subgraphs,
- generates one or more first order clusters for each first order subgraph, and
- distributes first order hashes and sets of first order keys for each first order cluster, the first order keys being based on similarities between nodes of the first order cluster;
- and
- a group of one or more second computing machines that
- recreate the first order subgraphs, based on the received first order hashes and first order keys distributed from the first computing machine,
- recreate the input graph, based on the recreated first order subgraphs,
- divide the recreated input graphs to yield second order subgraphs,
- generate one or more second order clusters for each second order subgraph,
- generate a second order key for each second order cluster, the second order keys being based on similarities between nodes of the second order cluster,
- encode each second order cluster with a hash,
- recreate both the second order subgraphs, based on the second order hashes and second order keys, and the input graph, based on the recreated second order partitions, and
- provide search results in response to a search query utilizing data mined from at least the recreated input graph.
11 more elements
Dependencies are inferred from the claim text.