Optimized rule based constraints for collaborative filtering systems

• US 7,461,058 B1
• Filed: 09/24/1999
• Issued: 12/02/2008
• Est. Priority Date: 09/24/1999
• Status: Expired due to Fees

• Current Assignee: CDN Innovations, LLC (IP Investments Group LLC)
• Original Assignee: Thalveg Data Flow LLC (Intellectual Ventures LLC)
• Inventors: Guralnik, Valerie, Rauser, John
• Primary Examiner(s): Wassum; Luke S
• Application Number:
  US09/404,597
• Time in Patent Office: 3,357 Days
• Field of Search: 705/27, 705/10, 707 1- 10, 706 45- 61
• US Class Current: 1/1
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Methods, systems, and articles of manufacture consistent with the present invention provide a recommendation server that receives a recommendation request from a user of a client computer. The recommendation server contains software to provide recommendations to the user. To provide the recommendations, the recommendation server applies a constraint filter and a recommendation filter on a set of items.

Claims

1. A computer-implemented method for providing a recommendation list from a plurality of items, comprising:

receiving an adaptable constraint to apply during searches performed in response to recommendation requests, wherein the adaptable constraint includes a plurality of free variables;

receiving a recommendation request including a plurality of values defined by a user, wherein the plurality of values includes at least one value for each of the plurality of free variables in the adaptable constraint;

binding the received values to the corresponding free variables to update the adaptable constraint;

searching the plurality of items in response to the received recommendation request, wherein a set of search parameters is defined by the updated adaptable constraint, and wherein the searching includes;

determining an order for applying a recommendation filter and a constraint filter using a cost calculation based at least on (i) a number of results required, (ii) a probability that a randomly selected item of the plurality of items will pass the second applied filter of the recommendation filter and the constraint filter, (iii) a cost of applying the first applied filter of the recommendation filter and the constraint filter to generate a single item, and (iv) a cost of applying the second applied filter to the single item;

selecting an item from the plurality of items and, in the determined order,

applying the constraint filter, comprising determining if the item satisfies the updated adaptable constraint for the recommendation request, and

applying the recommendation filter, comprising computing a predicted value based on the recommendation filter and determining if the predicted value exceeds a predetermined number,

wherein if the item does not pass the first applied filter, the item is discarded; and

appending the item to the recommendation list if the item passes both filters; and

transmitting the recommendation list for presentation on a device.

2. The method of claim 1, wherein said selecting and appending are repeated until the recommendation list includes a predetermined number of items.

3. The method of claim 1, wherein applying the constraint filter further includes applying a constraint including a Boolean expression.

4. The method of claim 1, wherein applying the constraint filter further includes applying a constraint to including an equality expression.

5. The method of claim 1, wherein applying the constraint filter further includes applying a constraint to including a category membership expression.

6. The method of claim 1, wherein computing the predicted value further includes evaluating the item with collaborative filtering.

7. The method of claim 1, wherein receiving the adaptable constraint further includes:

obtaining a constraint; and

storing the constraint in memory.

8. The computer-implemented method of claim 1, wherein a free variable in the plurality of free variables for the adaptable constraint includes a set of possible values to be selected by the user.

9. The computer-implemented method of claim 1, further comprising:

building a constraint to apply to recommendation requests using constraint forming rules, wherein the constraint includes a plurality of free variables.

10. The computer-implemented method of claim 1, wherein the cost calculation is determined according to the equation:

cost=(number of results required/probability that a randomly selected item will pass the second applied filter)*(cost of applying the first filter to generate a single item+cost of applying the second filter to the single item).

11. The computer implemented method according to claim 1, wherein the cost calculation is based at least on a predetermined relationship among (i) a number of results required, (ii) a probability that a randomly selected item of the plurality of items will pass the second applied filter of the recommendation filter and the constraint filter, (iii) a cost of applying the first applied filter of the recommendation filter and the constraint filter to generate a single item, and (iv) a cost of applying the second applied filter to the single item.

12. An apparatus for providing a recommendation list from a plurality of items in a data processing system, comprising:

a processing component configured to process instructions for selecting items from the plurality of items, wherein the processing component includes;

a constraint filter including at least one constraint having a plurality of free variables, wherein a value for each free variable is defined by a user;

a recommendation filter; and

an order determination module configured to determine an order for applying the constraint filter and the recommendation filter using a cost calculation based at least on (i) a number of results required, (ii) a probability that a randomly selected item will pass the second applied filter of the constraint filter and the recommendation filter, (iii) a cost of applying the first applied filter of the recommendation filter and the constraint filter to generate a single item, and (iv) a cost of applying the second applied filter to the single item;

an input component configured to receive a recommendation request including a value defined by the user for each of the free variables in the constraint;

a recommender component configured to perform a search in response to a received recommendation request, wherein a set of search parameters is defined by the constraint, and to generate a recommendation list based on the constraint filter and the recommendation filter; and

an output component configured to transmit the generated list for presentation on a device.

13. The apparatus of claim 12, wherein the processing component further includes a prediction module configured to compute the predicted values based on the recommendation filter.

14. The apparatus of claim 12, wherein the order determination module is further configured to determine a lowest cost order.

15. The apparatus of claim 12, wherein the at least one constraint includes a Boolean expression.

16. The apparatus of claim 12, wherein the at least one constraint includes a category membership expression.

17. The apparatus of claim 12, wherein the at least one constraint includes an equality expression.

18. The apparatus of claim 12, wherein the recommendation filter includes a collaborative filtering module that computes predicted values by evaluating ones of the plurality of items.

19. The apparatus of claim 12, wherein the recommender component is further configured to search until the recommendation list includes a predetermined number of items.

20. The apparatus of claim 12, further comprising an input component configured to:

obtain a constraint; and

store the constraint in a memory.

21. The apparatus of claim 12, wherein the processing component is further configured to adaptively specify the constraint filter, using a set of constraint-forming rules.

22. The apparatus of claim 12, wherein the cost calculation is determined according to the equation:

cost=(number of results required/probability that a randomly selected item will pass the second applied filter)*(cost of applying the first filter to generate a single item+cost of applying the second filter to the single item).

23. The apparatus of claim 12, wherein the cost calculation is based at least on a predetermined relationship among (i) a number of results required, (ii) a probability that a randomly selected item of the plurality of items will pass the second applied filter of the recommendation filter and the constraint filter, (iii) a cost of applying the first applied filter of the recommendation filter and the constraint filter to generate a single item, and (iv) a cost of applying the second applied filter to the single item.

24. A computer-implemented method of generating recommendation lists from a plurality of items having assigned category memberships representing attributes of the items, comprising:

receiving a plurality of recommendation requests;

applying, during a search of the plurality of items performed for each recommendation request, a series of filters to each of the items, the series comprising a constraint filter and a recommendation filter for furnishing a predicted rating value, wherein the recommendation filter and the constraint filter are applied in an order determined using a cost calculation based at least on (i) a number of results required, (ii) the probability that a randomly selected item will pass the second applied filter of the recommendation filter and the constraint filter, (iii) a cost of applying the first applied filter of the recommendation filter and the constraint filter to generate a single item, and (iv) a cost of applying a second applied filter to the single item,

wherein the constraint filter is selected based on attributes associated with the recommendation request, wherein the constraint filter applies a constraint to the parameters of the search, the constraint having a plurality of free variables each free variable in the plurality of free variables has a value defined by the user;

generating, for each recommendation request, a recommendation list based on the predicted rating value for the item that passes the constraint filter and the recommendation filter; and

for each recommendation request, transmitting the generated list to a user for presentation on a device.

25. The method of claim 24, further comprising:

building a constraint using constraint forming rules; and

incorporating the constraint into the constraint filter.

26. The method of claim 24 wherein the recommendation filter and the constraint filter are applied in a lowest cost order.

27. The method of claim 24, wherein generating the recommendation list comprises generating a list of recommendations based on predicted rating values of the items that pass the constraint filter and the recommendation filter being in excess of a specified rating value.

28. The method of claim 24, wherein generating the recommendation list comprises generating a list of recommendations based on a specified number of the items that pass the constraint filter and the recommendation filter with highest predicted rating values.

29. The computer-implemented method of claim 24, wherein the cost calculation is determined according to the equation:

cost=(number of results required/probability that a randomly selected item will pass the second applied filter)*(cost of applying the first filter to generate a single item+cost of applying the second filter to the single item).

30. The computer implemented method according to claim 24, wherein the cost calculation is based at least on a predetermined relationship among (i) a number of results required, (ii) a probability that a randomly selected item of the plurality of items will pass the second applied filter of the recommendation filter and the constraint filter, (iii) a cost of applying the first applied filter of the recommendation filter and the constraint filter to generate a single item, and (iv) a cost of applying the second applied filter to the single item.

31. A method of generating a recommendation list from plurality of items having assigned category memberships representing attributes of the items, comprising:

building a constraint using constraint forming rules, wherein the constraint includes a plurality of free variables;

receiving a recommendation request including a plurality of values defined by a user, wherein the plurality of values includes at least one value for each of the plurality of free variables in the constraint;

binding the received values to the corresponding free variables to update the constraint;

incorporating the constraint into a constraint filter;

determining a cost for a first order based at least on (i) a number of results required, (ii) a probability that a randomly selected item will pass the recommendation filter, (iii) a cost of applying the constraint filter to generate a single item, and (iv) a cost of applying the recommendation filter to the single item the first order being applying the constraint filter before applying the recommendation filter;

determining a cost for a second order based at least on (i) a number of results required, (ii) a probability that a randomly selected item will pass the constraint filter, (iii) a cost of applying the recommendation filter to generate a single item, and (iv) a cost of applying the constraint filter to the single item, the second order being applying the recommendation filter before applying the constraint filter;

establishing one of the first and second orders as the lowest cost order based on the respective costs thereof;

applying a series of filters to each of the plurality of items during a search performed in response to the recommendation request, the series comprising the recommendation filter and the updated constraint filter in the lowest cost order, wherein a set of parameters for the search is defined by the constraint;

generating a list of recommendations based on the predicted rating values for the items that pass the constraint filter and the recommendation filter; and

transmitting the generated list to the user for presentation on a device.

32. The method of claim 31, wherein a free variable in the plurality of free variables for the adaptable constraint includes a set of possible values to be selected by the user.

33. The method of claim 31, wherein the cost calculation is determined according to the equation:

cost=(number of results required/probability that a randomly selected item will pass the second applied filter)*(cost of applying the first filter to generate a single item+cost of applying the second filter to the single item).

34. The method according to claim 31, wherein the cost for the first order is based at least on a predetermined relationship among (i) a number of results required, (ii) a probability that a randomly selected item of the plurality of items will pass the recommendation filter, (iii) a cost of applying the constraint filter to generate a single item, and (iv) a cost of applying the recommendation filter to the single item, and

wherein the cost for the second order is based at least on a predetermined relationship among (i) a number of results required, (ii) a probability that a randomly selected item of the plurality of items will pass the constraint filter, (iii) a cost of applying the recommendation filter to generate a single item, and (iv) a cost of applying the constraint filter to the single item.

35. A computer program product comprising a computer readable storage medium including control logic stored therein, the control logic enabling the generation of a recommendation list, by a method comprising:

receiving an adaptable constraint to apply during searches performed in response to recommendation requests, wherein the adaptable constraint includes a plurality of free variables;

receiving a recommendation request including a plurality of values defined by a user, wherein the plurality of values includes at least one value for each of the plurality of free variables in the adaptable constraint;

binding the received values to the corresponding free variables to update the adaptable constraint; and

searching a plurality of items in response to the received recommendation request, wherein a set of search parameters is defined by the updated adaptable constraint, comprising;

determining an order of applying a recommendation filter and a constraint filter using a cost calculation based at least on (i) a number of results required, (ii) a probability that a randomly selected item will pass a second applied filter of the recommendation filter and the constraint filter, (iii) a cost of applying the first applied filter of the recommendation filter and the constraint filter to generate a single item, and (iv) a cost of applying the second applied filter to the single item;

selecting an item from the plurality of items,

applying a first filter of the recommendation filter and the constraint filter according to the determined order,

if the item does not pass the first applied filter, discarding the item,

if the item passes the first applied filter, applying the second filter of the recommendation filter and the constraint filter according to the determined order, and

if the item passes both the first and second filters, appending the item to the recommendation list.

36. The computer program product of claim 35, wherein the cost calculation is determined according to the equation:

cost=(number of results required/probability that a randomly selected item will pass the second applied filter)*(cost of applying the first filter to generate a single item+cost of applying the second filter to the single item).

37. The computer program product of claim 35, wherein the cost calculation is based at least on a predetermined relationship among (i) a number of results required, (ii) a probability that a randomly selected item of the plurality of items will pass the second applied filter of the recommendation filter and the constraint filter, (iii) a cost of applying the first applied filter of the recommendation filter and the constraint filter to generate a single item, and (iv) a cost of applying the second applied filter to the single item.

38. A method for providing a recommendation list, comprising:

receiving a recommendation request including a value corresponding to a free variable of a constraint; and

generating a recommendation list of at least one item of a plurality of items in response to the recommendation request, comprising;

determining an order for applying a constraint filter, including the constraint, and a recommendation filter, based at least on (i) a number of results required, (ii) a probability that a randomly selected item of the plurality of items will pass a second applied filter of the recommendation filter and the constraint filter, (iii) a cost of applying the first applied filter of the recommendation filter and the constraint filter to generate a single item, and (iv) a cost of applying the second applied filter to the single item;

selecting an item from the plurality of items;

applying a first filter of the recommendation filter and the constraint filter according to the determined order;

applying a second filter of the recommendation filter and the constraint filter according to the determined order if the item passes the first filter; and

appending the item to the recommendation list if the item passes both the first filter and the second filter.

39. The method according to claim 38, wherein the cost calculation is based at least on a predetermined relationship among (i) a number of results required, (ii) a probability that a randomly selected item of the plurality of items will pass the second applied filter of the recommendation filter and the constraint filter, (iii) a cost of applying the first applied filter of the recommendation filter and the constraint filter to generate a single item, and (iv) a cost of applying the second applied filter to the single item.