System and method for compressing graphs via cliques
US10217241B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 15, 2016 |
| Grant date | Feb 26, 2019 |
| Priority date | — |
| Expiry date | Apr 5, 2037 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M7/70
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.