×

System and method for accelerating route search

  • US 10,119,826 B2
  • Filed: 05/19/2015
  • Issued: 11/06/2018
  • Est. Priority Date: 05/19/2015
  • Status: Active Grant
First Claim
Patent Images

1. A method, comprising:

  • determining, by a device, whether a quantity of nodes in a set of nodes satisfies a first threshold;

    clustering, by the device and based on determining that the quantity of nodes satisfies the first threshold, the set of nodes into a plurality of subgroups so that;

    a quantity of nodes in each subgroup is no greater than a second threshold, anda maximum distance between any two nodes of a same subgroup is no greater than a third threshold,the second threshold and the third threshold being determined based on a computing capability of the device;

    determining, by the device, intra group cost information for the plurality of subgroups,the intra group cost information being associated with a shortest path among all pairs of nodes that belong to a same subgroup;

    determining, by the device, inter group cost information,the inter group cost information being associated with a shortest path between nodes of two subgroups; and

    building, by the device and based on determining the intra group cost information and the inter group cost information, a graph of the set of nodes.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×