Ranking nodes in a graph

• US 20030050909A1
• Filed: 08/27/2001
• Published: 03/13/2003
• Est. Priority Date: 08/27/2001
• Status: Active Grant

• Current Assignee: Xyleme SA (Xyleme, Inc.)
• Original Assignee: Xyleme SA (Xyleme, Inc.)
• Inventors: Preda, Mihai, Abiteboul, Serge
• Granted Patent: US 7,076,483 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for updating importance rank of Internet Web pages. The importance rank is used by an application. The Internet includes Hyper-links interconnecting the Web units. The method includes the step of updating the importance rank of Web pages in the internet in real time during visit of the Web pages, and applying corrective measures in order to render the graph strongly connected. Repeating the step as many times as required. The above updating of importance rank of step (a) is capable of being executed also when the Internet is changing.

Claims

1. A method for updating importance rank of nodes in a dynamically changing large graph;

the importance ranks are used by an application;

the graph includes links interconnecting the nodes;

the method comprising the steps of;

a. updating the importance rank of nodes in the graph substantially in real time during visit of nodes in the graph;

if said graph is not strongly connected, selectively applying corrective measures;

an order of visit of nodes is prescribed by an algorithm;

b. repeating step (a) as many times as required;

said updating of importance rank of step (a) is capable of being executed also when the graph is changing,

and wherein an algorithm that governs the order of visit of nodes is not prescribed by said updating and applying correction steps.

2. The method according to claim 1, wherein said step of updating the importance rank of nodes in the graph substantially in real time during visit of nodes in the graph includes processing for each visited node only links originated from the visited node.

3. The method according to claim 1, wherein said graph being a selected sub-graph of a larger graph.

4. The method according to claim 1, further comprising the steps of:

obtaining other rank of the nodes; and

combining said importance rank and other rank for each node giving rise to a composite rank of the respective node.

6. The method according to claim 1, wherein said updating is confined to selected Web units in the Internet, constituting a sub-graph of the internet.

5. A method for updating importance rank of Internet Web units in an Internet;

the importance ranks are used by an application;

the Internet includes Hyper-links interconnecting the Web units;

the method comprising the steps of;

a) updating the importance rank of Web units in the internet substantially in real time during visit of the Web units; and

applying corrective measures;

an order of visit of nodes is prescribed by an algorithm;

b) repeating step (a) as many times as required;

said updating of importance rank of step (a) is capable of being executed also when the Internet is changing,

and wherein an algorithm that governs the order of visit of nodes is not prescribed by said by said updating and applying correction steps.

7. The method according to claim 5, further comprising the steps of:

obtaining other rank of the Web units; and

combining said importance rank and other rank for each Web unit giving rise to a composite rank of the respective Web unit.

8. The method according to claim 7, wherein said other rank being a text based rank.

9. A method for updating importance rank of nodes in a dynamically changing graph, the importance ranks are used by an application;

the graph includes links interconnecting the nodes;

the method comprising the steps of;

a. storing for each node in the graph at least;

i) short history indication representative of what happened to the node in terms of importance rank since last update;

ii) long history indication representative of what happened to the node in terms of importance rank since a certain point of time in the past;

b. visiting nodes in the graph;

c. for each visited node, updating the importance rank of nodes by performing the steps of;

i) in the case that said visited node has at least one child node, distributing at least substantial part of the short history indication of the visited node to the short history indication of the at least one child node;

ii) recording at least substantial part of the short history indication of the visited node to the long history indication of the visited node and designating that said recording has been accomplished.

d. repeating steps (b) and (c) as many times as required;

said steps (b) to (d) are capable of being executed also when said graph is changing, and if said graph is not strongly connected selectively applying corrective measures.

10. The method according to claim 9, wherein said updating step is performed during said visiting step.

11. The method according to claim 9, wherein said distribution step (c)(i) includes, distributing at least substantial part of the short history indication of the visited node to the short history indication of the at least one child node in equal shares.

12. The method according to claim 9, wherein said distribution step (c)(i) includes, distributing at least substantial part of the short history indication of the visited node to the short history indication of the at least one child node in non-equal shares according to a pre-defined criterion.

13. The method according to claim 9, further comprising the step of:

configuring a time interval of said long history indication.

14. The method according to claim 9, further comprising the step of:

maintaining several time intervals for said long history indication.

15. The method according to claim 9, wherein said graph being a selected sub-graph of a larger graph.

16. The method according to claim 9, further comprising the steps of:

obtaining other rank of the nodes; and

combining said importance rank and other rank for each node giving rise to a composite rank of the respective node.

17. The method according to claim 9, wherein a short history indication value constituting said short history indication and long history indication value constituting said long history indication;

and said distributing step stipulated in (c)(i), includes;

(1) distributing a substantial part of the short history indication value of the visited node to a short history indication value of the at least one child node; and

(2) distributing, a remaining part of the short history indication value of the visited node to a respective short history indication value of nodes in the graph, in equal shares;

said recording step stipulated in (c)(ii), includes;

(3) summing the short history indication value of the visited node and the long history indication value of the visited node, giving rise to a sum that constitutes the long history indication value, and the step of designating that said recording has been accomplished, includes;

resetting said short history indication value.

18. The method according to claim 10, wherein said graph being Internet graph, nodes being Web units and links being Hyper-links.

19. A method for calculating the importance rank of nodes in a dynamically changing graph, the importance ranks are used by an application;

the graph includes links interconnecting the nodes;

the method comprising the steps of;

a) providing for each node in the graph at least;

(i) short history indication representative of what happened to the node in terms of importance rank since last update;

(ii) long history indication representative of what happened to the node in terms of importance rank since a certain point of time in the past;

b) selecting node in the graph;

c) for selected node, computing the importance rank as a function of at least one of said short history indication and long history indication;

d) repeating steps (b) and (c) as many times as required.

20. The method according to claim 19, wherein a short history indication value constituting said short history indication and long history indication value constituting said long history indication;

said function being the sum of said short history indication value and long history indication value.

21. The method according to claim 20, wherein the computing step includes normalizing the so calculated sum.

22. The method according to claim 20, wherein the computing step includes applying a bias factor to the so obtained sum according to a predetermined criterion.

23. The method according to claim 19, wherein said graph includes the Internet or portion thereof, said links being hyperlinks, said nodes being Web units, and wherein said application includes a search engine, and further comprising the step of:

placing a query;

said step (b) includes selecting Web units in response to said query; and

further comprising;

sorting selected Web units on the basis of at least their importance rank; and

displaying information that pertains to the Web units, the information includes Web units internet address (URL), in a display order according to the respective Web units sorted importance rank.

24. The method according to claim 23, further comprising the steps of:

obtaining other rank of the Web units;

combining said importance rank and other rank for selected node, giving rise to a composite rank of the respective selected Web unit;

said sorting step includes;

sorting the selected Web units on the basis of at least their respective composite rank; and

displaying information that pertains to the Web units, the information includes Web units internet address (URL), in a display order according to the respective Web units sorted composite rank.

25. The method according to claim 19, wherein said graph includes the internet or portion thereof, said links being hyperlinks, said nodes being Web units, and further including:

sorting visited Web units on the basis of at least their importance rank; and

said application modifying visiting strategy which prescribe which Web units are selected in said step (b), such that the higher the importance rank the more often the Web unit is visited.

26. A system for updating importance rank of nodes in a dynamically changing large graph;

the importance ranks are used by an application;

the graph includes links interconnecting the nodes;

the system comprising;

at least one processor and associated storage configured to perform the operations that include;

update the importance rank of nodes in the graph substantially in real time during visit of nodes in the graph; and

if said graph is not strongly connected, said processor is configured to selectively applying corrective measures;

the processor is configured to update said importance rank also when the graph is changing,

and wherein an algorithm that governs the order of visiting of nodes is not prescribed by the processor update and corrective measures operations.

27. A system for updating importance rank of Web units in an Internet;

the importance ranks are used by an application;

the Internet includes Hyper-links interconnecting the Web units;

the system comprising;

at least one processor and associated storage configured to perform the operations that include;

update the importance rank of Web units in the graph substantially in real time during visit of Web units in the graph; and

selectively applying corrective measures;

the processor is configured of updating said importance rank also when the Internet is changing,

and wherein an algorithm that governs the order of visiting of Web units is not prescribed by the processor update and corrective measures operations.

28. A system for updating importance rank of nodes in a dynamically changing graph, the importance ranks are used by an application;

the graph includes links interconnecting the nodes;

the system comprising;

at least one processor and associated storage, the storage storing for each node in the graph at least;

short history indication representative of what happened to the node in terms of importance rank since last update;

long history indication representative of what happened to the node in terms of importance rank since a certain point of time in the past;

the at least one processor being configured to perform the operations that include;

a) receiving for each visited node a visiting node identification and identifications to its respective at least one child node, if any;

b) for each visited node, updating the importance rank of nodes in said by performing the steps of;

(i) in the case that said visited node has at least one child node, distributing at least substantial part of the short history indication of the visited node to the short history indication of the at least one child node;

(ii) recording at least substantial part of the short history indication of the visited node to the long history indication of the visited node and designating that said recording has been accomplished.

c) repeating operations (a) and (b) as many times as required;

said operations (a) to (c) are capable of being executed also when said graph is changing,

and if said graph is not strongly connected, said at least one processor being configured to selectively applying corrective measures.

29. The system according to claim 28, wherein said graph being Internet graph, nodes being Web units and links being Hyper-links.

30. The system according to claim 28, wherein said short history indications being an array of cells each holding a real value signifying a short history indication value of a respective node in the graph, and said long history indications being an array of cells each holding a real value signifying a long history indication value of the respective node in the graph;

31. A system for calculating the importance rank of nodes in a dynamically changing graph, the importance ranks are used by an application;

the graph includes links interconnecting the nodes;

the system comprising;

at least one processor and associated storage, the storage storing for each node in the graph at least;

short history indication representative of what happened to the node in terms of importance rank since last update;

long history indication representative of what happened to the node in terms of importance rank since a certain point of time in the past;

the at least one processor being configured to perform the operations that include;

a. receiving selected nodes;

b. for the selected node, computing the importance rank as a function of at least one of said short history indication and long history indication.

32. The system according to claim 31, wherein a short history indication value constituting said short history indication and long history indication value constituting said long history indication;

said function being the sum of said short history indication value and long history indication value.

33. The system according to claim 32, wherein the at least one processor being further configured to normalize the so calculated sum.

34. The system according to claim 31, wherein said graph includes the Internet or portion thereof, said links being hyperlinks, said nodes being Web units, and wherein said application includes a search engine, and wherein said at least one processor being further configured to:

receiving selected Web units in response to said query and providing their calculated importance rank.

35. The system according to claim 33, wherein said at least one processor being further configured to sorting the selected Web units on the basis of at least their importance rank.

36. A storage medium storing a computer implemented code for performing method steps for updating importance rank of nodes in a dynamically changing large graph;

the importance ranks are used by an application;

the graph includes links interconnecting the nodes;

the method steps include;

a) updating the importance rank of nodes in the graph substantially in real time during visit of nodes in the graph;

if said graph is not strongly connected, selectively applying corrective measures;

an order of visit of nodes is prescribed by an algorithm;

b) repeating step (a) as many times as required;

said updating of importance rank of step (a) is capable of being executed also when the graph is changing,

and wherein an algorithm that governs the order of visit of nodes is not prescribed by said updating and applying correction steps.

37. A storage medium storing a computer implemented code for performing method steps for updating importance rank of Internet Web units in an Internet;

the importance ranks are used by an application;

the Internet includes Hyper-links interconnecting the Web units;

the method includes the steps of;

a) updating the importance rank of Web units in the internet substantially in real time during visit of the Web units; and

applying corrective measures;

an order of visit of nodes is prescribed by an algorithm;

b) repeating step (a) as many times as required, said updating of importance rank of step (a) is capable of being executed also when the internet is changing,

and wherein an algorithm that governs the order of visit of nodes is not prescribed by said by said updating and applying correction steps.

38. A storage medium storing a computer implemented code for performing method steps for updating importance rank of nodes in a dynamically changing graph, the importance ranks are used by an application;

the graph includes links interconnecting the nodes;

the method include the steps of;

a) storing for each node in the graph at least;

(i) short history indication representative of what happened to the node in terms of importance rank since last update;

(ii) long history indication representative of what happened to the node in terms of importance rank since a certain point of time in the past;

b) visiting nodes in the graph;

c) for each visited node, updating the importance rank of nodes by performing the steps of;

(i) in the case that said visited node has at least one child node, distributing at least substantial part of the short history indication of the visited node to the short history indication of the at least one child node;

(ii) recording at least substantial part of the short history indication of the visited node to the long history indication of the visited node and designating that said recording has been accomplished.

d) repeating steps (b) and (c) as many times as required;

said steps (b) to (d) are capable of being executed also when said graph is changing,

and if said graph is not strongly connected, selectively applying corrective measures.

39. A storage medium storing a computer implemented code for performing method steps for calculating the importance rank of nodes in a dynamically changing graph, the importance ranks are used by an application;

the graph includes links interconnecting the nodes;

the method comprising the steps of;

(a) providing for each node in the graph at least;

(i) short history indication representative of what happened to the node in terms of importance rank since last update;

(ii) long history indication representative of what happened to the node in terms of importance rank since a certain point of time in the past;

b) selecting node in tie graph;

c) for selected node, computing the importance rank as a function of at least one of said short history indication and long history indication;

repeating steps (b) and (c) as many times as required.