Patent Issued for Method, apparatus, and computer program product for compression of a graph (USPTO 11023421)

2021 JUN 18 (NewsRx) -- By a News Reporter-Staff News Editor at Insurance Daily News -- According to news reporting originating from Alexandria, Virginia, by NewsRx journalists, a patent by the inventors Timmons, Justin (Boston, MA, US), filed on December 6, 2018, was published online on June 1, 2021.

The assignee for this patent, patent number 11023421, is Liberty Mutual Insurance Company (Boston, Massachusetts, United States).

Reporters obtained the following quote from the background information supplied by the inventors: “Graphs are used to represent massive collections of large network datasets ranging from social networks, web graphs, road networks, internet networks, citation networks, collaboration networks, communication networks, and the like. These large network datasets may have millions or even billions of nodes and edges. As such, the size of these datasets presents resource-intensive computational search space and presents significant obstacles in routing, for example, to and from various nodes.

“Applicant has identified a number of deficiencies and problems associated with conventional compression techniques. Through applied effort, ingenuity, and innovation, many of these identified problems have been solved by developing solutions that are included in embodiments of the present invention, some examples of which are described in detail herein.”

In addition to obtaining background information on this patent, NewsRx editors also obtained the inventors’ summary information for this patent: “In general, embodiments of the present invention provide methods, apparatus, systems, computing devices, computing entities, and/or the like for graph compression and routing.

“In accordance with one aspect, a method is provided. In one embodiment, the method comprises accessing the graph for compression, the graph comprising a node set comprising a plurality of nodes and an edge set comprising a plurality of edges, each edge of the comprising a weighting value; identifying a first intermediate node from the node set; programmatically searching outwardly from the first intermediate node to identify a first decision node in a first direction and a second decision node in a second direction; generating a new edge from the first decision node to the second decision node, wherein the new edge bypasses at least the first intermediate node; assigning a weighting value to the new edge; and store the graph as a compressed graph.

“In accordance with another aspect, a computer program product is provided. The computer program product may comprise at least one computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising executable portions configured to access the graph for compression, the graph comprising a node set comprising a plurality of nodes and an edge set comprising a plurality of edges, each edge of the comprising a weighting value; identify a first intermediate node from the node set; programmatically search outwardly from the first intermediate node to identify a first decision node in a first direction and a second decision node in a second direction; generate a new edge from the first decision node to the second decision node, wherein the new edge bypasses at least the first intermediate node; assign a weighting value to the new edge; and store the graph as a compressed graph.

“In accordance with yet another aspect, an apparatus comprising at least one processor and at least one memory including computer program code is provided. In one embodiment, the at least one memory and the computer program code may be configured to, with the processor, cause the apparatus to access the graph for compression, the graph comprising a node set comprising a plurality of nodes and an edge set comprising a plurality of edges, each edge of the comprising a weighting value; identify a first intermediate node from the node set; programmatically search outwardly from the first intermediate node to identify a first decision node in a first direction and a second decision node in a second direction; generate a new edge from the first decision node to the second decision node, wherein the new edge bypasses at least the first intermediate node; assign a weighting value to the new edge; and store the graph as a compressed graph.”

The claims supplied by the inventors are:

“1. An apparatus for graph compression and routing, the apparatus comprising at least one processor and at least one memory including computer program code, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to: access a graph for compression, the graph comprising a node set comprising a plurality of nodes and an edge set comprising a plurality of edges, each edge of the plurality of edges comprising a corresponding weighting value; identify an intermediate node from the node set; programmatically search outwardly from the intermediate node (a) to identify a first decision node from the plurality of nodes in a first direction, and (b) to identify a second decision node from the plurality of nodes in a second direction, wherein the search defines a path through at least a portion of the graph from the first decision node to the second decision node that passes through the intermediate node; generate a new edge from the first decision node to the second decision node, wherein the new edge bypasses at least the intermediate node; assign a new weighting value to the new edge; and store the graph with the new edge and the new weighting value for the new edge as a compressed graph.

“2. The apparatus of claim 1, wherein the at least one memory and the computer program code are further configured to, with the at least one processor, cause the apparatus to: store data for the intermediate node in the new edge.

“3. The apparatus of claim 2, wherein the at least one memory and the computer program code are further configured to, with the at least one processor, cause the apparatus to: determine a route from a third decision node to a fourth decision node using the compressed graph, wherein the route traverses the new edge.

“4. The apparatus of claim 2, wherein the at least one memory and the computer program code are further configured to, with the at least one processor, cause the apparatus to: decompress the new edge to obtain the data associated with the intermediate node.

“5. The apparatus of claim 1, wherein the graph represents a road network.

“6. A computer-implemented method for graph compression and routing, the method comprising: accessing a graph for compression, the graph comprising a node set comprising a plurality of nodes and an edge set comprising a plurality of edges, each edge of the plurality of edges comprising a corresponding weighting value; identifying an intermediate node from the node set; programmatically searching outwardly from the intermediate node (a) to identify a first decision node from the plurality of nodes in a first direction, and (b) to identify a second decision node from the plurality of nodes in a second direction, wherein the search defines a path through at least a portion of the graph from the first decision node to the second decision node that passes through the intermediate node; generating a new edge from the first decision node to the second decision node, wherein the new edge bypasses at least the intermediate node; assigning a new weighting value to the new edge; and storing the graph with the new edge and the new weighting value for the new edge as a compressed graph.

“7. The computer-implemented of claim 6 further comprising: storing data for the intermediate node in the new edge.

“8. The computer-implemented of claim 7 further comprising: determining a route from a third decision node to a fourth decision node using the compressed graph, wherein the route traverses the new edge.

“9. The computer-implemented of claim 7 further comprising: decompressing the new edge to obtain the data associated with the intermediate node.

“10. The computer-implemented of claim 6 further comprising: providing the route for display, wherein the route comprises at least a portion of the data associated with the intermediate node, but not the new edge.

“11. The computer-implemented of claim 6, wherein the graph represents a road network.

“12. A computer program product comprising a non-transitory computer readable medium having computer program instructions stored therein, the computer program instructions when executed by a processor, cause the processor to: access a graph for compression, the graph comprising a node set comprising a plurality of nodes and an edge set comprising a plurality of edges, each edge of the plurality of edges comprising a corresponding weighting value; identify an intermediate node from the node set; programmatically search outwardly from the intermediate node (a) to identify a first decision node from the plurality of nodes in a first direction, and (b) to identify a second decision node from the plurality of nodes in a second direction, wherein the search defines a path through at least a portion of the graph from the first decision node to the second decision node that passes through the intermediate node; generate a new edge from the first decision node to the second decision node, wherein the new edge bypasses at least the intermediate node; assign a new weighting value to the new edge; and store the graph with the new edge and the new weighting value for the new edge as a compressed graph.

“13. The computer program product of claim 12, wherein the computer program instructions when executed by a processor, further cause the processor to: store data for the intermediate node in the new edge.

“14. The computer program product of claim 13, wherein the computer program instructions when executed by a processor, further cause the processor to: determine a route from a third decision node to a fourth decision node using the compressed graph, wherein the route traverses the new edge.

“15. The computer program product of claim 13, wherein the computer program instructions when executed by a processor, further cause the processor to: decompress the new edge to obtain the data associated with the intermediate node.

“16. The computer program product of claim 12, wherein the computer program instructions when executed by a processor, further cause the processor to: provide the route for display, wherein the route comprises at least a portion of the data associated with the intermediate node, but not the new edge.

“17. The computer program product of claim 12, wherein the graph represents a road network.”

For more information, see this patent: Timmons, Justin. Method, apparatus, and computer program product for compression of a graph. U.S. Patent Number 11023421, filed December 6, 2018, and published online on June 1, 2021. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=11023421.PN.&OS=PN/11023421RS=PN/11023421

(Our reports deliver fact-based news of research and discoveries from around the world.)