Representations for estimating distance

• US 20030033582A1
• Filed: 01/04/2002
• Published: 02/13/2003
• Est. Priority Date: 05/09/2001
• Status: Abandoned Application

• Current Assignee: Wavemarket Incorporated (Gen Digital Inc.)
• Original Assignee: Wavemarket Incorporated (Gen Digital Inc.)
• Inventors: Klein, Philip Nathan, Ioppe, Igor, Roumeliotis, Tasso
• Application Number:
  US10/039,539
• Publication Number:
  US 20030033582A1
• Time in Patent Office: Days
• US Class Current: 716/4
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 7/00 Image analysis

Abstract

In one aspect, a method and system are provided for preprocessing a weighted planar undirected graph and representing the results of the preprocessing so as to facilitate subsequent approximate distance queries. A representation can be constructed so that an approximate distance from one node to another can be computed quickly. Also, the representation in one embodiment stores information for computing distances in a relatively compact format, thus reducing memory requirements. In another aspect, a method and system are provided which use the representation for rapid computation of distances.

Claims

1. A process for constructing a representation of a network, comprising:

providing an input graph, wherein the input graph comprises nodes and edges;

deriving at least one separator comprising one or more shortest paths comprising a plurality of nodes, wherein said nodes in said shortest paths comprise portal nodes;

deriving a recursive decomposition tree of said input graph, wherein said recursive decomposition tree comprises a plurality of vertices, each vertex having a depth value and each vertex corresponding to one or more nodes;

compiling a first table of data for nodes of said graph wherein said first table has a plurality of first entries each indexed by a node;

deriving, for each node in said first table, a second table from said recursive decomposition tree wherein said second table has a plurality of second entries each indexed according to said depth value of said vertices;

deriving, for each said depth value in said second table, a third table having a plurality of third entries indexed according to said shortest paths of said separator; and

deriving, for each said indexed third entries, corresponding distance values.

2. A process in accordance with claim 1, wherein:

said nodes of said input graph comprise at least one root node; and

said distance values comprise a sequence of said pairs of distance values, wherein a first value in each pair represents portal distance from a node to a portal node and a second value in each pair represents distance from said portal node to a root node.

3. A process according to claim 1, wherein:

said nodes of said input graph comprise at least one root node;

said distance values comprise a sequence of said pairs of values, wherein a first value in each pair represents portal distance from a node to a portal node and a second value in each pair represents an identifier for said portal node; and

further comprising a fourth table having fourth entries indexed by portal node identifiers, wherein said fourth entries comprise data representing distance from each said portal node to a root node.

4. A process according to claim 2, wherein the act of deriving corresponding sequences of pairs of distance values comprises:

deriving a first set of nodes that are closer to the root node than a reference portal node; and

deriving a second set of nodes that are farther from the root node than said reference portal node.

5. A process according to claim 4, further comprising:

determining a distance value comprising a distance between each node of said graph and each node in said set first and second sets of nodes;

determining a height value comprising a distance between each node in said first and second sets of nodes and said root node;

pairing each distance value with each corresponding height value for each node in said first and second sets of nodes;

ordering said first and second sets of nodes in increasing order based on distance of each said node from said root node.

6. A process according to claim 4, wherein:

for each node of the graph, said reference portal node comprises a portal node closest to each said node of the graph;

wherein said process of deriving a first set of nodes comprises;

initializing a first index i to a value of negative one (−

1);

while there is a node z in said shortest path which satisfies a first condition wherein said node z is closer to said root node than node z_i+1 and satisfies a second condition wherein the distance from each said node of said graph to said node z is less than a first threshold factor, assigning node z_i the value of node z;

decrementing the value of said first index i by one (−

1); and

wherein said process of deriving a second set of nodes comprises;

initializing a second index i to a value of one (1);

while there is a node z in said shortest path which satisfies a third condition wherein said node z is farther from said root node than node z<sub>i−

1</sub> and satisfies a fourth condition wherein the distance from each said node of said graph to said node z is less than a second threshold factor, assigning node z₁ the value of node z;

incrementing the value of said second index i by one (1).

7. A process according to claim 6, wherein:

said first threshold value comprises the value of

(1+bar-ε

)<sup>−

1</sup>(d(z_i+1)+h(z₁₊₁)−

h(z_i))

wherein bar-ε

comprises a factor having value between zero and one, and wherein d(z_i+1) comprises a distance from each said node in said graph to node z_i+1, and wherein h(z_i+1) comprises a distance from said root node to node z_i+1 and h(z_i) comprises a distance from the root node to node z_i; and

said second threshold value comprises the value of

(1+bar-ε

)<sup>−

1</sup>(d(z<sub>i−

1</sub>)+h(z₁)−

h(z<sub>i−

1</sub>))

wherein bar-ε

comprises a factor having value between zero and one, and wherein d(z<sub>i−

1</sub>) comprises a distance from each said node in said graph to node z<sub>i−

1</sub>, and wherein h(z<sub>i−

1</sub>) comprises a distance from said root node to node z<sub>i−

1</sub> and h(z_i) comprises a distance from the root node to node z_i.

8. A representation of a network, comprising:

an input graph comprising nodes and edges;

one or more separators comprising one or more shortest paths, each comprising a plurality of nodes, wherein said nodes in said shortest paths comprise portal nodes;

a recursive decomposition tree of said input graph, wherein said tree comprises a plurality of vertices, each vertex having a depth value and each vertex corresponding to one or more nodes;

a first table of data for nodes of said graph wherein said first table has a plurality of first entries each indexed by node;

for each said first entry in said first table, a second table having a plurality of second entries each indexed according to said depth value of said vertices;

for each said second entry in said second table, a third table having a plurality of third entries each indexed according to said shortest paths of said at least one separator;

for each said third entry in said third table, corresponding distance values;

wherein for any node w on a shortest path, there is a node z such that the distance from a corresponding vertex v to node z plus the distance from node z to node w is at most (1+(1−

c/2)ε

₀) times the distance from said vertex v to node w, wherein c is a factor ranging in value from zero to one and ε

₀ is a factor ranging in value between zero and one.

9. A representation accordance to claim 8, wherein:

said nodes of said input graph comprise at least one root node; and

said distance values comprise a sequence of said pairs of distance values, wherein a first value in each pair represents portal distance from a node to a portal node and a second value in each pair represents distance from said portal node to a root node.

10. A representation according to claim 8, wherein:

said nodes of said input graph comprise at least one root node;

said distance values comprise a sequence of said pairs of values, wherein a first value in each pair represents portal distance from a node to a portal node and a second value in each pair represents an identifier for said portal node; and

further comprising a fourth table having fourth entries indexed by portal node identifiers, wherein said fourth entries comprise data representing distance from each said portal node to a root node.

11. A representation in accordance with claim 8, wherein said input graph represents an undirected embedded planar network.

12. A representation in accordance with claim 8, wherein said input graph represents an undirected embedded nearly-planar network.

13. A representation in accordance with claim 8, wherein said input graph represents a roadway network.

14. A representation in accordance with claim 8, whereby a processed representation of an undirected network is adapted for use in route planning.

15. A representation in accordance with claim 8, whereby a processed representation of an undirected network is adapted for use in navigation.

16. A representation in accordance with claim 8, whereby a processed representation of an undirected network is adapted for use in trigger alert applications.

17. A representation according to claim 8, whereby a processed representation of an undirected embedded network is adapted for use in polling server applications.

18. A representation according to claim 8, whereby a processed representation of an undirected embedded graph is adapted for use in point-of-interest query applications.

19. A representation according to claim 8, wherein:

each said node is associated with a vertex in a fourth table indexed by a unique node identifier for each said node and wherein each said vertex has a unique vertex identifier; and

each vertex'"'"'s depth value is stored in a fifth table indexed by said unique vertex identifiers, and wherein said fifth table further comprises data identifying the parent vertex for each said vertex, wherein the parent vertex for each said vertex is one depth value closer to said root node.

20. A representation according to claim 19, wherein said unique vertex identifiers comprise binary values assigned in dependence on the path from said root node to each vertex.

21. A representation according to claim 19, wherein said unique vertex identifiers comprise unique, sequentially-assigned numerical identifiers for each vertex.

22. A process for estimating distance, comprising:

providing an input graph comprising nodes and edges;

deriving at least one separator comprising at least one shortest path;

providing a representation of said graph comprising;

a recursive-decomposition tree of said graph, said recursive-decomposition tree having vertices each of which has a depth value and wherein each node of said graph has at least one corresponding vertex;

a first table comprising first entries indexed by each node in said graph, wherein each said first entry comprises a second table;

said second table comprising second entries indexed by the depth values of vertices corresponding to each node, wherein each said second entry comprises a third table;

said third table comprising third entries indexed by said at least one shortest path,

wherein each said third entry comprises distance data;

obtaining a first endpoint, comprising one of said nodes of said graph, and a second endpoint, comprising a second of said nodes of said graph;

determining the least common ancestor vertex for the first endpoint and the second endpoint, said least common ancestor vertex having one of said depth values;

looking up, in said second table, a second entry indexed according to said least common ancestor'"'"'s depth value;

for each shortest path index in said third table, deriving distance values indexed according to said at least one shortest path;

for each shortest path index in said third table, determining a candidate estimated minimum distance between said first endpoint and said second endpoint using said distance values; and

determining a minimum estimated distance from said first endpoint to said second endpoint from among the set of all said candidate estimated minimum distances determined using said distance values.

23. A process in accordance with claim 22, wherein said separator comprises no more than two shortest paths.

24. A process in accordance with claim 22, wherein a plurality of said first endpoints and a plurality of said second endpoints are in a cluster corresponding to a vertex.

25. A process in accordance with claim 24, wherein said first endpoints and said second endpoints in said cluster are not divided by a separator.

26. A process in accordance with claim 25, wherein distance between one of said first endpoints and one of said second endpoints is derived from a look up table.

27. A system for estimating distances, comprising:

a computing platform comprising a processor and a memory, wherein a processed representation of an undirected network is stored in said memory;

said processed representation comprising nodes and edges;

said processed representation further comprising a recursive-decomposition tree of said network, said tree comprising vertices each having a depth value;

said processed representation further comprising tables comprising distance value data;

said computer adapted to identify a first node and a second node, each said node having corresponding vertices in said tree, and said first node and said second node having a least common ancestor vertex;

said computer configured to determine a minimum estimated distance between said first node and said second node, by deriving from said tables corresponding distance value data indexed according to the depth value of said least common ancestor vertex.

28. A system in accordance with claim 27, wherein said computing platform comprises a server adapted for supporting wireless applications.

29. A system in accordance with claim 27, wherein said computing platform is adapted for use in a kiosk.

30. A system in accordance with claim 27, wherein said computing platform comprises a wireless device.

31. A system in accordance with claim 30, wherein said wireless device comprises a device chosen from the set of cellular phones, personal digital assistants, laptop computers, wireless e-mail devices, and pagers.

32. A system in accordance with claim 27, wherein said computer is located in a vehicle movable over streets represented by said network.

33. A method for estimating distances using a processed network representation, comprising:

step for providing an input graph comprising nodes and edges;

step for storing a processed representation of said graph;

step for determining a first location and a second location, each said location having data associated therewith;

step for determining from said processed representation and said locations'"'"' associated data a minimum estimated distance between said first location and said second location.