Methods and apparatus using task models for targeting marketing information to computer users based on a task being performed

• US 6,330,554 B1
• Filed: 06/03/1999
• Issued: 12/11/2001
• Est. Priority Date: 06/03/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ingerman, David, Wu, Lani F., Altschuler, Steven J., Jung, Edward K., Ridgeway, Greg
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/325,167
• Time in Patent Office: 922 Days
• Field of Search: 705/1, 705/10, 705/14, 705/23, 382/100, 382/137, 717/5, 707/6
• US Class Current: 706/21
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Methods and apparatus for analyzing tasks performed by computer users by (i) gathering usage data, (ii) converting logged usage data into a uniform format, (iii) determining or defining task boundaries, and (iv) determining a task analysis model by “clustering” similar tasks together. The task analysis model may be used to (i) help users complete a task (such help, for example, may be in the form of a gratuitous help function), and/or (ii) to target marketing information to users based on user inputs and the task analysis model. The present invention also provides a uniform semantic network for representing different types of objects in a uniform way.

Claims

1. A method for using a predetermined model of clustered tasks, for providing marketing information to a user attempting to perform a task, the method comprising steps of:

a) logging inputs of the user as steps;

b) generating a partial task from the steps logged;

c) determining a distance between the partial task generated and each of the clustered tasks;

d) determining a minimum of the distances determined; and

e) rendering marketing information content to the user, wherein the marketing information content is related to a task cluster associated with the minimum of the distances determined.

2. The method of claim 1 wherein the user input are at least one of a query and a command, and

wherein the step of determining a distance between the partial task generated and each of the clustered tasks includes sub-steps of:

i) formatting the steps corresponding to the user input as a run time graph having vertices corresponding to the at least one of the query and the command and having edges corresponding to related queries and commands; and

ii) determining a distance between the run time graph and graphs of tasks of the task clusters of the model.

3. The method of claim 2 wherein the sub-step of determining distances between the run time graph and the graphs of tasks of the task clusters of the model includes steps of:

A) determining an intersection of the run time graph and each of the graphs of the tasks of the task clusters of the model;

B) determining a difference of the run time graph and each of the graphs of the tasks of the task clusters of the model;

C) determining connected elements of each of the differences; and

D) determining, in each case, the distance based on the connected elements and the intersection, wherein the distance increases as a number of the connected elements increases.

4. The method of claim 3 wherein the distance between the run time graph A and each of the graphs B of the tasks of the task clusters of the model, is defined by the expression:

$\mathrm{dis}<br><br>\text{\hspace{1em}<br><br>}<br><br>\tan <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ce}<br><br>\left(A,B\right)=\underset{\mathrm{<br><br>}\in <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{all}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{graph}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{pieces}}{\sum <br><br>}<br><br>v^{<br><br>c_i<br><br>}$

where v is a parameter greater than 1 and c_i is the number of connected elements in piece i of the difference graph A−

B.

5. The method of claim 3 wherein the distance between the run time graph A and each of the graphs B of the tasks of the task clusters of the model, is defined by the expression:

$\mathrm{dis}<br><br>\text{\hspace{1em}<br><br>}<br><br>\tan <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ce}<br><br>\left(A,B\right)=\frac{\max <br><br>\left[d^{*}<br><br>\left(A,B\right),d^{*}<br><br>\left(B,A\right)\right]}{n_{\mathrm{intersect}}}$

wherein n_intersect is the number of vertices and edges in A∩

B,

wherein $d^{*}<br><br>\left(A,B\right)=\underset{\mathrm{<br><br>}\in <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{all}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{graph}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{pieces}}{\sum <br><br>}<br><br>v^{<br><br>c_i<br><br>}$

where v is a parameter greater than 1 and c_i is the number of connected elements in piece i of the difference graph A−

B, and,

wherein $d^{*}<br><br>\left(B,A\right)=\underset{\mathrm{<br><br>}\in <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{all}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{graph}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{pieces}}{\sum <br><br>}<br><br>v^{<br><br>c_i^{\mathrm{\prime <br><br>}}<br><br>}$

where v is a parameter greater than 1 and c′

_i is the number of connected elements in piece i of the difference graph B−

A.

6. An apparatus for using a predetermined model of clustered tasks, for providing marketing information to a user attempting to perform a task, the apparatus comprising:

a) means for logging inputs of the user as steps;

b) means for generating a partial task from the steps logged;

c) means for determining a distance between the partial task generated and each of the clustered tasks;

d) means for determining a minimum of the distances determined; and

e) means for rendering marketing information content to the user, wherein the marketing information content is related to a task cluster associated with the minimum of the distances determined.

7. The apparatus of claim 6 wherein the user input are at least one of a query and a command, and

wherein the means for determining a distance between the partial task generated and each of the clustered tasks include:

i) means for formatting the steps corresponding to the user input as a run time graph having vertices corresponding to the at least one of the query and the command and having edges corresponding to related queries and commands; and

ii) means for determining a distance between the run time graph and graphs of tasks of the task clusters of the model.

8. The apparatus of claim 7 wherein the means for determining distances between the run time graph and the graphs of tasks of the task clusters of the model include:

A) means for determining an intersection of the run time graph and each of the graphs of the tasks of the task clusters of the model;

B) means for determining a difference of the run time graph and each of the graphs of the tasks of the task clusters of the model;

C) means for determining connected elements of each of the differences; and

D) means for determining, in each case, the distance based on the connected elements and the intersection, wherein the distance increases as a number of the connected elements increases.

9. The apparatus of claim 8 wherein the distance between the run time graph A and each of the graphs B of the tasks of the task clusters of the model, is defined by the expression:

$\mathrm{dis}<br><br>\text{\hspace{1em}<br><br>}<br><br>\tan <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ce}<br><br>\left(A,B\right)=\underset{\mathrm{<br><br>}\in <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{all}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{graph}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{pieces}}{\sum <br><br>}<br><br>v^{<br><br>c_i<br><br>}$

where v is a parameter greater than 1 and c_i is the number of connected elements in piece i of the difference graph A−

B.

10. The apparatus of claim 8 wherein the distance between the run time graph A and each of the graphs B of the tasks of the task clusters of the model, is defined by the expression:

$\mathrm{dis}<br><br>\text{\hspace{1em}<br><br>}<br><br>\tan <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{ce}<br><br>\left(A,B\right)=\frac{\max <br><br>\left[d^{*}<br><br>\left(A,B\right),d^{*}<br><br>\left(B,A\right)\right]}{n_{\mathrm{intersect}}}$

wherein n_intersect is the number of vertices and edges in A∩

B,

wherein $d^{*}<br><br>\left(A,B\right)=\underset{\mathrm{<br><br>}\in <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{all}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{graph}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{pieces}}{\sum <br><br>}<br><br>v^{<br><br>c_i<br><br>}$

where v is a parameter greater than 1 and c_i is the number of connected elements in piece i of the difference graph A−

B, and,

wherein $d^{*}<br><br>\left(B,A\right)=\underset{\mathrm{<br><br>}\in <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{all}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{graph}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{pieces}}{\sum <br><br>}<br><br>v^{<br><br>c_i^{\mathrm{\prime <br><br>}}<br><br>}$

where v is a parameter greater than 1 and c′

_i is the number of connected elements in piece i of the difference graph B−

A.

11. A machine readable medium having machine executable instructions which, when executed by the machine, perform steps for using a predetermined model of clustered tasks, for providing marketing information to a user attempting to perform a task, the steps comprising:

a) logging inputs of the user as steps;

b) generating a partial task from the steps logged;

c) determining a distance between the partial task generated and each of the clustered tasks;

d) determining a minimum of the distances determined; and

e) rendering marketing information content to the user, wherein the marketing information content is related to a task cluster associated with the minimum of the distances determined.