Methods and apparatus for analyzing computer-based tasks to build task models

US 6,778,971 B1
Filed: 06/03/1999
Issued: 08/17/2004
Est. Priority Date: 06/03/1999
Status: Expired due to Fees

First Claim

Patent Images

1. A computer implemented method for defining a task model used as a basis for a delivery of content to a user, the task model being a clustering of similar tasks based on stored objects used by at least one computer based application in response to user input steps, the method comprising steps of:

a) generating a log record when the at least one computer-based application uses a stored object, wherein the log record includes an identification of the stored object used by the at least one computer-based application, and wherein an object usage log is defined by a set of log records;

b) generating a uniform format object usage log from the object usage log;

c) generating a log of tasks by defining task boundaries in the uniform format object usage log, wherein the log of tasks is defined by records having a task identifier; and

d) generating the task model based on the log of tasks in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.

View all claims

2 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

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.

95 Citations

View as Search Results

100 Claims

1. A computer implemented method for defining a task model used as a basis for a delivery of content to a user, the task model being a clustering of similar tasks based on stored objects used by at least one computer based application in response to user input steps, the method comprising steps of:
- a) generating a log record when the at least one computer-based application uses a stored object, wherein the log record includes an identification of the stored object used by the at least one computer-based application, and wherein an object usage log is defined by a set of log records;
  
  b) generating a uniform format object usage log from the object usage log;
  
  c) generating a log of tasks by defining task boundaries in the uniform format object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  d) generating the task model based on the log of tasks in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
- - 2. The method of claim 1 wherein each of the log records includes a time stamp.
  - 3. The method of claim 1 wherein the step of generating the task model includes sub-steps of:
4. The method of claim 3 wherein the sub-step of determining distances between tasks includes steps of:
- A) representing each of the tasks as a graph; and
  
  B) determining a distance between graphs, wherein the distance determined is based, in part, on a connectedness of graph differences.
5. The method of claim 4 wherein each of the tasks is represented by a relation of related entities having known or variable values and wherein the step of representing each of the tasks as a graph includes steps of:
- 1) defining a vertex for each entity and each relation;
  
  2) merging vertices having entities with a variable value; and
  
  3) defining edges to connect related entities and entities that are instances of a relation.
6. The method of claim 5 wherein the step of determining a distance between graphs includes steps of:
- 1) determining an intersection of the graphs;
  
  2) determining a difference between the graphs;
  
  3) determining connected elements of the difference;
  
  4) determining the distance based on the connected elements and the intersection, wherein the distance increases as a number of the connected elements increases.
7. The method of claim 6 wherein the distance between two graphs, A and B, is defined by the expression:
- $distance (A, B) = \sum_{i ɛ all graph pieces}^{} v^{\langle c_{i} \rangle}$ where v is a parameter greater than 1 and c_iis the number of connect elements in piece i of the difference graph A−
  
  B.
8. The method of claim 6 wherein the distance between two graphs, A and B, is defined by the expression:
- $distance (A, B) = \frac{\max [d * (A, B), d * (B, A)]}{n_{intersect}}$ wherein n_intersectis the number of vertices and edges in A∩
  
  B, wherein $d * (A, B) = \sum_{i ɛ all graph pieces}^{} v^{\langle c_{i} \rangle}$ where v is a parameter greater than 1 and c_iis the number of connected elements in piece i of the difference graph A−
  
  B, and wherein $d * (B, A) = \sum_{i ɛ all graph pieces}^{} v^{\langle c_{i}^{'} \rangle}$ where v is a parameter greater than 1 and c′
  
  _iis the number of connected elements in piece i of the difference graph B−
  
  A.
9. The method of claim 3 wherein the sub-step of clustering tasks based on the distances determined is carried out in accordance with agglomerative hierarchical clustering.
10. The method of claim 3 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum of the distances determined; and
  
  D) if the minimum distance is less than a predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
11. The method of claim 3 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum of the distances determined; and
  
  D) if a number of clusters is greater than a predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
12. The method of claim 3 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum of the distances determined; and
  
  D) if the minimum distance is less than a first predetermined threshold and if a number of clusters is greater than a second predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
13. The method of claim 1 wherein the at least one application is defined by an a-ERD and wherein the uniform format object usage log generated describes user input steps as sub-a-ERDs of the a-ERD.
14. The method of claim 13 wherein the step of generating a log of tasks by defining task boundaries includes sub-steps of:
- i) determining when two temporally adjacent user input steps correspond to disjoint sub-a-ERDs of the a-ERD defining the at least one application; and
  
  ii) when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD defining the at least one application, defining a task boundary.
15. The method of claim 13 wherein the step of generating a log of tasks by defining task boundaries includes sub-steps of:
- i) determining when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD defining the at least one application;
  
  ii) determining whether disjoint sub-a-ERDs are joined by a user input; and
  
  iii) when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD defining the at least one application and are not joined by a user input, defining a task boundary.
16. The method of claim 1 wherein the user input steps are selected from a group of user inputs comprising queries and commands.

17. A computer implemented method for defining a task model used as a basis for delivery of content to a user, the task model being a clustering of similar tasks based on an object usage log defined by a set of log records, each of the log records including an identification of a stored object used by at least one application in response to user input steps, the method comprising steps of:
- a) generating a uniform format object usage log from the object usage log;
  
  b) generating a log of tasks by defining task boundaries in the uniform format object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  c) generating the task model based on the log of tasks in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.
- View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
- - 18. The method of claim 17 wherein each of the log records includes a time stamp.
  - 19. The method of claim 17 wherein the step of generating the task model includes sub-steps of:
20. The method of claim 19 wherein the sub-step of determining distances between tasks includes steps of:
- A) representing each of the tasks as a graph; and
  
  B) determining a distance between graphs, wherein the distance determined is based, in part, on a connectedness of graph differences.
21. The method of claim 20 wherein each of the tasks is represented by a relation of related entities having known or variable values and wherein the step of representing each of the tasks as a graph includes steps of:
- 1) defining a vertex for each entity and each relation;
  
  2) merging vertices having entities with a variable value; and
  
  3) defining edges to connect related entities and entities that are instances of a relation.
22. The method of claim 21 wherein the step of determining a distance between graphs includes steps of:
- 1) determining an intersection of the graphs;
  
  2) determining a difference between the graphs;
  
  3) determining connected elements of the difference;
  
  4) determining the distance based on the connected elements and the intersection, wherein the distance increases as a number of the connected elements increases.
23. The method of claim 22 wherein the distance between two graph, A and B, is defined by the expression:
- $distance (A, B) = \sum_{i ɛ all graph pieces} v^{\langle c_{i} \rangle}$ where v is a parameter greater than 1 and C_iis the number of connected elements in piece i of the difference graph A−
  
  B.
24. The method of claim 22 wherein the distance between two graphs, A and B, is defined by the expression:
- $distance (A, B) = \frac{\max [d * (A, B), d * (B, A)]}{n_{intersect}}$ wherein n_intersectis the number of vertices and edges in A∩
  
  B, wherein $d * (A, B) = \sum_{i ɛ all graph pieces} v^{\langle c_{i} \rangle}$ where v is a parameter greater than 1 and c_iis the number of connected elements in piece i of the difference graph A−
  
  B, and wherein $d * (B, A) = \sum_{i ɛ all graph pieces} v^{\langle c_{i}^{'} \rangle}$ where v is a parameter greater than 1 and c′
  
  _iis the number of connected elements in piece i of the difference graph B−
  
  A.
25. The method of claim 19 wherein the sub-step of clustering tasks based on the distances determined is carried out in accordance with agglomerative hierarchical clustering.
26. The method of claim 19 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum of the distances determined; and
  
  D) if the minimum distance is less than a predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
27. The method of claim 19 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum of the distances determined; and
  
  D) if a number of clusters is greater than a predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
28. The method of claim 19 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum of the distances determined; and
  
  D) if the minimum distance is less than a first predetermined threshold and if a number of clusters is greater than a second predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
29. The method of claim 17 wherein the at least one application is defined by an a-ERD and wherein the uniform format object usage log generated describes user input steps as sub-a-ERDs of the a-ERD.
30. The method of claim 29 wherein the steps of generating a log of tasks by defining task boundaries includes sub-steps of:
- i) determining when two temporally adjacent user input steps correspond to disjoint sub-a-ERDs of the a-ERD defining the at least one application; and
  
  ii) when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD defining the at least on application, defining a task boundary.
31. The method of claim 29 wherein the step of generating a log of tasks by defining task boundaries includes sub-steps of:
- i) determining when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD defining the at least one application;
  
  ii) determining whether disjoint sub-a-ERDs are joined by a user input; and
  
  iii) when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD defining the at least one application and are not joined by a user input, defining a task boundary.
32. The method of claim 17 wherein the user input steps are selected from a group of user inputs comprising queries and commands.

33. A computer implemented method for defining a task model used as a basis for a delivery of context to a user, the task model being a clustering of similar tasks based on stored objects used by an application in response to user input steps, the method comprising steps of:
- a) generating a log record when the application uses a stored object, wherein the log record includes an identification of the stored object used by the application, and wherein an object usage log is defined by a set of log records;
  
  b) generating a log of tasks by defining task boundaries in the object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  c) generating the task model based on the log of tasks in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.
- View Dependent Claims (34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48)
- - 34. The method of claim 33 wherein each of the log records includes a time stamp.
  - 35. The method of claim 33 wherein the step of generating the task model includes sub-steps of:
36. The method of claim 35 wherein the sub-step of determining distances between tasks includes steps of:
- A) representing each of the tasks as a graph; and
  
  B) determining a distance between graphs, wherein the distance determined is based, in part, on a connectedness of graph differences.
37. The method of claim 36 wherein each of the tasks is represented by a relation of related entities having known or variable values and wherein the step of representing each of the tasks as a graph includes steps of:
- 1) defining a vertex for each entity and each relation;
  
  2) merging vertices having entities with a variable value; and
  
  3) defining edges to connect related entities and entities that are instances of a relation.
38. The method of claim 37 wherein the step of determining a distance between graphs includes steps of:
- 1) determining an intersection of the graphs;
  
  2) determining a difference between the graphs;
  
  3) determining connected elements of the difference;
  
  4) determining the distance based on the connected elements and the intersection, wherein the distance increases as a number of the connected elements increases.
39. The method of claim 38 wherein the distance between two graphs, A and B, is defined by the expression:
- $distance (A, B) = \sum_{i ɛ all graph pieces} v^{\langle c_{i} \rangle}$ where v is a parameter greater than 1 and c_iis the number of connected elements in piece i of the difference graph A−
  
  B.
40. The method of claim 38 wherein the distance between two graphs, A and B, is defined by the expression:
- $distance (A, B) = \frac{\max [d * (A, B), d * (B, A)]}{n_{intersect}}$ wherein n_intersectis the number of vertices and edges in A∩
  
  B, wherein $d * (A, B) = \sum_{i ɛ all graph pieces} v^{\langle c_{i} \rangle}$ where v is a parameter great than 1 and c_iis the number of connected elements in piece i of the difference graph A−
  
  B, and wherein $d * (B, A) = \sum_{i ɛ all graph pieces} v^{\langle c_{i}^{'} \rangle}$ where v is a parameter greater than 1 and c′
  
  _iis the number of connected elements in piece i of the difference graph B−
  
  A.
41. The method of claim 35 wherein the sub-step of clustering tasks based on the distances determined is carried out in accordance with agglomerative hierarchical clustering.
42. The method of claim 35 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum distances determined; and
  
  D) if the minimum distance is less than a predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
43. The method of claim 35 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum of the distances determined; and
  
  D) if a number of clusters is greater than a predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
44. The method of claim 35 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum of the distances determined; and
  
  D) if the minimum distance is less than a first predetermined threshold and if a number of clusters is greater than a second predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
45. The method of claim 33 wherein the application is defined by an a-ERD and wherein user input steps are defined as sub-a-ERDs of the a-ERD.
46. The method of claim 45 wherein the step of generating a log of tasks by defining task boundaries includes sub-steps of:
- i) determining when two temporally adjacent user input steps correspond to disjoint sub-a-ERDs of the a-ERD defining the application; and
  
  ii) when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD, defining a task boundary.
47. The method of claim 45 wherein the step of generating a log of tasks by defining task boundaries includes sub-steps of:
- i) determining when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD defining the application;
  
  ii) determining whether disjoint sub-a-ERDs are joined by a user input; and
  
  iii) when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD defining the application and are not joined by a user input, defining a task boundary.
48. The method of claim 33 wherein the user input steps are selected from a group of user inputs comprising queries and commands.

49. A computer implemented method for defining a task model used as a basis for delivery of context to a user, the task model being a clustering of similar tasks based on an object usage log defined by a set of log records, each of the log records including an identification of a stored object used by an application in response to user input steps, the method comprising steps of:
- a) generating a log of tasks by defining task boundaries in the object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  b) generating the task model based on the log of tasks in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.
- View Dependent Claims (50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64)
- - 50. The method of claim 49 wherein each of the log records includes a time stamp.
  - 51. The method of claim 49 wherein the step of generating the task model includes sub-steps of:
52. The method of claim 51 wherein the sub-step of determining distances between tasks includes steps of:
- A) representing each of the tasks as a graph; and
  
  B) determining a distance between graphs, wherein the distance determined is based, in part, on a connectedness of graph differences.
53. The method of claim 52 wherein each of the tasks is represented by a relation of related entities having known or variable values and wherein the step of representing each of the tasks as a graph includes steps of:
- 1) defining a vertex for each entity and each relation;
  
  2) merging vertices having entities with a variable value; and
  
  3) defining edges to connect related entities and entities that are instances of a relation.
54. The method of claim 53 wherein the step of determining a distance between graphs includes steps of:
- 1) determining an intersection of the graphs;
  
  2) determining a difference between the graphs;
  
  3) determining connected elements of the difference;
  
  4) determining the distance based on the connected elements and the intersection, wherein the distance increases as a number of the connected elements increases.
55. The method of claim 54 wherein the distance between two graphs, A and B, is defined by the expression:
- $distance (A, B) = \sum_{i ɛ all graph pieces} v^{\langle c_{i} \rangle}$ where v is a parameter great than 1 and c_iis the number of connected elements in piece i of the difference graph A−
  
  B.
56. The method of claim 54 wherein the distance between two graphs, A and B, is defined by the expression:
- $distance (A, B) = \frac{\max [d * (A, B), d * (B, A)]}{n_{intersect}}$ wherein n_intersectis the number of vertices and edges in A∩
  
  B, wherein $d * (A, B) = \sum_{i ɛ all graph pieces} v^{\langle c_{i} \rangle}$ where v is a parameter greater than 1 and c_iis the number of connected elements in piece i of the difference graph A−
  
  B, and, wherein $d * (B, A) = \sum_{i ɛ all graph pieces} v^{\langle c_{i}^{'} \rangle}$ where v is a parameter greater than 1 and c′
  
  _iis the number of connected elements in piece i of the difference graph B−
  
  A.
57. The method of claim 51 wherein the sub-step of clustering tasks based on the distances determined is carried out in accordance with agglomerative hierarchical clustering.
58. The method of claim 51 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum of the distances determined; and
  
  D) if the minimum distance is less than a predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
59. The method of claim 51 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum of the distances determined; and
  
  D) if a number of clusters is greater than a predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
60. The method of claim 51 wherein the sub-step of clustering tasks based on the distances determined includes steps of:
- A) determining least distant tasks and clustering them;
  
  B) determining distances between (i) tasks, (ii) clusters, and (iii) tasks and clusters;
  
  C) determining a minimum of the distances determined; and
  
  D) if the minimum distance is greater than a first predetermined threshold and if a number of clusters is greater than a second predetermined threshold, clustering the (i) tasks, (ii) clusters, or (iii) tasks and clusters associated with the minimum distance and repeating steps B through D.
61. The method of claim 49 wherein the application is defined by an a-ERD and wherein the object usage log generated describes user input steps as sub-a-ERDs of the a-ERD.
62. The method of claim 61 wherein the step of generating a log of tasks by defining task boundaries includes sub-steps of:
- i) determining when two temporally adjacent user input steps correspond to disjoint sub-a-ERDs of the a-ERD defining the application; and
  
  ii) when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD defining the application, defining a task boundary.
63. The method of claim 61 wherein the step of generating a log of tasks by defining task boundaries includes sub-steps of:
- i) determining when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD defining the application;
  
  ii) determining whether disjoint sub-a-ERDs are joined by a user input; and
  
  iii) when two temporally adjacent steps correspond to disjoint sub-a-ERDs of the a-ERD defining the application and are not joined by a user input, defining a task boundary.
64. The method of claim 49 wherein the user input steps are selected from a group of user inputs comprising queries and commands.

65. A computer implemented method for generating a task model in which similar tasks are clustered, the task model used as a basis for a delivery of context to a user, the method comprising steps of:
- a) determining distances between tasks; and
  
  b) clustering tasks based on the distances determined.
- View Dependent Claims (66, 67, 68, 69, 70, 71, 72, 73, 74)
- - 66. The method of claim 65 wherein the step of determining distances between tasks includes sub-steps of:
67. The method of claim 66 wherein each of the tasks is represented by a relation of related entities having known or variable values and wherein the sub-step of representing each of the tasks as a graph includes steps of:
- A) defining a vertex for each entity and each relation;
  
  B) merging vertices having entities with a variable value; and
  
  C) defining edges to connect related entities and entities that are instances of a relation.
68. The method of claim 67 wherein the sub-step of determining a distance between graphs includes steps of:
- A) determining an intersection of the graphs;
  
  B) determining a difference between the graphs;
  
  C) determining connected element of the difference;
  
  D) determining the distance based on the connected elements and the intersection, wherein the distance increases as a number of the connected elements increases.
69. The method of claim 68 wherein the distance between two graph, A and B, is defined by the expression:
- $distance (A, B) = \sum_{i ɛ all graph pieces} v^{\langle c_{i} \rangle}$ where v is a parameter greater than 1 and c_iis the number of connected elements in piece i of the difference graph A−
  
  B.
70. The method of claim 68 wherein the distance between two graphs, A and B, is defined by the expression:
- $distance (A, B) = \frac{\max [d * (A, B), d * (B, A)]}{n_{intersect}}$ wherein n_intersectis the number of vertices and edges in A∩
  
  B, wherein $d * (A, B) = \sum_{i ɛ all graph pieces} v^{\langle c_{i}^{'} \rangle}$ where v is a parameter greater than 1 and c_iis the number of connected elements in piece i of the difference graph A−
  
  B, and, wherein $d * (B, A) = \sum_{i ɛ all graph pieces} v^{\langle c_{i} \rangle}$ where v is a parameter greater than 1 and c′
  
  _iis the number of connected elements in piece i of the difference graph B−
  
  A.
71. The method of claim 65 wherein the step of clustering tasks based on the distances determined is carried out in accordance with agglomerative hierarchical clustering.
72. The method of claim 65 wherein the step of clustering tasks based on the distances determined includes sub-steps of:
- i) determining least distant tasks and clustering them;
  
  ii) determining distances between (a) tasks, (b) clusters, and (c) tasks and clusters;
  
  iii) determining a minimum of the distances determined; and
  
  iv) if the minimum distance is less than a predetermined threshold, clustering the (a) tasks, (b) clusters, or (c) tasks and clusters associated with the minimum distance and repeating sub-steps (ii) through (iv).
73. The method of claim 65 wherein the step of clustering tasks based on the distances determined includes sub-steps of:
- i) determining least distance tasks and clustering them;
  
  ii) determining distances between (a) tasks, (b) clusters, and (c) tasks and clusters;
  
  iii) determining a minimum of the distances determined; and
  
  iv) if a number of clusters is greater than a predetermined threshold, clustering the (a) tasks, (b) clusters, or (c) tasks and clusters associated with the minimum distance and repeating sub-steps (ii) through (iv).
74. The method of claim 65 wherein the step of clustering tasks based on the distances determined includes sub-steps of:
- i) determining least distant tasks and clustering them;
  
  ii) determining distances between (a) tasks, (b) clusters, and (c) tasks and clusters;
  
  iii) determining a minimum of the distances determined; and
  
  iv) if the minimum distance is less than a first predetermined threshold and if a number of clusters is greater than a second predetermined threshold, clustering the (a) tasks, (b) clusters, or (c) tasks and clusters associated with minimum distance and repeating steps (ii) through (iv).

75. An apparatus for defining a task model used as a basis for a delivery of context to a user the task model being a clustering of similar tasks based on stored objects used by at least one application in response to user input steps, the apparatus comprising:
- a) a log record generation unit for generating a log record when the at least one application uses a stored object, wherein the log record includes an identification of the stored object used by the at least one application, and wherein an object usage log is defined by a set of log records;
  
  b) a uniform format object usage log generator, provided with the object usage log, for generating a uniform format object usage log from the object usage log;
  
  c) a task log generator, provided with the uniform format object usage log, for generating a log of tasks by defining task boundaries in the uniform format object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  d) a task model generator, provided with the log of tasks, for generating the task model in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.
- View Dependent Claims (76)
- - 76. The apparatus of claim 75 wherein the task model generator includes:
    - i) a task distance determination unit for determining distances between tasks; and

77. An apparatus for defining a task model used as a basis for a delivery of context to a user, the task model being a clustering of similar tasks based on an object usage log defined by a set of log records, each of the log records including an identification of a stored object used by at least one application in response to user input steps, the apparatus comprising:
- a) a uniform format object usage log generator, provided with the object usage log, for generating a uniform format object usage log from the object usage log;
  
  b) a task log generator, provided with the uniform format object usage log, for generating a log of tasks by defining task boundaries in the uniform format object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  c) a task model generator, provided with the log of tasks, for generating the task model in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.
- View Dependent Claims (78)
- - 78. The apparatus of claim 77 wherein the task model generator includes:

79. An apparatus for defining a task model used as a basis for a delivery of context to a user, the task model being a clustering of similar tasks based on stored objects used by an application in response to user input steps, the apparatus comprising:
- a) an object usage log generator for generating a log record when the application uses a stored object, wherein the log record includes an identification of the stored object used by the application, and wherein an object usage log is defined by a set of log records;
  
  b) a task log generator, provided with the object usage log, for generating a log of tasks by defining task boundaries in the object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  c) a task model generator, provided with the log of tasks, for generating a task model in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.
- View Dependent Claims (80)
- - 80. The apparatus of claim 79 wherein the task model generator includes:

81. An apparatus for defining a task model used as a basis for a delivery of context to a user, the task model being a clustering of similar tasks based on an object usage log defined by a set of log records, each of the log records including an identification of a stored object used by an application in response to user input steps, the apparatus comprising:
- a) a task log generator, provided with the object usage log, for generating a log of tasks by defining task boundaries in the object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  b) a task model generator, provided with the log of tasks, for generating the task model in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.
- View Dependent Claims (82, 89, 90, 91)
- - 82. The apparatus of claim 81 wherein the task model generator includes:
89. The apparatus of claim 81 wherein the task clustering unit includes:
- i) means for determining least distant tasks and clustering them;
  
  ii) means for determining distances between (a) tasks, (b) clusters, and (c) tasks and clusters;
  
  iii) means, provided with determined distances from the means for determining distances, for determining a minimum of the distances determined; and
  
  iv) means, provided with the minimum of distances determined, for clustering the (a) tasks, (b) clusters, or (c) tasks and clusters associated with the minimum distance if the minimum distance is less than a predetermined threshold.
90. The apparatus of claim 81 wherein the task clustering unit includes:
- i) means for determining least distant tasks and clustering them;
  
  ii) means for determining distances between (a) tasks, (b) clusters, and (c) tasks and clusters;
  
  iii) means, provided with the determined distances from the means for determining distances, for determining a minimum of the distances determined; and
  
  iv) means, provided with the minimum of the distances determined, for clustering the (a) tasks, (b) clusters, or (c) tasks and clusters associated with the minimum distance if a number of clusters is greater than a predetermined threshold.
91. The apparatus of claim 81 wherein the task clustering unit includes:
- i) means for determining least distant tasks and clustering them;
  
  ii) means for determining distances between (a) tasks, (b) clusters, and (c) tasks and clusters;
  
  iii) means, provided with the predetermined distances from the mean for determining distances, for determining a minimum of the distances determined; and
  
  iv) means, provided with the minimum of the distances determined, for clustering the (a) tasks, (b) clusters, or (c) tasks and clusters associated with the minimum distance if the minimum distance is less than a first predetermined threshold and if a number of clusters is greater than a second predetermined threshold.

83. An apparatus for generating a task model in which similar tasks are clustered, the task model used as a basis for delivery of context to the user, the apparatus comprising:
- a) a task distance determination unit for determining distances between tasks; and
  
  b) a task clustering unit for clustering tasks based on the distances determined.
- View Dependent Claims (84, 85, 86, 87, 88)
- - 84. The apparatus of claim 83 wherein the task distance determination unit includes:
85. The apparatus of claim 84 wherein each of the tasks is represented by a relation of related entities having known or variable values and wherein the means for representing each of the tasks as a graph includes:
- A) means for defining a vertex for each entity and each relation;
  
  B) means for merging vertices having entities with a variable value; and
  
  C) means for defining edges to connect related entities and entities that are instances of a relation.
86. The apparatus of claim 85 wherein the means for determining a distance between graphs includes:
- A) means for determining an intersection of the graphs;
  
  B) means for determining a difference between the graphs;
  
  C) means for determining connected elements of the difference;
  
  D) means for determining the distance based on the connected elements and the intersection, wherein the distance increases as a number of the connected elements increases.
87. The apparatus of claim 86 wherein the distance between two graphs, A and B, is defined by the expression:
- $distance (A, B) = \sum_{i ɛ all graph pieces}^{} v^{\langle c_{i} \rangle}$ where v is a parameter greater than 1 and c_iis the number of connected elements in piece i of the difference graph A−
  
  B.
88. The apparatus of claim 86 wherein the distance between two graph, A and B, is defined by the expression:
- $distance (A, B) = \frac{\max [d * (A, B), d * (B, A)]}{n_{intersect}}$ wherein n_intersectis the number of vertices and edges in A∩
  
  B, wherein $d * (A, B) = \sum_{i ɛ all graph pieces}^{} v^{\langle c_{i} \rangle}$ where v is parameter greater than 1 and c_iis the number of connected elements in piece i of the difference A−
  
  B, and, wherein $d * (B, A) = \sum_{i ɛ all graph pieces}^{} v^{\langle c_{i}^{'} \rangle}$ where v is parameter greater than 1 and c′
  
  _iis the number of connected elements in piece i of the difference graph B−
  
  A.

92. A computer readable medium having computer executable instructions which, when executed by a computer, perform steps for defining tasks and clustering similar tasks based on stored objects used by at least one application in response to user input steps, the steps comprising:
- a) generating a log record when the at least one application uses a stored object, wherein the log record includes an identification of the stored object used by the at least one application, and wherein an object usage log is defined by a set of log records;
  
  b) generating a uniform format object usage log from the object usage log;
  
  c) generating a log of tasks by defining task boundaries in the uniform format object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  d) generating a task model in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.

93. A computer readable medium having computer executable instructions which, when executed by computer, perform steps for defining a task model used as a basis for a delivery of context to a user, the task model being a clustering of similar tasks based on an object usage log defined by a set of log records, each of the log records including an identification of a stored object used by at least one application in response to user input steps, the steps comprising:
- a) generating a uniform format object usage log from the object usage log;
  
  b) generating a log of tasks by defining task boundaries in the uniform format object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  c) generating the task model in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.

94. A computer readable medium having computer executable instructions which, when executed by a computer, perform steps for defining a task model used as a basis for a delivery of context to a user, the task model being a clustering similar tasks based on stored objects used by an application in response to user input steps, the steps comprising:
- a) generating a log record when the application uses a stored object, wherein the log record includes an identification of the stored object used by the application, and wherein an object usage log is defined by a set of log records;
  
  b) generating a log of tasks by defining task boundaries in the object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  c) generating a task model in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.

95. A computer readable medium having computer executable instructions which, when executed by computer, perform steps for defining a task model used as a basis for a delivery of context to a user, the task model being a clustering of similar tasks based on an object usage log defined by a set of log records, each of the log records including an identification of a stored object used by an application in response to user input steps, the steps comprising:
- a) generating a log of tasks be defining task boundaries in the object usage log, wherein the log of tasks is defined by records having a task identifier; and
  
  b) generating the task model in which similar tasks are clustered, wherein the task model includes records having a task identifier and a cluster identifier.

96. A computer readable medium having computer executable instructions which, when executed by a computer, perform steps for generating a task model in which similar tasks are clustered, the task model used as a basis for a delivery of context to a user, the steps comprising:
- a) determining distances between tasks; and
  
  b) clustering tasks based on the distances determined.

97. A computer readable medium for storing a data structure comprising:
- a) a first field functioning to identify one or more user inputs; and
  
  b) a second field functioning to identify a task associated with the first field.

98. A computer readable medium for storing a data structure comprising:
- a) a first field functioning to identify a task; and
  
  b) a second field functioning to identify a cluster to which the task identified in the first field belongs.
- View Dependent Claims (99)
- - 99. The computer readable medium for storing a data structure of claim 98 further comprising:

100. A computer readable medium for storing a data structure comprising:
- a) a first field functioning to identify a cluster of tasks; and
  
  b) a second field functioning to identify a probability that a user will want to perform a task within the cluster of tasks identified in the first field.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Microsoft Technology Licensing LLC (Microsoft Corporation)
Original Assignee
Microsoft Corporation
Inventors
Ingerman, David, Jung, Edward K., Ridgeway, Greg, Wu, Lani F., Altschuler, Steven J.
Primary Examiner(s)
STARKS, WILBERT L

Application Number

US09/325,169
Time in Patent Office

1,902 Days
Field of Search

700/29, 235/419, 706/55
US Class Current

706/55
CPC Class Codes

G06Q 10/06 Resources, workflows, human...

G06Q 30/02 Marketing; Price estimation...

Methods and apparatus for analyzing computer-based tasks to build task models

First Claim

2 Assignments

0 Petitions

Accused Products

Abstract

95 Citations

100 Claims

Specification

Solutions

Use Cases

Quick Links

Methods and apparatus for analyzing computer-based tasks to build task models

First Claim

2 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

95 Citations

100 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links