Methods and systems for performing time-partitioned collaborative filtering

• US 9,639,616 B2
• Filed: 10/02/2012
• Issued: 05/02/2017
• Est. Priority Date: 10/10/2011
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Palmert, Joel
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Morris, John J
• Application Number:
  US13/633,730
• Publication Number:
  US 20130091151A1
• Time in Patent Office: 1,673 Days
• Field of Search: 707706, 7079991, 70799905, 707999101, 70799902, 707750, 709207, 709219, 706 52
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering

Abstract

In accordance with disclosed embodiments, there are provided methods, systems, and apparatuses for performing time-partitioned collaborative filtering in an on-demand service environment including, for example, receiving as input, a plurality of access requests for data stored within the host organization and a corresponding plurality of actions for the data to which access is requested; accessing an input table having a time field, action field, item field, and agent field therein; recording time data and agent data for each of the received plurality of access requests and the corresponding plurality of actions; recording an item within the item field and an action within the action field for each of the received plurality of access requests and the corresponding plurality of actions based on the action performed on an item of the data to which access is requested; and analyzing the input table to generate one or more pairs of first actions and items to second actions and items and a time based score for each of the one or more pairs, in which the time based score is dependent upon a time between the actions for each of the one or more pairs. Other related embodiments are disclosed.

Claims

1. A method executed by a system having at least a processor and a memory therein, wherein the method comprises:

receiving as input at the system, a plurality of access requests by a plurality of users for data stored by the system;

determining a corresponding plurality of actions associated with the data to which access is requested by a first user to generate a plurality of related pairs by the first user from the plurality of access requests received as input and the data stored by the system, each of the plurality of related pairs including (i) a respective first action and item, (ii) a respective second action and item and (iii) a time difference between access requests by the first user for the related pair determined based on time data for each of the respective first action and item accessed by the first user and the respective second action and item as accessed by the first user;

generating additional related pairs by one or more additional users from the plurality of access requests for the additional users;

wherein every related pair among the plurality of related pairs corresponds to exactly one of the plurality of users in which both first and second access requests for every one of the plurality of related pairs are associated with a same user for the respective pair;

partitioning the generated plurality of related pairs into a plurality of overlapping time chunks;

iteratively analyzing the generated plurality of related pairs, wherein each iteration of analysis evaluates only related pairs within a single one of the plurality of overlapping time chunks, wherein each iteration of analysis comprises generating a predictive value for the related pairs within the single one of the plurality of overlapping time chunks being analyzed by decreasing a weighting for the related pairs having elements farther apart in time based on the time difference of each related pair and by increasing the weighting of the related pairs having elements closer in time to one another based on the time difference of each related pair; and

summing the weightings from all of the plurality of overlapping time chunks to establish a time based score for each related pair, wherein the time based score for each related pair indicates the predictive value for the related pair.

2. The method of claim 1:

wherein an agent corresponds to a user having initiated the action on the item; and

wherein an input table records each of (i) agent, (ii) action, (iii) item, and (iv) time, for each of the plurality of access requests received as input.

3. The method of claim 1, wherein the analyzing comprises generating a collaborative filter table as output having the related pairs recorded therein based on the analyzing.

4. The method of claim 1, wherein the analyzing comprises generating a collaborative filter table as output, wherein the collaborative filter table records as output for each of the related pairs:

(i) action_a;

(ii) item_a subjected to action_a by any entity;

(iii) action_b;

(iv) item_b subjected to action_b by the same entity; and

(v) the time based score having been derived based at least in part on a time difference between item_a subjected to action_a and item_b subjected to action_b by the same entity.

5. The method of claim 1, wherein the analyzing comprises outputting, for each of the related pairs:

a first action and a first item and a second action and a second item as a related pair when an entity performing the first action on the first item as the data requested with a first access request also performs the second action on the second item as the data requested with a second access request by the same entity; and

the time based score having been based at least in part on a difference between first time data recorded for the first action on the first item and second time data recorded for the second action on the second item.

6. The method of claim 1, further comprising:

increasing scoring for pairs having elements occurring closer in time to one another over pairs having elements occurring greater in time;

determining a difference between first time data recorded for a first action on a first item of the pair and second time data recorded for a second action on a second item of the pair; and

performing one of the following special case operations to the difference;

(a) applying a linear weighting to the difference of the pair, wherein pairs having elements closer in time to one another result in a greater linear weighting over pairs having elements occurring greater in time from one another;

(b) applying a weighting proportional to a function f of the time difference, wherein f is monotonically decreasing so that a greater time difference results in a lower score;

(c) applying an exponential weighting function f where f=2^(−

k*timeDiff);

or

(d) applying a squared weighting function f where f=timeDiff^(−

0.5).

7. The method of claim 1, wherein the analyzing comprises

establishing a pair when any entity performing a first action on a first item also performs a second action on a second item;

and

applying a weighted time based score to the pair established based on a difference between first time data recorded for the first action on the first item and second time data recorded for the second action on the second item.

8. The method of claim 7, further comprising:

establishing a second pair, identical to the first pair, when any second entity performing a first action on a first item also performs a second action on a second item;

applying a second weighted time based score to the second pair established based on a difference between third time data recorded for the first action on the first item and fourth time data recorded for the second action on the second item; and

summing the first weighted time based score for the first pair and the second weighted time based score for the second pair, wherein the summing represents both frequency of the established pairs and time relatedness of the established pairs'"'"' respective elements.

9. The method of claim 1, further comprising:

recording time data within the time field for each of the received plurality of access requests and the corresponding plurality of actions by one of;

(a) recording a time stamp representing when each item is accessed;

(b) recording a time stamp representing when each action is performed on the corresponding item of the data to which access is requested; and

(c) recording both (a) and (b).

10. The method of claim 1, wherein the analyzing comprises:

applying a weighted time based score to every instance for a pair in which a first item subjected to a first action by any entity is matched to a second item subjected to a second action by the same entity;

summing all weighted time based scores for every instance of the pair resulting in a summed score for all instances of the pair, wherein every instance of the pair contributes to the summed score, and further wherein instances of the pair having a smaller time difference between the first action and second action contribute greater to the summed score than instances of the pair having a greater time difference between the first action and the second action.

11. The method of claim 1, wherein the analyzing comprises:

eliminating any instance of a pair from scoring when a time difference between a first action and a second action for the instance of the pair exceeds a time threshold or is less than a score threshold, where the score threshold is proportional to the time threshold according to a weighting function f;

applying a weighted time based score to every remaining instance for the pair in which the time difference between the first action and the second action for the instance of the pair is within the time threshold; and

summing all weighted time based scores for every remaining instance of the pair resulting in a summed score for all remaining instances of the pair, wherein remaining instances of the pair having a smaller time difference between the first action and second action contribute greater to the summed score than remaining instances of the pair having a greater time difference between the first action and the second action.

12. The method of claim 1, wherein the method further comprises:

indexing at least a time field of an input table; and

wherein the analyzing comprises;

terminating a query prematurely based on the indexed time field exceeding a time threshold indicating permissible records for consideration by the analyzing.

13. The method of claim 1, wherein the analyzing comprises:

executing an SQL query to;

count all pairs;

group all pairs by action_a/item_a and action_b/item_b; and

filter via a WHERE clause of the SQL query to negate any pairs exceeding a time threshold based on the time field.

14. The method of claim 13, wherein the WHERE clause of the SQL query is to further:

filter out any instances of a pair having a negative time difference indicating action_b/item_b occurred prior in time to action_a/item_a.

15. The method of claim 1, wherein the analyzing comprises:

instituting a directionality requirement for establishment of a pair such that a first action and item that occurs in time before a second action and item represents a valid pair but the second action and item occurring in time before the first action and item is not a valid pair.

16. The method of claim 1, wherein the method further comprises:

recording time data within the time field for each of the received plurality of access requests and the corresponding plurality of actions; and

wherein the analyzing comprises;

applying the analyzing to the plurality of overlapping time chunks, based on the time data recorded.

17. The method of claim 16, wherein applying the analyzing to the plurality of overlapping time chunks comprises:

incrementally analyzing the input table by iteratively performing the analyzing against the input table for each of the plurality of overlapping time chunks, wherein each iteration comprises;

(a) selecting one of the plurality of overlapping time chunks having records therein corresponding to a period of time subsequent to the preceding incremental analyzing based on the time data recorded; and

(b) analyzing the selected one of the plurality of overlapping time chunks without re-analyzing the remaining plurality of overlapping time chunks having records therein corresponding to a period of time during or prior to the preceding incremental analyzing based on the time data recorded.

18. The method of claim 1, further comprising:

receiving from a user, a view request for a record specified by the user; and

sending to the user, unsolicited recommendations for records to be viewed by the user based on the analyzing and based further on the record currently being viewed by the user and/or records recently viewed by the user.

19. The method of claim 1, further comprising:

receiving as input, the plurality of access requests from one or more client devices, each of the one or more client devices being communicably interfaced with a host organization having the system therein via a network; and

sending unsolicited recommendations for records to be viewed to at least one of the client devices without regard to which of the client devices are associated with any of the plurality of access requests.

20. The method of claim 1:

wherein the data stored within the system comprises the data being stored within a multi-tenant database system of a host organization; and

wherein the method further comprises;

receiving as input, the plurality of access requests from one or more client devices of a plurality of customer organizations, wherein each customer organization is an entity selected from the group consisting of;

a separate and distinct remote organization, an organizational group within the host organization, a business partner of the host organization, or a customer organization that subscribes to cloud computing services provided by the host organization.

21. The method of claim 20, wherein the multi-tenant database system comprises elements of hardware and software that are shared by a plurality of separate and distinct customer organizations, each of the separate and distinct customer organizations being remotely located from the host organization having the multi-tenant database system operating therein.

22. Non-transitory computer readable storage medium having instructions stored thereon that, when executed by a processor of a system, the instructions cause the system to perform operations comprising:

receiving as input at the system, a plurality of access requests by a plurality of users for data stored by the system;

determining a corresponding plurality of actions associated with the data to which access is requested by a first user to generate a plurality of related pairs by the first user from the plurality of access requests received as input and the data stored by the system, each of the plurality of related pairs including (i) a respective first action and item, (ii) a respective second action and item and (iii) a time difference between access requests by the first user for the related pair determined based on time data for each of the respective first action and item accessed by the first user and the respective second action and item as accessed by the first user;

generating additional related pairs by one or more additional users from the plurality of access requests for the additional users;

wherein every related pair among the plurality of related pairs corresponds to exactly one of the plurality of users in which both first and second access requests for every one of the plurality of related pairs are associated with a same user for the respective pair;

partitioning the generated plurality of related pairs into a plurality of overlapping time chunks;

iteratively analyzing the generated plurality of related pairs, wherein each iteration of analysis evaluates only related pairs within a single one of the plurality of overlapping time chunks, wherein each iteration of analysis comprises generating a predictive value for the related pairs within the single one of the plurality of overlapping time chunks being analyzed by decreasing a weighting for the related pairs having elements farther apart in time based on the time difference of each related pair and by increasing the weighting of the related pairs having elements closer in time to one another based on the time difference of each related pair; and

summing the weightings from all of the plurality of overlapping time chunks to establish a time based score for each related pair, wherein the time based score for each related pair indicates the predictive value for the related pair.

23. The non-transitory computer readable storage medium of claim 22, wherein the analyzing comprises:

generating a collaborative filter table as output, wherein the collaborative filter table records as output for each of the one or more pairs;

(i) action_a;

(ii) item_a subjected to action_a by any entity;

(iii) action_b;

(iv) item_b subjected to action_b by the same entity; and

(v) the time based score having been derived based at least in part on a time difference between item_a subjected to action_a and item_b subjected to action_b by the same entity.

24. The non-transitory computer readable storage medium of claim 22, wherein the analyzing comprises:

eliminating any instance of a pair from scoring when a time difference between a first action and a second action for the instance of the pair exceeds a time threshold;

applying a weighted time based score to every remaining instance for the pair in which the time difference between the first action and the second action for the instance of the pair is within the time threshold; and

summing all weighted time based scores for every remaining instance of the pair resulting in a summed score for all remaining instances of the pair, wherein remaining instances of the pair having a smaller time difference between the first action and second action contribute greater to the summed score than remaining instances of the pair having a greater time difference between the first action and the second action.

25. The non-transitory computer readable storage medium of claim 22, wherein the instructions cause the system to perform further operations comprising:

indexing at least the time field of the input table; and

wherein the analyzing comprises;

terminating a query prematurely based on the indexed time field exceeding a time threshold indicating permissible records for consideration by the analyzing.

26. A system comprising:

a processor to execute instructions;

a request interface to receive as input at the system, a plurality of access requests for data stored by the system;

an analysis engine to determine a corresponding plurality of actions associated with the data to which access is requested by a first user to generate a plurality of related pairs by the first user from the plurality of access requests received as input and the data stored by the system, each of the plurality of related pairs including (i) a respective first action and item, (ii) a respective second action and item and (iii) a time difference between access requests by the first user for the related pair determined based on time data for each of the respective first action and item accessed by the first user and the respective second action and item as accessed by the first user;

the analysis engine to generate additional related pairs by one or more additional users from the plurality of access requests for the additional users;

wherein every related pair among the plurality of related pairs corresponds to exactly one of the plurality of users in which both first and second access requests for every one of the plurality of related pairs are associated with a same user for the respective pair;

the analysis engine to partition the generated plurality of related pairs into a plurality of overlapping time chunks;

the analysis engine to iteratively analyze the generated plurality of related pairs, wherein each iteration of analysis evaluates only related pairs within a single one of the plurality of overlapping time chunks, wherein each iteration of analysis comprises generating a predictive value for the related pairs within the single one of the plurality of overlapping time chunks being analyzed by decreasing a weighting for the related pairs having elements farther apart in time based on the time difference of each related pair and by increasing the weighting of the related pairs having elements closer in time to one another based on the time difference of each related pair; and

the analysis engine to sum the weightings from all of the plurality of overlapping time chunks to establish a time based score for each related pair, wherein the time based score for each related pair indicates the predictive value for the related pair.

27. The system of claim 26, further comprising:

a web-server to implement the request interface to receive as input, the plurality of access requests from one or more client devices from among a plurality of customer organizations communicably interfaced with a host organization having the system embodied therein via a network;

a multi-tenant database system to implement the database; and

wherein each customer organization being an entity selected from the group consisting of;

a separate and distinct remote organization, an organizational group within the host organization, a business partner of the host organization, or a customer organization that subscribes to cloud computing services provided by the host organization.