Back to results
US 2017/0365071 A1Published application
System and method for compressing graphs via cliques
AssigneePalo Alto Research Center Incorporated
InventorsRyan A. Rossi, Rong Zhou
Life of this patent
Estimating the term…
Loading patent…
Loading patent…
AssigneePalo Alto Research Center Incorporated
InventorsRyan A. Rossi, Rong Zhou
Estimating the term…
Embodiments of the present invention provide a system for fast parallel graph compression based on identifying a set of large cliques, which is used to encode the graph. The system provides both permanently-stored and in-memory graph encoding and reduces the space needed to represent and store a graph, the I/O traffic to use the graph, and the computation needed to perform algorithms involving the graph. The system thereby improves computing technology and graph computation. During operation, the system obtains data indicating vertices and edges of a graph. The system executes a clique-finding method to identify a maximum clique in the graph. The system then removes the clique from the graph, adds the clique to a set of found cliques, and generates a compressed representation of the graph based on the set of found cliques.
A computer-implemented method for compressing a representation of a graph, comprising:
A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for compressing a representation of a graph, the method comprising:
A computing system for compressing a representation of a graph, the system comprising:
Dependencies are inferred from the claim text.