System and method employing random walks for mining web page associations and usage to optimize user-oriented web page refresh and pre-fetch scheduling

US 6,549,896 B1
Filed: 11/09/2000
Issued: 04/15/2003
Est. Priority Date: 04/07/2000
Status: Active Grant

First Claim

Patent Images

1. On a computer network having a set of Web pages V and a set of links E between those Web pages represented as an undirected neighborhood graph G^N(V^N,E^N), the computer network further including seed Web pages v_aand v_bin V, a method executable on the computer network for estimating associations between v_aand v_band other Web pages v_iε

V, the method comprising the steps of;

constructing a directed random walk graph by creating a new v_i′

in V for each v_iε

V^N, and creating two directed edges e′

_2×

k=<

v_i′

,v_j′

) and e′

_2×

k−

1=<

v_j′

,v_i′

>

in E for each e_k=<

v_i,v_j>

ε

E^Nwherein both v_iand V_jare in V^N, computing a penalty value penalty(v_i′

) for all vertices v_i′

ε

V, and constructing a |V|×

|V| transition matrix T, where T[j,i] represents a transition value for each directed edge in E denoting a likelihood of moving to vertex v_ifrom vertex v_j; and

calculating a steady state distribution convergence vector t of T, wherein for each v_iε

V, t[i] represents the association between the seed Web pages and v_i.

View all claims

2 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A method for estimating an association between the media objects and the seed Web page accessed by a user. The method is employed in the context of a Web space on a network having Web pages and links between those Web pages modeled as a directed graph. Each Web page comprises a set of media objects and a page author. For each object a size, a user preference and a page author preference are determined. The network has an available pre-fetch bandwidth. The method calculates a weight for each Web object by applying preference rules defined by and user preference and page author preference to the contents of the set of media objects. Next, a random walk graph is generated, and object gains are calculated by finding a steady state distribution of the random walk graph. The object gain represents an association between the object and the seed Web page.

168 Citations

42 Claims

1. On a computer network having a set of Web pages V and a set of links E between those Web pages represented as an undirected neighborhood graph G^N(V^N,E^N), the computer network further including seed Web pages v_aand v_bin V, a method executable on the computer network for estimating associations between v_aand v_band other Web pages v_iε
- V, the method comprising the steps of;
  
  constructing a directed random walk graph by creating a new v_i′
  
  in V for each v_iε
  
  V^N, and creating two directed edges e′
  
  _2×
  
  k=<
  
  v_i′
  
  ,v_j′
  
  ) and e′
  
  _2×
  
  k−
  
  1=<
  
  v_j′
  
  ,v_i′
  
  >
  
  in E for each e_k=<
  
  v_i,v_j>
  
  ε
  
  E^Nwherein both v_iand V_jare in V^N, computing a penalty value penalty(v_i′
  
  ) for all vertices v_i′
  
  ε
  
  V, and constructing a |V|×
  
  |V| transition matrix T, where T[j,i] represents a transition value for each directed edge in E denoting a likelihood of moving to vertex v_ifrom vertex v_j; and
  
  calculating a steady state distribution convergence vector t of T, wherein for each v_iε
  
  V, t[i] represents the association between the seed Web pages and v_i.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
- - 2. A method as recited in claim 1, the step of computing a penalty value penalty(v_i′
    - ) for all vertices v_i′
      
      ε
      
      V comprising the steps of;
3. A method as recited in claim 2, the step of constructing a |V|×
- |V| transition matrix T comprising the steps of;
  
  resetting T[j,i]=0.0 for all vertices υ
  
  _i′
  
  ε
  
  V and for all (υ
  
  _i′
  
  ,υ
  
  _j′
  
  )∉
  
  E; and
  
  solving the following set of linear equations for all vertices υ
  
  _i′
  
  ε
  
  V, $L (υ_{i}^{'}) = {\sum_{(υ_{i}^{'}, υ_{j}^{'}) \in ɛ} T [j, i] = 1.0} ⋃ {T [j, i] x penalty (υ_{j}^{'}) = T [k, i] x penalty (υ_{k}^{'})  (υ_{i}^{'}, υ_{j}^{'}) \in E and (υ_{i}^{'}, υ_{k}^{'}) \in E} .$
4. A method as recited in claim 3, the step of calculating a steady state distribution (convergence vector) t of T comprising solving a linear equation (I−
- T)t=0, where I is a unit matrix, and $\sum_{1 \leq i \leq \langle v_{w} \rangle} t [i] = 1.0 .$
5. A method as recited in claim 2, the computer network further including a set of seed Web pages |S|≧
- 2 in V, the step of computing a penalty value penalty(v_i′
  
  ) for all vertices v_i′
  
  ε
  
  V comprising computing the penalty value as $penalty (v_{i}^{'}) = \sum_{u_{j} \in S} sdist (v_{i}^{'}, v_{j}^{'}) .$
6. A method as recited in claim 2, the computer network further including a set of seed Web pages |S|≧
- 2 in V, the step of computing a penalty value penalty(v_i′
  
  ) for all vertices v_i′
  
  ε
  
  V comprising computing the penalty value as
7. A method as recited in claim 6, further including the step of defining a relevant neighborhood of G^N(V^N,E^N) for constructing the random walk graph as a set of vertices, V^N=V_G_^U(S,d), that are reachable either from the vertices in S in d edge traversals such that $\forall$
- v1∈
  
  VGu
  
  (S,d)
  
  
  
  vj∈
  
  S
  
  reachableGu
  
  (vj,vi,d).
8. A method as recited in claim 1, further including the step of defining a relevant neighborhood of G^N(V^N,E^N) for constructing the random walk graph as a set of vertices, V^N=V_G_^u(v_a,v_b,d), that are reachable either from v_aor v_bin d edge traversals such that ∀
- v_iε
  
  V_G_^u(v_a,v_b,d) reachable_G_^u(v_a,v_i,d) ν
  
  reachable_G_^u(v_b,v_i,d).
9. A method as recited in claim 1, each Web page v_iε
- V having a known relevance value for a particular topic relevance(v,topic), the method further including the step of adjusting the penalty value penalty(v_i′
  
  ) for all vertices v_i′
  
  ε
  
  V by dividing penalty(v_i′
  
  ) by relevance(v,topic).
10. A method as recited in claim 1, further including the step of pre-fetching Web pages into a memory in decreasing order of t[i].

11. On a computer network having a set of Web pages V and a set of links between those Web pages E modeled as a directed graph G(V,E), each Web page v_iε
- V comprising a pair <
  
  O_v,a_v>
  
  , where O_vis a set of media objects including a main HTML file and a_vis a page author, and where each object oε
  
  O_vhas a known end-user preference upref(u) for an end-user u and a page author preference apref(a_v) for a page author a_v, an end-user u accessing at a seed Web page v_c, a method executable on the computer network for estimating an association between the media objects and the seed Web page, the method comprising the steps of;
  
  calculating a page preference weight pref(u,v) for each Web page v_iby applying preference rules defined by upref(u) and apref(a_v) to the contents of O_vcalculating an object preference weight pref(u,o,v) for each object oε
  
  O_vby applying the preference rules defined by upref(u) and apref(a_v) to the contents of O_v;
  
  generating a random walk graph G_whaving a set of vertices V_wand a set of edges E_w;
  
  calculating a page gain gain(u,v) by finding a steady state distribution convergence vector of the random walk graph; and
  
  calculating an object gain gain(u,o) for each object as $gain (u, o) = \sum_{o \in O_{v}} gain (u, v) \times pref (u, o, v),$ wherein the object gain represents an association between the object and the seed Web page.
- View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
- - 12. A method as recited in claim 11, the step of generating a random walk graph G_whaving a set of vertices V_wand a set of edges E_wcomprising the steps of:
13. A method as recited in claim 12, wherein s(u,v_j) is a known stickiness value for each Web page v_jε
- V.
14. A method as recited in claim 12, wherein s(u,v_j) is assigned a unit value for each edge e_j=<
- v_a,v_b>
  
  in E.
15. A method as recited in claim 12, wherein s(u,v_j) is assigned a larger value than the unit value for each edge e_j=<
- v_a,v_b>
  
  in E that crosses a domain boundary.
16. A method as recited in claim 12, the step of calculating a page gain gain(u,v) by finding a steady state distribution (convergence vector) of the random walk graph comprising the steps of:
- finding a shortest distance shortest (v_c, v_i) from vertex v_cto all vertices v_iε
  
  V while taking into account the edge weight using a shortest path algorithm;
  
  for each vertex vε
  
  V_w, calculating a penalty penalty(u,v)=shortest(v_c,v_i)/(pref(u,v)+1), and calculating a unit probability unit(u,v) by solving $\sum_{〈 v, v_{i} 〉 \in E_{w}} \frac{unit (u, v)}{penalty (u, v_{i})} = 1;$ calculating $prob (u) (v_{j} | v_{i}) = \frac{unit (u, v_{j})}{penalty (u, v_{i})}$
  
  for each edge e=ε
  
  <
  
  v_i,v_j>
  
  ε
  
  V_w; and
  
  calculating gain(u,v) by finding a steady state distribution (convergence vector) t of T, wherein for each v_iε
  
  V, t[i] represents the association between the seed Web pages and v_i, where T is a matrix of transition values prob(u)(v_j|v_i).
17. A method as recited in claim 16, the step of calculating gain(u,v) by finding a steady state distribution (convergence vector) t of T comprising solving a linear equation (I−
- T)t=0, where I is a unit matrix, and Σ
  
  _{1≦
  
  i≦
  
  |v}_w_| gain(u,v)=1.0.
18. A method as recited in claim 17, wherein each object oε
- O_vhas a known size size(o) and, having an available pre-fetch bandwidth P_uand a pre-fetch duration δ
  
  t in which a server may pre-fetch objects into a memory, the method further includes the step of identifying a set of objects O_shighly associated with the end-user or seed Web page, the step comprising;
  
  defining a cost of each object as cost(o)=size(o); and
  
  identifying a subset O_sof O_vsuch that Σ
  
  _oε
  
  O_scost(o)≦
  
  P_u×
  
  δ
  
  t and Σ
  
  _oε
  
  O_sgain(u,o) is maximized.
19. A method as recited in claim 18, further including the step of pre-fetching or refreshing objects from O_sinto the memory.
20. A method as recited in claim 18, where each object oε
- O_vhas a known expiration time expire(o), the method further including the step of refining the set of objects O_sby removing those objects that will expire before their earliest time to view, the step comprising;
  
  finding a shortest path shortest_path(v_c,v_i) from vertex v_cto all vertices v_iε
  
  V while taking into account the edge weight using a shortest path algorithm;
  
  calculating a measure of an earliest time that a page p may be accessed as earliest(u,p)=shortest_path(v_c, v_p);
  
  calculating a measure of an earliest time that an object o may be needed as earliest(u,o)=min{earliest(u,p)|pε
  
  pages(o)}; and
  
  eliminating those objects from O_vin which expire(o)<
  
  earliest(u,o) before identifying the set of objects O_s.
21. A method as recited in claim 17, wherein each object oε
- O_vhas a known size size(o) and, having an available pre-fetch bandwidth P_uand a pre-fetch duration δ
  
  t in which a server may pre-fetch objects into a memory, and given a set of users U or seed Web pages, the method further includes the step of identifying a set of objects O_shighly associated with the set of users or seed Web pages, the step comprising;
  
  calculating an object gain gain(o) for each object as $gain (o) = \sum_{u \in U} \sum_{o \in O_{v}} gain (u, v) \times pref (u, o, v),$ wherein the object gain represents an association between the object and the set of end-users or seed Web pages;
  
  defining a cost of each object as cost(o)=size(o); and
  
  identifying a subset O_sof O_vsuch that $\sum_{o \in O_{s}} cost (o) \leq P_{U} \times δ t and \sum_{o \in O_{s}} gain (o)$ is maximized.

22. On a computer network having a set of Web pages V and a set of links E between those Web pages, a system for estimating associations between seed Web pages v_aand v_band other Web pages v_iε
- V, comprising;
  
  memory for storing a location of the seed Web pages v_aand v_band the other Web pages v_iin V; and
  
  a processor programmed for modeling the computer network as an undirected neighborhood graph G^N(V^N,E^N), and programmed for constructing a directed random walk graph by creating a new v_i′
  
  in V for each v_iε
  
  V^N, and creating two directed edges e′
  
  _2×
  
  k=<
  
  v_i′
  
  ,v_j′
  
  > and
  
  e′
  
  _2×
  
  k+1=<
  
  v_j′
  
  ,v_i′
  
  >
  
  in E for each e_k=<
  
  v_i,v_j>
  
  ε
  
  E^Nwherein both v_iand v_jare in V^N, computing a penalty value penalty(v_i′
  
  ) for all vertices v_i′
  
  ε
  
  V, and constructing a |V|×
  
  |V| transition matrix T, where T[j,i] represents a transition value for each directed edge in E denoting a likelihood of moving to vertex v_ifrom vertex v_j; and
  
  calculating a steady state distribution convergence vector t of T, wherein for each vε
  
  V, t[i] represents the association between the seed Web pages and V_i.
- View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31)
- - 23. A system as recited in claim 22, the processor further programmed for computing a penalty value penalty(v_i′
    - ) for all vertices v_i′
      
      ε
      
      V by;
24. A system as recited in claim 23, the processor further programmed for constructing a |V|×
- |V| transition matrix T by;
  
  resetting T[j,i]=0.0 for all vertices υ
  
  _i′
  
  ε
  
  V and for all (υ
  
  _i′
  
  ,υ
  
  _j′
  
  )∉
  
  E; and
  
  solving the following set of linear equations for all vertices v_i′
  
  ε
  
  V, $L (υ_{i}^{'}) = {\sum_{(υ_{i}^{'}, υ_{j}^{'}) \in ɛ} T [j, i] = 1.0} ⋃ {T [j, i] x penalty (υ_{j}^{'}) = T [k, i] x penalty (υ_{k}^{'})  (υ_{i}^{'}, υ_{j}^{'}) \in E and (υ_{i}^{'}, υ_{k}^{'}) \in E} .$
25. A system as recited in claim 24, the processor further programmed for calculating a steady state distribution (convergence vector) t of T by solving a linear equation (I−
- T)t=0, where I is a unit matrix, and $\sum_{1 \leq i \leq v_{w} \rangle} t [i] = 1.0 .$
26. A system as recited in claim 23, the computer network further including a set of seed Web pages |S|≧
- 2 in V, the processor further programmed for computing a penalty value penalty(v_i′
  
  ) for all vertices $v_{i}^{'} \in V as penalty (v_{i}^{'}) = \sum_{u_{j} \in S} sdist (v_{i}^{'}, v_{j}^{'}) .$
27. A system as recited in claim 23, the computer network further including a set of seed Web pages |S|≧
- 2 in V, the processor further programmed for computing a penalty value penalty(v_i′
  
  ) for all vertices v_iε
  
  V as
28. A system as recited in claim 27, the processor further programmed for defining a relevant neighborhood of G^N(V^N, E^N) for constructing the random walk graph as a set of vertices, V^N=V_G_^U(S,d), that are reachable either from the vertices in S in d edge traversals such that $\forall$
- v1∈
  
  VGu
  
  (S,d)
  
  
  
  vj∈
  
  S
  
  reachableGu
  
  (vj,vi,d).
29. A system as recited in claim 22, the processor further programmed for defining a relevant neighborhood of G^N(V^N,E^N) for constructing the random walk graph as a set of vertices, V^N=V_G_^u(v_a,v_b,d), that are reachable either from v_aor v_bin d edge traversals such that ∀
- v_iε
  
  V_G_^u(v_a,v_b,d)reachable_G_^u(v_a,v_i,d)v reachable_G_^u(v_b,v_i,d).
30. A system as recited in claim 22, each Web page v_iε
- V having a known relevance value for a particular topic relevance(v,topic), the processor further programmed for adjusting the penalty value penalty(v_i′
  
  ) for all vertices v_i′
  
  ε
  
  V by dividing penalty(v_i′
  
  ) by relevance(v,topic).
31. A system as recited in claim 22, the processor further programmed for pre-fetching Web pages into the memory in decreasing order of t[i].

32. On a computer network having a set of Web pages V and a set of links between those Web pages E, each Web page v_iε
- V comprising a pair <
  
  O_va_v>
  
  , where O_vis a set of media objects including a main HTML file and a_vis a page author, a system for estimating an association between the media objects and a seed Web page v_ccorresponding to a current location of an end-user u, comprising;
  
  memory for storing, for each object oε
  
  O_v, a known end-user preference upref(u) for the end-user u, a page author preference apref(a_v) for the page author a_v, and a location of the seed Web page v_c; and
  
  a processor programmed for modeling the computer network as a directed graph G(V,E), and programmed for calculating a page preference weight pref(u,v) for an end user u for each Web page v_iby applying preference rules defined by upref(u) and apref(a_v) to the contents of O_v, calculating an object preference weight pref(u,o,v) for each object oε
  
  O_vby applying the preference rules defined by upref(u) and apref(a_v) to the contents of O_v, generating a random walk graph G_whaving a set of vertices V_wand a set of edges E_w, calculating a page gain gain(u,v) by finding a steady state distribution convergence vector of the random walk graph, and calculating an object gain gain(u,o) for each object as $gain (u, o) = \sum_{o \in O_{v}} gain (u, v) \times pref (u, o, v),$ wherein the object gain represents an association between the object and the end-user or seed Web page.
- View Dependent Claims (33, 34, 35, 36, 37, 38, 39, 40, 41, 42)
- - 33. A system as recited in claim 32, the processor further programmed for generating a random walk graph G_whaving a set of vertices V_wand a set of edges E_wby:
34. A system as recited in claim 33, wherein s(u,v_j) is a known stickiness value for each Web page v_jε
- V.
35. A system as recited in claim 33, wherein s(u,v_j) is assigned a unit value for each edge e_j=<
- v_a,v_b>
  
  in E.
36. A system as recited in claim 33, wherein s(u,v_j) is assigned a larger value than the unit value for each edge e_j=<
- v_a, v_b>
  
  in E that crosses a domain boundary.
37. A system as recited in claim 33, the processor further programmed for calculating a page gain gain(u,v) by finding a steady state distribution (convergence vector) of the random walk graph by:
- finding a shortest distance shortest (v_c, v_i) from vertex v_cto all vertices v_iε
  
  V while taking into account the edge weight using a shortest path algorithm;
  
  for each vertex vε
  
  V_w, calculating a penalty penalty(u,v)=shortest(v_c,v_i)/(pref(u,v)+1), and calculating a unit probability unit(u,v) by solving $\sum_{〈 v, v_{i} 〉 \in E_{w}} \frac{unit (u, v)}{penalty (u, v_{i})} = 1;$ calculating $prob (u) (v_{j} | v_{i}) = \frac{unit (u, v_{j})}{penalty (u, v_{i})}$
  
  for each edge e=ε
  
  <
  
  v_i,v_j>
  
  ε
  
  V_w; and
  
  calculating gain(u,v) by finding a steady state distribution (convergence vector) of T, where T is a matrix of transition values prob(u)(v_j|v_i), and $\sum_{1 \leq i \leq {}_{i}^{'}v_{u} |} gain (u, v) = 1.0 .$
38. A system as recited in claim 37, the processor further programmed for calculating gain(u,v) by finding a steady state distribution (convergence vector) t of T by solving a linear equation (I−
- T)t=0, where I is a unit matrix, and $\sum_{1 \leq i \leq \langle v_{u} \rangle} gain (u, v) = 1.0 .$
39. A system as recited in claim 38:
- the memory for storing a known size size(o) for each object oε
  
  O_v; and
  
  the processor having an available pre-fetch bandwidth P_uand a pre-fetch duration δ
  
  t for pre-fetching objects into a memory, and further programmed for identifying a set of objects O_shighly associated with the end-user or seed Web page by defining a cost of each object as cost(o)=size(o), and identifying a subset O_sof O_vsuch that Σ
  
  _oε
  
  O_scost(o)≦
  
  P_u×
  
  δ
  
  t and Σ
  
  _oε
  
  O_sgain(u,o) is maximized.
40. A system as recited in claim 39, the processor further programmed for pre-fetching or refreshing objects from O_sinto the memory.
41. A system as recited in claim 39:
- the memory for storing a known expiration time expire(o) for each object oε
  
  O_v; and
  
  the processor further programmed for refining the set of objects O_sby removing those objects that will expire before their earliest time to view by finding a shortest path shortest_path(v_c,v_i) from vertex v_cto all vertices v_iε
  
  V while taking into account the edge weight using a shortest path algorithm, calculating a measure of an earliest time that a page p may be accessed as earliest(u,p)=shortest_path(v_c,v_p), calculating a measure of an earliest time that an object o may be needed as earliest(u,o)=min{earliest(u,p)|pε
  
  pages(o)}, and eliminating those objects from O_vin which expire(o)<
  
  earliest(u,o) before identifying the set of objects O_s.
42. A system as recited in claim 38:
- the memory for storing a known size size(o) for each object oε
  
  O_v; and
  
  the processor having an available pre-fetch bandwidth P_Uand a pre-fetch duration δ
  
  t in which a server may pre-fetch objects into a memory, and further programmed for identifying a set of objects O_shighly associated with a set of users U or seed Web pages by calculating an object gain gain(o) for each object as $gain (o) = \sum_{u \in U} \sum_{o \in O_{v}} gain (u, v) \times pref (u, o, v),$
  
  wherein the object gain represents an association between the object and the set of end-users or seed Web pages, defining a cost of each object as cost(o)=size(o), and identifying a subset O_sof O_vsuch that $\sum_{o \in O_{s}} cost (o) \leq P_{U} \times δ t and \sum_{o \in O_{s}} gain (o) is maximized .$

Specification

Resources

Litigation Campaign Assessment

Current Assignee
NEC Corporation
Original Assignee
NEC USA (NEC Corporation)
Inventors
Li, Wen-Syan, Candan, Kasim Selcuk
Primary Examiner(s)
CHOULES, JACK M

Application Number

US09/710,524
Time in Patent Office

887 Days
Field of Search

707/1, 707/2, 707/10, 709/217
US Class Current

1/1
CPC Class Codes

G06F 16/9574 of access to content, e.g. ...

Y10S 707/99932 Access augmentation or opti...

System and method employing random walks for mining web page associations and usage to optimize user-oriented web page refresh and pre-fetch scheduling

First Claim

2 Assignments

0 Petitions

Accused Products

Abstract

168 Citations

42 Claims

Specification

Solutions

Use Cases

Quick Links

System and method employing random walks for mining web page associations and usage to optimize user-oriented web page refresh and pre-fetch scheduling

First Claim

2 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

168 Citations

42 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links