Generating a set of representative items using a maximum-set-coverage selection strategy

Patent metadata

Field	Value
Publication number	US-10248712-B1
Application number	US-201615162365-A
Country	US
Kind code	B1
Filing date	May 23, 2016
Priority date	May 23, 2016
Publication date	Apr 2, 2019
Grant date	Apr 2, 2019

Abstract

Systems and methods are directed to a computing device for selecting a set of representative items from a set of items using a maximum-set-coverage selection strategy. The computing device may derive an associated collection of elements from the set of items. The computing device may determine a marginal utility value for the item based on elements related to the review. The computing device may similarly determine the marginal utility value for each item in the set and may select the item in the set having the highest marginal utility value. The computing device may remove elements related to the selected item from the associated collection of elements, determine updated marginal utility values for the items based on the remaining elements, and select another item having the highest updated marginal utility value. The computing device may repeat the above process until a number of items that is desired has been selected.

First claim

What is claimed is:

1. A computing system comprising:
a memory configured to store processor-executable instructions; and
a processor in communication with the memory and configured to execute the processor-executable instructions to perform operations comprising:
receiving, from another computing device, a value indicative of the number of reviews desired for presentation on the other computing device;
deriving an associated collection of elements from a set of reviews, wherein each element in the associated collection of elements is related to a review in the set of reviews;
for each review of the set of reviews, identifying a set of elements related to the review based at least in part on the associated collection of elements;
for each review of the set of reviews, determining a marginal utility value of the review based at least in part on the set of elements, in the associated collection of elements, that is related to the review;
selecting, from the set of reviews, a set of representative reviews based at least in part on the value indicative of the number of reviews desired for presentation and the marginal utility values of the reviews in the set of reviews;
determining that the number of reviews in the set of representative reviews corresponds to the value indicative of the number of reviews desired for presentation; and
providing the set of representative reviews to the other computing device for presentation via a user interface.

2. The computing system of claim 1 , wherein the operations further comprise ranking the reviews in the set of representative reviews.

3. The computing system of claim 1 , wherein an element in the associated collection of elements comprises one of a word, a portion of a word, a token, a type of media, or a characteristic of a user associated with the review.

4. The computing system of claim 1 , wherein the associated collection of elements comprises a plurality of words included in the set of reviews.

5. A computer-implemented method comprising:
deriving an associated collection of elements from a set of reviews of an item, wherein each element in the associated collection of elements is related to review in the set of reviews;
for each review of the set of reviews:
identifying an element, in the associated collection of elements, that is related to the review, and
determining a marginal utility value for the review based at least in part on the element, in the associated collection of elements, that is related to the review;

identifying, from among the set of reviews, a review having a highest marginal utility value;
identifying, from the associated collection of elements, an element related to the review having the highest marginal utility value; and
modifying, from the associated collection of elements, an element related to the review having the highest marginal utility value.

6. The computer-implemented method of claim 5 , further comprising providing the review having the highest marginal utility value to a computing device for presentation.

7. The computer-implemented method of claim 5 , further comprising, for each review of the set of reviews, determining an updated marginal utility value for the review based at least in part on a remaining element, in the associated collection of elements, that is related to the review.

8. The computer-implemented method of claim 7 , further comprising:
determining, from among the set of reviews, a review having a highest updated marginal utility value; and
modifying, from the associated collection of elements, an element that is related to the review having the highest updated marginal utility value.

9. The computer-implemented method of claim 8 , further comprising providing the review having the highest marginal utility value and the review having the highest updated marginal utility value to a computing device for presentation.

10. The computer-implemented method of claim 5 , wherein determining the marginal utility value for the review based at least in part on the element, in the associated collection of elements, that is related to the review comprises:
determining a number of elements included in the associated collection of elements that are related to the review; and
determining the marginal utility value for the review based at least in part on said number.

11. The computer-implemented method of claim 5 , further comprising determining a weight for each element in the associated collection of elements.

12. The computer-implemented method of claim 11 , wherein a weight of the element, in the associated collection of elements, related to the review is based at least in part on at least one of:
an amount of space required to display the element on a user interface of a computing device;
an amount of available space to display the element on the user interface of the computing device;
a size of the user interface of the computing device; or
a number of reviews that are related to the element.

13. The computer-implemented method of claim 11 , wherein determining the marginal utility value for the review based at least in part on the element, in the associated collection of elements, related to the review comprises:
determining a value of the element;
determining a weight of the element;
applying the weight of the element to the value of the element to determine a weighted value of the element; and
determining the marginal utility value for the review based at least in part on weighted value of the element.

14. The computer-implemented method of claim 13 , further comprising determining an updated weight for each element of a remaining set of elements included in the associated collection of elements in response to modifying the element related to the review having the highest marginal utility value from the associated collection of elements.

15. A non-transitory, computer-readable medium having stored thereon computer-executable software instructions configured to cause a processor of a computing device to perform operations comprising:
deriving an associated collection of elements from a set of reviews, wherein each element in the associated collection of elements is related to a review in the set of reviews;
for each review of the set of reviews:
identifying an element, in the associated collection of elements, that is related to the review, and
determining a marginal utility value for the review based at least in part on the element, in the associated collection of elements, that is related to the review;

determining, from among the set of reviews, a review having a highest marginal utility value; and
modifying, from the associated collection of elements, an element related to the review having the highest marginal utility value.

16. The non-transitory, computer-readable medium of claim 15 , wherein deriving the associated collection of elements from the set of reviews comprises:
for each review in the set of reviews:
determining a word included in the review,
determining that the word is not included in the associated collection of elements, and
including the word in the associated collection of elements.

17. The non-transitory, computer-readable medium of claim 16 , wherein deriving the associated collection of elements from the set of reviews further comprises:
obtaining a set of common words; and
modifying one or more words included in the set of common words from the associated collection of elements.

18. The non-transitory, computer-readable medium of claim 15 , wherein deriving the associated collec

Assignees

• Amazon Tech Inc

Inventors

• Cheng Weiwei

Classifications

• G06F16/243

  Natural language query formulation · CPC title

• G06F16/285 Primary

  Clustering or classification · CPC title

• G06F17/30598 Primary

  Physics · mapped topic

• G06F17/30401

  Physics · mapped topic