US6714975B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for targeted advertising on the web based on accumulated self-learning data, clustering users and semantic node graph techniques
Assignee: Warner Media LLC
•
Filing: 1997-03-31
•
Granted: 2004-03-30
•
Expires: 2017-03-31
Abstract
Abstract A method for dynamically placing objects in slots on a web page in response to a current client request for the web page comprises the steps of classifying users into user groups based one or more user-characteristics, accumulating self-learning data based on user click behavior for each user group, matching the current client request with a corresponding user group and scheduling real-time selection of the slots for the objects on the web page based on the self-learning data of the corresponding user group.
Inventors
- 👤 Charu Chandra Aggarwal
- 👤 Joel Leonard Wolf
- 👤 Philip Shi-lung Yu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 23:43
CPC Classifications
G; G06; G06Q; G06Q30/00; G06Q30/02; G06Q30/0241; G06Q30/0242; G06Q30/0244; G06Q30/0251; G06Q30/0255; G06Q30/0256; G06Q30/0277
Claims Analysis
Total Claims: 60
Claim 1
Independent Claim
150 words
A method for dynamically placing objects in slots on a web page in response to a current request for said web page, comprising the steps of: classifying users into a plurality of user groups based on at least one user characteristic; accumulating, for each user group, self learning data based on user click behavior during web page accesses; matching a user identification of a current request for a web page with a corresponding user group; creating a semantic diagram having nodes corresponding to web pages, keywords, and the objects; generating a graph based upon the semantic diagram, the graph representing possibilities for assigning the objects to the web pages; and dynamically selecting one or more objects, and one or more slots on said requested web page in which to position said one or more objects, based on at least said self-learning data of said corresponding user group and the graph.
Claim 2
Independent Claim
150 words
A method for dynamically placing objects in slots on a web page in response to a current request for said web page, comprising the steps of: classifying users into a plurality of user groups based on at least one user characteristic; accumulating, for each user group, self learning data based on user click behavior during web page accesses; matching a user identification of a current request for a web page with a corresponding user group; creating a semantic diagram having nodes corresponding to web pages, keywords, and the objects; generating a graph based upon the semantic diagram, the graph representing possibilities for assigning the objects to the web pages; and dynamically selecting one or more objects, and one or more slots on said requested web page in which to position said one or more objects, based on at least said self-learning data of said corresponding user group and the graph.
Claim 3
Dependent Claim
61 words
The method of claim 1 wherein said accumulating step comprises the step of accumulating a group click/exposure ratio for each user group and wherein said dynamically selecting step comprises the step of selecting said one or more objects and said one or more slots for said objects on said web page based on said group click/exposure ratio for said corresponding group.
Claim 4
Dependent Claim
39 words
The method of claim 1 further comprising the step of generating probabilistic assignment data for each user group based on a contract requirement of said objects and wherein said dynamically selecting step is further based on said assignment data.
Claim 5
Dependent Claim
34 words
The method of claim 3 wherein said generating step comprises the step of generating probabilistic assignment data for each user group based on an exposure requirement of said object for a period of time.
Claim 6
Dependent Claim
30 words
The method of claim 3 wherein said classifying step comprises the step of classifying objects and web pages into a plurality of classes so that user classification efficiency is improved.
Claim 7
Dependent Claim
41 words
The method of claim 5 wherein said classifying step comprises the steps of: assigning keywords to classes of objects and web pages and classifying objects and web pages into a plurality of said classes so that user classification efficiency is improved.
Claim 8
Dependent Claim
69 words
The method of claim 5 wherein said classifying step comprises the steps of: selecting a set of popular web pages with high click rates; classifying objects with similar click/exposure ratios on the set of popular web pages into object groups; classifying web pages experiencing similar click/exposure ratios for objects in each of said object groups into page groups; adding web pages to said set; and repeating said classifying steps.
Claim 9
Dependent Claim
17 words
The method of claim 7 wherein said slots have differing sizes and locations on said web page.
Claim 10
Dependent Claim
57 words
The method of claim 3 wherein the dynamically selecting step comprises the steps of: maintaining cumulated statistics on exposures for said corresponding user group within a required range of tolerance as a result of said probabilistic assignment data; and choosing objects for said slots based on a function of said cumulated statistics and said range of tolerance.
Claim 11
Dependent Claim
42 words
The method of claim 9 wherein the choosing step comprises the step of choosing objects for said slots based on a largest outstanding requirement as dictated by a difference between said cumulated statistics and a targeted rate for said corresponding user group.
Claim 12
Dependent Claim
27 words
The method of claim 1 further comprising the step of generating probabilistic assignment data for each user group based on a popularity characteristic of said web page.
Claim 13
Dependent Claim
36 words
The method of claim 11 wherein said generating step comprises the step of generating probabilistic assignment data for each user group based on a number of clicks on said web page for a period of time.
Claim 14
Dependent Claim
35 words
The method of claim 1 wherein said classifying step comprises the steps of: probabilistically choosing a fraction of previous requests and classifying users of said fraction of previous requests into a plurality of user groups.
Claim 15
Dependent Claim
15 words
The method of claim 1 wherein said classifying step is based on user demographic information.
Claim 16
Dependent Claim
15 words
The method of claim 1 wherein said classifying step is based on user click behavior.
Claim 17
Dependent Claim
15 words
The method of claim 15 wherein said classifying step is based on user click/exposure ratios.
Claim 18
Dependent Claim
16 words
The method of claim 15 wherein said classifying step is based on user path traversal patterns.
Claim 19
Dependent Claim
36 words
The method of claim 1 wherein said dynamcally selecting step is further based on exposures of objects on previous web pages requested by a same user so that repetitive exposure of the same object is controlled.
Claim 20
Dependent Claim
23 words
The method of claim 1 wherein the dynamically selecting step comprises the step of varying a size, appearance and/or position of said objects.
Claim 21
Dependent Claim
13 words
The method of claim 19 wherein the varying step is traversal path dependent.
Claim 22
Dependent Claim
50 words
The method of claim 1 wherein said classifying step comprises the steps of: collecting user characteristic data based on previous object assignments; analyzing said user characteristic data so that new user characteristic data is discovered; classifying users into a plurality of user groups based on said new user characteristic data.
Claim 23
Dependent Claim
14 words
The method of claim 21 wherein said user characteristic data is click/exposure ratio data.
Claim 24
Dependent Claim
15 words
The method of claim 21 wherein a fraction of said previous assignments are randomly made.
Claim 25
Dependent Claim
10 words
The method of claim 1 wherein said objects are advertisements.
Claim 26
Dependent Claim
33 words
The method of claim 1 wherein said classifying step is further based on a sensitivity of said corresponding user group to variations in size and location of said slots on said web page.
Claim 27
Dependent Claim
28 words
The method of claim 25 further comprising the step of collecting statistics representing the impact of different slot sizes and locations on click/exposure ratios for said user groups.
Claim 28
Dependent Claim
28 words
The method of claim 1 wherein said classifying step comprises the step of using an efficient multi-dimensional clustering algorithm to classify users into a plurality of user groups.
Claim 29
Dependent Claim
30 words
The method of claim 1 wherein said dynamically selecting step comprises the step of randomly scheduling a fraction of said objects to said web page so that self-learning is improved.
Claim 30
Dependent Claim
24 words
The method of claim 1 wherein said dynamically selecting step comprises the step of scheduling on said web page different numbers of said slots.
Claim 31
Dependent Claim
16 words
The method of claim 1 wherein said classifying step is further based on time of day.
Claim 32
Dependent Claim
34 words
The method of claim 1 , wherein said method is implemented by a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform said method steps.
Claim 33
Dependent Claim
23 words
The method of claim 1 , wherein the one or more objects and the one or more slots are dynamically selected in real-time.
Claim 34
Dependent Claim
18 words
The method of claim 1 , wherein said selecting step is further based on said requested web page.
Claim 35
Dependent Claim
26 words
The method of claim 1 , wherein, upon serving said requested web page, a number of expected clicks of said one or more objects is maximized.
Claim 36
Dependent Claim
68 words
The method of claim 1 , wherein, the graph comprises object nodes and page nodes respectively corresponding to the objects and the web pages, and arcs for connecting the object nodes to the page nodes, and wherein object node flow requirements and page node flow requirements are respectively assigned to the object nodes and the page nodes, and flow weights and a flow are assigned to the arcs.
Claim 37
Dependent Claim
30 words
The method of claim 35 , wherein the arcs connect the object nodes to the page nodes as a function of a classification of the objects and the web pages.
Claim 38
Dependent Claim
27 words
The method of claim 35 , wherein the object node flow requirements are assigned to the object nodes based on periodic contract requirements of a corresponding object.
Claim 39
Dependent Claim
28 words
The method of claim 35 , wherein the page node flow requirements are assigned to the page nodes based on an expected popularity of a corresponding web page.
Claim 40
Dependent Claim
32 words
The method of claim 35 , wherein the flow weights are assigned to the arcs based on a function of group click/exposure ratios resulting from placing the objects on the web pages.
Claim 41
Dependent Claim
36 words
The method of claim 35 , wherein said generating step comprises the step of introducing a flow supply node having an arc to each of the object nodes, the flow supply node providing a supply flow.
Claim 42
Dependent Claim
54 words
The method of claim 35 , wherein the flow to each of the arcs is assigned such that the supply flow flows through the arcs to the page nodes and in-flow equals out-flow for each of the object nodes and in-flow is less than the node flow requirements for each of the page nodes.
Claim 43
Dependent Claim
21 words
The method of claim 35 , wherein the flow to each of the arcs is assigned using a probabilistic assignment method.
Claim 44
Dependent Claim
32 words
The method of claim 1 , wherein said creating step connects a page node to a keyword node in the semantic diagram if a corresponding page falls in a corresponding keyword category.
Claim 45
Dependent Claim
32 words
The method of claim 43 , wherein said creating step connects an object node to the keyword node in the semantic diagram if a corresponding object falls in a corresponding keyword category.
Claim 46
Dependent Claim
42 words
The method of claim 44 , wherein the page node is connected by an arc to the object node in the graph if a path exists in the semantic diagram from the page node through the keyword node to the object node.
Claim 47
Dependent Claim
72 words
The method of claim 35 , wherein the arcs connect the object nodes to the page nodes as a function of a classification of the objects and the web pages, and the object node flow requirements and the page node flow requirements are respectively assigned to the object nodes and the page nodes based on periodic contract requirements of a corresponding object and an expected popularity of a corresponding web page, respectively.
Claim 48
Dependent Claim
36 words
The method of claim 46 , wherein said generating step comprises the step of introducing a flow supply node having an arc to each of the object nodes, the flow supply node providing a supply flow.
Claim 49
Dependent Claim
54 words
The method of claim 47 , wherein the flow to each of the arcs is assigned such that the supply flow flows through the arcs to the page nodes and in-flow equals out-flow for each of the object nodes and in-flow is less than the node flow requirements for each of the page nodes.
Claim 50
Dependent Claim
21 words
The method of claim 48 , wherein the flow to each of the arcs is assigned using a probabilistic assignment method.
Claim 51
Dependent Claim
32 words
The method of claim 48 , wherein the flow weights are assigned to the arcs based on a function of group click/exposure ratios resulting from placing the objects on the web pages.
Claim 52
Independent Claim
336 words
A method for dynamically placing objects in slots on a web page in response to a current request for said web page, comprising the steps of: classifying users into a plurality of user groups based on at least one user characteristic; generating probabilistic assignment data for each user group based on a contract requirement of said objects; accumulating, for each user group, self learning data based on user click behavior during web page accesses; matching a user identification of a current request for a web page with a corresponding user group; and dynamically selecting, in real-time, one or more objects, and one or more slots on said requested web page in which to position said one or more objects, based on at least said self-learning data of said corresponding user group, said requested web page, and said probabilistic assignment data, wherein said generating step comprises the steps of: assigning each of said objects to an object node; assigning each of a plurality of web pages to a page node; providing an arc between a page node and at least one of said object nodes as a function of a classification of said objects and said web pages; assigning an object node flow requirement to each object node based on periodic contract requirements of a corresponding object; assigning a page node flow requirement to each page node based on an expected popularity of a corresponding web page; introducing a flow supply node having an arc to each object node, said flow supply node providing a supply flow; assigning a flow weight to each arc based on a function of group click/exposure ratios resulting from placing said corresponding objects on said corresponding web pages; and assigning a flow to each arc with a probabilistic assignment method so that said supply flow flows through said arcs to said page nodes and in-flow equals out-flow for each object node and in-flow is less than said node flow requirement each page node, wherein a total return of the assignment is maximized.
Claim 53
Independent Claim
336 words
A method for dynamically placing objects in slots on a web page in response to a current request for said web page, comprising the steps of: classifying users into a plurality of user groups based on at least one user characteristic; generating probabilistic assignment data for each user group based on a contract requirement of said objects; accumulating, for each user group, self learning data based on user click behavior during web page accesses; matching a user identification of a current request for a web page with a corresponding user group; and dynamically selecting, in real-time, one or more objects, and one or more slots on said requested web page in which to position said one or more objects, based on at least said self-learning data of said corresponding user group, said requested web page, and said probabilistic assignment data, wherein said generating step comprises the steps of: assigning each of said objects to an object node; assigning each of a plurality of web pages to a page node; providing an arc between a page node and at least one of said object nodes as a function of a classification of said objects and said web pages; assigning an object node flow requirement to each object node based on periodic contract requirements of a corresponding object; assigning a page node flow requirement to each page node based on an expected popularity of a corresponding web page; introducing a flow supply node having an arc to each object node, said flow supply node providing a supply flow; assigning a flow weight to each arc based on a function of group click/exposure ratios resulting from placing said corresponding objects on said corresponding web pages; and assigning a flow to each arc with a probabilistic assignment method so that said supply flow flows through said arcs to said page nodes and in-flow equals out-flow for each object node and in-flow is less than said node flow requirement each page node, wherein a total return of the assignment is maximized.
Claim 54
Dependent Claim
26 words
The method of claim 51 , wherein, upon serving said requested web page, a number of expected clicks of said one or more objects is maximized.
Claim 55
Independent Claim
146 words
A method for dynamically placing objects in slots on a web page in response to a current request for said web page, comprising the steps of: classifying users into a plurality of user groups based on at least one user characteristic; accumulating, for each user group, self learning data based on user click behavior during web page accesses; matching a user identification of a current request for a web page with a corresponding user group; creating a semantic diagram having nodes corresponding to web pages, keywords, and the objects; generating a graph based upon the semantic diagram, the graph representing possibilities for assigning the objects to the web pages; and dynamically selecting one or more slots on said requested web page in which to position one or more of the objects, based on at least said self-learning data of said corresponding user group and the graph.
Claim 56
Independent Claim
146 words
A method for dynamically placing objects in slots on a web page in response to a current request for said web page, comprising the steps of: classifying users into a plurality of user groups based on at least one user characteristic; accumulating, for each user group, self learning data based on user click behavior during web page accesses; matching a user identification of a current request for a web page with a corresponding user group; creating a semantic diagram having nodes corresponding to web pages, keywords, and the objects; generating a graph based upon the semantic diagram, the graph representing possibilities for assigning the objects to the web pages; and dynamically selecting one or more slots on said requested web page in which to position one or more of the objects, based on at least said self-learning data of said corresponding user group and the graph.
Claim 57
Dependent Claim
46 words
The method of claim 53 , wherein said step of selecting the one or more objects comprises the step of dynamically selecting, in real-time, said one or more objects, based on at least said self-learning data of said corresponding user group and said requested web page.
Claim 58
Dependent Claim
26 words
The method of claim 53 , wherein, upon serving said requested web page, a number of expected clicks of said one or more objects is maximized.
Claim 59
Dependent Claim
17 words
The method of claim 53 , wherein the one or more slots are dynamically selected in real-time.
Claim 60
Dependent Claim
34 words
The method of claim 53 , wherein said method is implemented by a program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform said method steps.
References Cited (Backward Citations)
US5596703A
Cited
US5799292A
Cited
US5835087A
Cited
US5754939A
Cited
US5754938A
Cited
US6029195A
Cited
US5740549A
Cited
US6026368A
Cited
US5819285A
Cited
US5918014A
Cited
US5862325A
Cited
US5848397A
Cited
US5848396A
Cited
US5727129A
Cited
US5933811A
Cited
US5948061A
Cited
US6243375B1
Cited
US5796952A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-03-30 | 2007-09-29 | 2008-03-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-03-30 | 2011-09-29 | 2012-03-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-03-30 | 2015-09-29 | 2016-03-30 | $7700.00 | Window Closed / Lapsed |