a2) United States Patent
`US 6,317,722 B1
`(10) Patent No.:
`*Nov. 13, 2001
`(45) Date of Patent:
`Jacobi et al.
`
`US006317722B1
`
`(54)
`
`(75)
`
`USE OF ELECTRONIC SHOPPING CARTS
`TO GENERATE PERSONAL
`RECOMMENDATIONS
`
`Inventors: Jennifer A. Jacobi; Eric A. Benson;
`Gregory D. Linden, all of Seattle, WA
`(US)
`
`(73)
`
`Assignee: Amazon.com,Inc., Seattle, WA (US)
`
`(*)
`
`Notice:
`
`issued on a continued pros-
`This patent
`ecution application filed under 37 CFR
`1.53(d), and is subject to the twenty year
`patent
`term provisions of 35 U.S.C.
`154(a)(2).
`
`Subject to any disclaimer, the term of this
`patent
`is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21)
`
`(22)
`
`Appl. No.: 09/156,237
`
`Filed:
`
`Sep. 18, 1998
`
`(51)
`
`Tint. C1.
`
`iccccceecccssssesesnseeeen GO6F 17/60; GO6F 17/00;
`GO6F 15/173; HO4K 1/00; HO4H 1/00
`
`US ©lisiainsnnncncaaas 705/14; 233/383; 380/24;
`455/3.1; 455/480; 705/14; 705/27; 707/102
`
`(58)
`
`(56)
`
`Field of Search .
`;
`.. 235/383; 380/24;
`455/5.1, 480:"705/14, 27; 707/3, 102; 709/227
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,870,579 © SH9S9 Hey vuiiisanininiiniivicnie 364/419
`we 364/419
`4,996,642 *
`2/1991 Hey -.ucsees
`
`8/1993 Muelleret al.
`we 364/405
`5,235,509 *
`
`5,459,306 * 10/1995 Stein et al. occ 235/383
`5,583,763 * 12/1996 Atcheson et al. ........... 364/55 1.01
`4/1998 Levineet al. ..
`. 395/200.3
`5,745,681 *
`
`5/1998 Whiteis ......
`wee 707/102
`5,749,081 *
`
`395/200.57
`5,774,670 *
`6/1998 Montulli
`8/1998 Payton cocccceecccesccsessssssssseensens 455/5.1
`5,790,935 *
`5,905,973 *
`5/1999 Yonezawa et al. ........ss0 705/27
`5,909,492 *
`6/1999 Payne et al. o..ccceccesercneceseeee 380/24
`
`FOREIGN PATENT DOCUMENTS
`
`O751471L.A *
`0827063 A *
`0265083 A *
`2336925 *
`
`cccccccccecccceceeeeesaeee GO6F/17/60
`LU/L99T CEP)
`
`..
`.. GO6F/3/00
`3/1998 (EP)
`
`..
`GO9F/27/00
`4/1988 (EP)
`creccccocccoccrererereeerenes GO06F/17/00
`3/1999 (GB)
`OTHER PUBLICATIONS
`
`“COSMOCOM”, Computer Telephony, p. 124, Jul. 1998.*
`Brier, S.E., “Smart Devices Peep Into Your Grocery Cart”,
`New York Times Co., Section G, p. 3, col.3, Circuits, Jul.
`1998.*
`Nash, E.L., “Direct Marketing; Strategy, Planning, Execu-
`tion”, 3rd Ed., McGraw-Hill, Inc., pp. 165, & 365-6, 1994.*
`“iCat Electronic Commerce Suite Takes ‘Best of Show’
`Award At WebINNOVATION 97”, PR Newswire, Jun.
`1997,*
`iCat’s Commerce Suite Makes Setting
`“iCat Corporation:
`Up Shop on Net Even Easier Than High Street”, M2
`Presswire, Feb. 1997,*
`
`(List continued on next page.)
`
`Primary Examiner—Tarig R. Hafiz
`Assistant Examiner—J Harle
`
`(74) Attorney, Agent, or Firm—Knobbe, Martens, Olson &
`Bear, LLP
`
`(57)
`
`ABSTRACT
`
`A computer-implemented service recommends products or
`other items to a user based on a set of items knownto be of
`interest to the user, such as a set of items currently in the
`user’s electronic shopping cart.
`In one embodiment,
`the
`service identifies items that are currently in the user’s
`shopping cart, and uses these items to generate a list of
`additional items that are predicted to be of interest to the
`user, Wherein an additional item is selected to include in the
`list based in-part upon whetherthat item is related to more
`than one of the items in the user’s shopping cart. The item
`relationships are preferably determined by an off-line pro-
`cess that analyzes user purchase histories to identify corre-
`lations between item purchases. The additional
`items are
`preferably displayed to the user when the user views the
`contents of the shopping cart.
`
`42 Claims, 7 Drawing Sheets
`
`WEB SITE)
`-40
`EaieanaL ‘COMPONENTS
`
`oe -44
`RECOMMENDATIONSERVICECOMPONENTS)
`
`
`iTS
`
`
`
` ee
`
`ape s
`
`TasooEneeaTON
`teros)
`
`USER PROFILES
`+ PURCHASE
`HISTORIES
`
`
`
`© TEM RATINGS:
`
`«© SHOPPING CART
`‘CONTENTS
`
`
`
`«RECENT SHOPPING
`CART CONTENTS
`
`—_—_—_—_— NN
`ITEMS
`
`
`EX1047
`Roku V. Media Chain
`U.S. Patent No. 10,489,560
`
`EX1047
`Roku V. Media Chain
`U.S. Patent No. 10,489,560
`
`

`

`US 6,317,722 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`Dragan et al., “Advice From the Web”, PC Magazine, v.16,
`n.15, p. 133, Sep, 1997.*
`“Able Solutions Announces Able Commerce 2.6”, PR
`Newswire, Sep, 1998.*
`“Internet World—IBM ‘To Expand E-Comm Features”,
`Newsbytes News Network, Dec. 1996.*
`McMains,A., “Weiss, Whitten, Staliano’s”, ADWEEK East-
`ern Edition, v.39, n.24, p. 82, Jun. 1998.*
`“Cdnow Rated Top Music Site by eMarketer, the Authority
`on Business Online”, PR Newswire, Sep, 1998.*
`Joaquin Delgado, “Intelligent Collaborative Information
`Retrieval” .*
`Joaquin Delgado, “Content-based Collaborative Informa-
`tion Filtering”.*
`Marko Balabanovic and Yoav Shoham, “Content—Based,
`Collaborative Recommendation,” Communications of the
`ACM, v 40n3, pp. 66-72, Mar. 1997,*
`Upendra Shardanand and Pattie Maes with MIT Media—Lab,
`Social Information Filtering: Algorithms for Automating
`“Word of Mouth”, 8 pgs. (undated).
`Combining Social Networks and Collaborative Filtering,
`Communications of the ACM, Mar. 1997/vol. 40, No. 3, pp.
`63-65.
`
`Pointing the Way: Active Collaborative Filtering, CHI *95
`Proceedings Papers, 11 pgs.
`
`Bradley N. Miller, John T. Riedl, Joseph A. Konstan with
`Department of Computer Science, University of Minnesota,
`Experiences with GroupLens: Making Usenet Useful Again,
`13 pgs.
`A System for Sharing Recommendations, Communications
`of the ACM, Mar. 1997/vol. 40, No. 3, pp. 59-62.
`Recommender Systems for Evaluating Computer Messages,
`Communications of the ACM, Mar. 1997/vol. 40, No. 3, pp.
`88 and 89.
`
`Content-Based, Collaborative Recommendation, Commun-
`ciations of the ACM, Mar. 1997/vol. 40, No. 3, pp. 66-72.
`Applying Collaborative Filtering to Usenet News, Commu-
`nications of the ACM, Mar. 1997/vol. 40, No. 3, pp. 77-87.
`Personalized Navigation for the Web, Communications of
`the ACM, Mar. 1997/vol. 40, No. 3, pp. 73-76.
`GroupLens: An Open Architecture for Collaborative Filter-
`ing of Netnews, 18 pgs.
`Net Perceptions,
`Inc., White Paper, Building Customer
`Loyalty and High-Yield Relationships Through GroupLens
`Collaborative Filtering, 9 pgs., Nov. 22, 1996,
`Christos Faloutsos and Douglas Oard with University of
`Maryland, A Survey of Information Retrieval and Filtering
`Methods, 22 pgs. (undated).
`
`* cited by examiner
`
`

`

`U.S. Patent
`
`Nov.13, 2001
`
`Sheet 1 of 7
`
`US 6,317,722 BL
`
`TIWNY3LX3
`||||||||||||||||||||||||||||||(JIS83MOF
`SLNSNOdNOD
`
`
`SLNINOdNODJOIAN3SSNOILVONSNNOD3Y
`
`
`
`FISVLSW3LIYVIINIS3NI1—440
`oFOF
`
`(SONIddVNW3LI-O1-N3LI)
`NOLLVONSNNOD3Y
`(22S'Z°S914)
`
`SS3ID0Ud
`
`YSHOLYANNOOE
`
`$$390¥d
`
`
`
`NOILVY3N39JT8VL
`
`SS300Ud
`
`(¢°914)
`
`hE
`
`gam
`
`YAAN3S
`
`S$31Ns0udYasn
`
`S3INOLSIH
`
`3SVHOUNd*
`
`
`
`LYVDONIddOHS
`
`SLN3LNOD
`
`SONILVHWAL!¢
`
`
`
`
`
`QNIddOHSIN3038¢
`
`
`
`SIN3INODLYVO
`
`4U7
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Nov.13, 2001
`
`Sheet 2 of 7
`
`US 6,317,722 B1
`
`GENERATE PERSONAL
`RECOMMENDATIONS
`
`60
`
`IDENTIFY ITEMS KNOWN
`
`TO BE OF INTEREST TO USER
`
`
`
`
`
`RETRIEVE SIMILAR ITEMS
`
`LIST (IF ANY) FOR EACH
`ITEM OF KNOW INTEREST
`
`
`
`WEIGHT SIMILAR
`ITEMS LIST(S)
`(OPTIONAL)
`
`
`
`COMBINE SIMILAR
`ITEMS LISTS IF
`MULTIPLE LISTS
`
`
`
`
`
`FIC.
`
`
`
`
`
`
`
`
`
`
`RECOMMEND TOP
`M ITEMS FROM
`RECOMMENDATIONS LIST
`
`
`
`
`SORT RESULTING
`
`LIST FROM HIGHEST-
`TO-LOWEST SCORE
`
`
`
`FILTER SORTED
`LIST TO GENERATE
`RECOMMENDATIONS LIST
`
` ADD ITEMS TO
`
`RECOMMENDATIONS LIST
`(OPTIONAL)
`
`

`

`U.S. Patent
`
`Nov.13, 2001
`
`Sheet 3 of 7
`
`US 6,317,722 B1
`
`BUILD SIMILAR ITEMS TABLE
`
`
`
`
`RETRIEVE PURCHASE
`
`HISTORIES FOR ALL
`CUSTOMERS
`CUSTOMER|PURCHASED ITEMS
`
`
`
`
`
`USER_A|ITEM_A ITEM_C ==>
`USER_B|ITEM_C ITEM_D -:--
`
`
`GENERATE TEMPORARY
`
`
`TABLE MAPPING CUSTOMERS
`TO PURCHASED ITEMS
`
`7024
`
`
`GENERATE TEMPORARY.
`CUSTOMERS WHO
`
`TABLE MAPPING PURCHASED
`PURCHASED ITEM
`ITEMS TO CUSTOMERS
`ITEM_A|USER_B, USER_D--:
`USER_A, USER_F::
`
`
`
`
`
`
`
`
`
`
` IDENTIFY
`
`POPULAR
`ITEMS
`
`
` FOR EACH
`(POPULAR_ITEM,
`
`
`
`
`OTHER_ITEM) PAIR,
`
`
`se
`POPULAR_ ITEM
`irem_a|i EM_
`CUSTOMERS IN COMMON
`:
`.
`\ el =
`COUNT NUMBER OF
`
`
`
`POPULAR_A |2|70|
`
`
`POPULAR_B
`
` COMPUTE
`
`COMMONALITY
`INDEXES
`
`
` SORT
`OTHER_ITEMS
`
`
`
`108
`
`412
`
`
`
`
`7/4
`
`FILTER
`
`176
`
`
`TRUNCATE
`OTHER_ITEMS
`
`
`
`LISTS AND
`STORE IN TABLE
`
`
`
`FIC. F
`
`

`

`U.S. Patent
`
`Nov.13, 2001
`
`Sheet 4 of 7
`
`US 6,317,722 B1
`
`
`
`FIG.4
`
`

`

`U.S. Patent
`
`Nov. 13, 2001
`
`Sheet 5 of 7
`
`US 6,317,722 BI
`
`GENERATE INSTANT RECOMMENDATIONS
`
`IDENTIFY ALL POPULAR ITEMS
`PURCHASED OR RATED BY USER
`
`WITHIN LAST SIX MONTHS
`
`180
`
`182
`
`RETRIEVE SIMILAR
`ITEMS LISTS FROM TABLE
`
`RATING OF CORRESPONDING POPULAR ITEM
`
`WEIGHT EACH SIMILAR ITEMS LIST
`BASED ON USER'S PURCHASE DATE OR
`
`184
`
`186
`
`MERGE SIMILAR ITEMS LISTS
`(IF MULTIPLE LISTS) WHILE
`
`SUMMING SCORES
`
`188
`
`SORT RESULTING LIST FROM
`HIGHEST-TO—LOWEST SCORE
`
`
`
`
`
`
`
`FILTER RESULTING LIST BY DELETING ITEMS
`WHICH HAVE BEEN PURCHASED, HAVE BEEN RATED,
`HAVE A NEGATIVE SCORE, OR FALL OUTSIDE
`DESIGNATED PRODUCT GROUP OR CATEGORY
`
`190
`
`
`
`OPTIONALLY SELECT ITEM FROM USER’S RECENT
`SHOPPING CART CONTENTS AND INSERT INTO
`ONE OF THE TOP M POSITIONS IN LIST
`
`
`
`
`192
`
`FIG. I
`
`RECOMMEND TOP M ITEMS FROM LIST
`
`194
`
`

`

`U.S. Patent
`
`Nov.13, 2001
`
`Sheet 6 of 7
`
`US 6,317,722 B1
`
`File
`
`Edit
`
`View
`
`Go
`
`Favorite
`
`Help
`
`ao GAB
`
`Favorite
`
`Print
`
`
`Font
`Mail
`
`Amazon.com Home| Shopping Cart | Your Account | Recommendation Center
`
`e The Other Side of Midnight; Sidney Sheldon
`e Inside Intel; Tim Jackson
`e The Road Ahead; Bill Gates, et al
`e The Doomsday Conspiracy; Sidney Sheldon
`e Skin
`Legs and All; Tom Robbins
`
`=a => ©
`
`
`Bock Forw... Stop Refresh Home
`
`fa}
`
`Search
`
`
`
`Address|http: //www.amozon.com/instant—recs/recs iv]
`
`amazon.com
`
`7 I
`
`nstant Recommendations
`
`We think you'll like these items in|All Categories |'V| [cor]
`
`Hello, John Gerry.
`
`
`202
`
`
`
`200
`‘More Recommendations|
`
`Already own any of these titles? Know you don't like one? Refine your
`recommendations and we'll
`immediately show you new choices!
`
`New! We have music recommendations for you!
`
`FIC.6
`
`

`

`U.S. Patent
`
`Nov.13, 2001
`
`Sheet 7 of 7
`
`US 6,317,722 B1
`
`GENERATE SHOPPING CART
`BASED RECOMMENDATIONS
`
`LEZ
`
`FOR EACH SHOPPING CART
`ITEM THAT IS A POPULAR ITEM,
`RETRIEVE SIMILAR ITEMS
`
`LIST FROM TABLE
`
`MERGE SIMILAR ITEMS LISTS
`WHILE SUMMING Cl VALVES
`
`Z2Eo
`
`LEE
`
`SORT RESULTING LIST FROM
`HIGHEST TO LOWEST SCORE
`
`290
`
`FILTER RESULTING LIST BY
`DELETING ITEMS THAT ARE
`CURRENTLY IN THE SHOPPING
`CART AND ITEMS THAT HAVE
`
`BEEN PURCHASED OR RATED
`
`RECOMMEND TOP M ITEMS FROM LIST
`
`294
`
`FIG. /
`
`

`

`US 6,317,722 B1
`
`1
`USE OF ELECTRONIC SHOPPING CARTS
`TO GENERATE PERSONAL
`RECOMMENDATIONS
`FIELD OF THE INVENTION
`
`The present invention relates to information filtering and
`recommendation systems. More specifically, the invention
`relates to methods for recommending products or other
`itemsto individual users of an electronic commerce system.
`BACKGROUND OF THE INVENTION
`
`A recommendation service is a computer-implemented
`service that recommends items from a database ofitems.
`The recommendations are customized to particular users
`based on information known about the users. One common
`application for recommendation services involves recom-
`mending products to online customers. For example, online
`merchants commonly provide services for recommending
`products (books, compact discs, videos, etc.) to customers
`based on profiles that have been developed for such cus-
`tomers. Recommendation services are also common for
`
`recommending Websites, articles, and other types of infor-
`mational content to users.
`
`One technique commonly used by recommendation ser-
`vices is known as content-based filtering. Pure content-
`based systems operate by attempting to identify items
`which, based on an analysis of item content, are similar to
`items that are known to be of interest
`to the user. For
`example, a content-based Website recommendation service
`may operate by parsing the user’s favorite Web pages to
`generate a profile of commonly-occurring terms, and then
`use this profile to search for other Web pages that include
`some or all of these terms.
`
`2
`Another problem with collaborativefiltering techniquesis
`that an item in the database normally cannot be recom-
`mended until
`the item has been rated. As a result,
`the
`operator of a new collaborative recommendation system is
`commonly faced with a “cold start” problem in which the
`service cannot be brought online in a useful form until a
`threshold quantity of ratings data has been collected. In
`addition, even after the service has been brought online, it
`may take months or years before a significant quantity of the
`database items can be recommended.
`
`Another problem with collaborative filtering methods is
`that the task of comparing user profiles tends to be time
`consuming—particularly if the number of users is large
`(e.g., tens or hundreds of thousands). As a result, a tradeoff
`tends to exist between response time and breadth ofanalysis.
`For example,
`in a recommendation system that generates
`real-time recommendations in response to requests from
`users, it may not be feasible to compare the user’s ratings
`profile to those of all other users. A relatively shallow
`analysis of the available data (leading to poor
`recommendations) may therefore be performed.
`Another problem with both collaborative and content-
`based systemsis that they generally do not reflect the current
`preferences of the community of users. In the context of a
`system that
`recommends products to customers,
`for
`example, there is typically no mechanism for favoring items
`that are currently “hot sellers.” In addition, existing systems
`do not provide a mechanism for recognizing that the user
`may be searching for a particular type or category of item.
`
`15
`
`20
`
`25
`
`30
`
`SUMMARY OF THE DISCLOSURE
`
`limita-
`Content-based systems have several significant
`tions, For example, content-based methods generally do not
`provide any mechanism for evaluating the quality or popu-
`larity of an item. In addition, content-based methods gen-
`erally require that the items include some form of content
`that is amenable to feature extraction algorithms; as a result,
`content-based systems tend to be poorly suited for recom-
`mending movies, musictitles, authors, restaurants, and other
`types of items that havelittle or no useful, parsable content.
`Another common recommendation technique is known as
`collaborative filtering. In a pure collaborative system, items
`are recommended to users based on the interests of a
`community of users, without any analysis of item content.
`Collaborative systems commonly operate by having the
`users rate individual items from a list of popular items.
`Through this process, each user builds a personal profile of
`ratings data. To generate recommendations for a particular
`user, the user’s profile is initially comparedto the profiles of
`other users to identify one or more “similar users.” Items
`that were rated highly by these similar users (but which have
`not yet been rated by the user) are then recommendedto the
`user. An important benefit of collaborative filtering is that it
`overcomes the above-noted deficiencies of content-based
`filtering.
`As with content-based filtering methods, however, exist-
`ing collaborative filtering techniques have several problems.
`One problem is that the user is commonly faced with the
`onerous task of having to rate items in the database to build
`up a personal ratings profile. This task can be frustrating,
`particularly if the user is not familiar with manyofthe items
`that are presented for rating purposes. Further, because
`collaborative filtering relies on the existence of other, similar
`users, collaborative systems tend to be poorly suited for
`providing recommendations to users that have unusual
`tastes.
`
`60
`
`65
`
`40
`
`$0
`
`55
`
`The present invention addresses these and other problems
`by providing a computer-implemented service and associ-
`ated methods for generating personalized recommendations
`of items based on the collective interests of a community of
`users. An important benefit of the service is that the recom-
`mendations are generated without the need for the user, or
`any other users, to rate items. Another important benefit is
`that
`the recommended items are identified using a
`previously-generated table or other mapping structure which
`maps individual items tolists of “similar” items. The item
`similarities reflected by the table are based at least upon
`correlations between the interests of users in particular
`items.
`
`The types of items that can be recommended by the
`service include, without
`limitation, books, compact discs
`(“CDs”), videos, authors, artists, item categories, Websites,
`and chat groups. The service may be implemented, for
`example, as part of a Web site, online services network,
`e-mail notification service, documentfiltering system, or
`other type of computer system that explicitly or implicitly
`recommends items to users. In a preferred embodiment
`described herein, the service is used to recommend works
`such as book titles and music titles to users of an online
`merchant's Web site.
`
`the
`In accordance with one aspect of the invention,
`mappings of
`items to similar
`items (“item-to-item
`mappings’) are generated periodically, such as once per
`week, by an off-line process which identifies correlations
`between known interests of users in particular items. For
`example, in the embodiment described in detail below, the
`mappings are generating by periodically analyzing user
`purchase histories to identify correlations between pur-
`chases of items. The similarity between two items is pref-
`erably measured by determining the number ofusers that
`have an interest in both items relative to the numberof users
`
`

`

`US 6,317,722 B1
`
`3
`that have an interestin either item (e.g., items A and Bare
`highly similar because a relatively large portion ofthe users
`that bought one of the items also bought the other item). The
`item-to-item mappings could also incorporate other types of
`similarities, including content-based similarities extracted
`by analyzing item descriptions or content.
`To generate a set of recommendationsfor a given user, the
`service retrieves from the table the similar items lists cor-
`responding to items already known to be of interest to the
`user, and then appropriately combinesthese lists to generate
`a list of recommended items. For example, if there are three
`items that are known to beof interest to the user (such as
`three items the user recently purchased), the service may
`retrieve the similar itemslists for these three items from the
`table and combine these lists. Because the item-to-item
`mappings are regenerated periodically based on up-to-date
`sales data, the recommendations tend to reflect the current
`buying trends of the community.
`In accordance with another aspect of the invention, the
`similar items lists read from the table may be appropriately
`weighted (prior to being combined) based on indicia of the
`user’s affinity for, or current interest in, the corresponding
`items of known interest. For example, the similar itemslist
`for a book that was purchased in the last week may be
`weighted more heavily than the similar itemslist for a book
`that was purchased four months ago. Weighting a similar
`itemslist heavily has the effect ofincreasing the likelihood
`that the items in that list will be included in the recommen-
`dations that are ultimately presented to the user.
`An important aspect of the service is that the relatively
`computation-intensive task of correlating item interests is
`performedoff-line, and the results of this task (item-to-item
`mappings) stored in a mapping structure for subsequent
`look-up. This enables the personal recommendations to be
`generated rapidly and efficiently (such as in real-time in
`response to a
`request by the user), without sacrificing
`breadth of analysis.
`Another feature of the invention involves using the cur-
`rent and/or recent contents of the user’s shopping cart as
`inputs to the recommendation service (or to another type of
`recommendation service which generates recommendations
`given a unary listing of items). For example, if the user
`currently has three items in his or her shopping cart, these
`three items can be treated as the items of knowninterest for
`purposes of generating recommendations, in which case the
`recommendations may be generated and displayed automati-
`cally when the user views the shopping cart contents. Using
`the current and/or recent shopping cart contents as inputs
`tends to produce recommendationsthat are highly correlated
`to the current short-term interests of the user—evenifthese
`short term interestdiffer significantly from the user’s general
`preferences. For example, if the user is currently searching
`for books on a particular topic and has added several such
`books to the shopping cart, this method will more likely
`produce other books that involve the sameor similar topics.
`One aspect of the invention is
`thus a computer-
`implemented method of recommending items to a user. The
`method comprises identifying a plurality of items that are
`currently in the user’s shopping cart; and using the plurality
`of items in the user’s shopping cart to generate a list of
`additional items that are predicted to be ofinterest to the
`user, wherein an additional item is selected for inclusion in
`the list based in-part upon whether that additional item is
`similar to more than oneof the plurality of items in the user’s
`shoppingcart. Thelist of additional itemsis displayed to the
`user when the user views contents of the shopping cart.
`
`5
`
`15
`
`25
`
`30
`
`40
`
`$0
`
`55
`
`60
`
`65
`
`4
`Another aspect of the invention is a method of recom-
`mending products to a user. The method comprises gener-
`ating a data structure which maps individual productsto sets
`of related products in which product relatedness is deter-
`mined based at least in-part on an automated analysis of user
`purchase histories of products. The method further com-
`prises identifying a plurality of products that are currently in
`a shopping cart of a user. For each of the plurality of
`products, the data structure is accessedto identify a corre-
`sponding set of related products,
`to thereby identify a
`plurality ofsets of related products. The related products are
`selected from the sets to recommendto the userbased in part
`on whether a related product falls within more than one of
`the sets, such that productsthat are related to more than one
`of the products in the user’s shopping cart
`tend to be
`recommended to the user over products related to only a
`single product in the shopping cart.
`Another feature of the invention involves allowing the
`userto create multiple shopping carts under a single account
`(such as shopping carts for different family members), and
`generating recommendationsthat are specific to a particular
`shopping cart. For example, the user can be prompted to
`select a particular shopping cart (or set of shopping carts),
`and the recommendations can then be generated based on
`the items that were purchased from or otherwise placed into
`the designated shopping cart(s). This feature of the invention
`allows users to obtain recommendations that correspond to
`the role or purpose (e¢.g., work versus pleasure) of a par-
`ticular shopping cart.
`‘Twospecific implementationsof the service are disclosed,
`both of which generate personal recommendations using the
`same type of table. In the first implementation, the recom-
`mendations are based on the items that have recently been
`rated or purchased by the user.
`In the second
`implementation,
`the recommendations are based on the
`current shopping cart contents of the user.
`BRIEF DESCRIPTION OF THE DRAWINGS
`These and other features of the invention will now be
`described with reference to the drawings summarizedbelow.
`These drawings and the associated description are provided
`to illustrate a preferred embodiment ofthe invention, and not
`to limit the scope of the invention.
`FIG. 1 illustrates a Web site which implements a recom-
`mendation service which operates in accordance with the
`invention, andillustrates the flow of information between
`components.
`FIG. 2 illustrates a sequence of steps that are performed
`by the recommendation process of FIG.
`1
`to generate
`personalized recommendations.
`FIG, 3 illustrates a sequence of steps that are performed
`by the table generation process of FIG. 1 to generate a
`similar itemstable, andillustrates temporary data structures
`generated during the process.
`FIG. 4 is a Venn diagram illustrating a hypothetical
`purchase history profile of three items.
`FIG. 5 illustrates one specific implementation of the
`sequence of steps of FIG. 2.
`FIG. 6 illustrates the general form of a Web pagesused to
`present the recommendations of the FIG. 5 process to the
`user.
`
`FIG, 7 illustrates another specific implementation of the
`sequence of steps of FIG. 2.
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`The various features and methods of the invention will
`now be described in the context of a recommendation
`
`

`

`US 6,317,722 B1
`
`5
`service, including twospecific implementations thereof, that
`is used to recommend book titles, music titles, videotitles,
`and other types of items to individual users of
`the
`Amazon.com Website. As will be recognized to those
`skilled in the art, the disclosed methods can also be used to
`recommend other types of items, including non-physical
`items. By way of example and not limitation, the disclosed
`methods can also be used to recommend authors, artists,
`categories or groups of titles, Web sites, chat groups,
`movies,
`television shows, downloadable content,
`restaurants, and other users.
`Throughout the description, reference will be made to
`various implementation-specific details of the recommenda-
`tion service, the Amazon.com Web site, and other recom-
`mendation services of the Web site. These details are pro-
`vided in order to fully illustrate preferred embodiments of
`the invention, and not tolimit the scope of the invention. The
`scope of the invention is set forth in the appended claims.
`I. Overview of Web Site and Recommendation Services
`The Amazon.com Web site includes functionality for
`allowing users to search, browse, and make purchases from
`an online catalog ofseveral million booktitles, music titles,
`video titles, and other types of items. Using a shopping cart
`feature of the site, users can add and remove items to/from
`a personal shopping cart which is persistent over multiple
`sessions.
`(As used herein, a “shopping cart” is a data
`structure and associated code which keeps track of items that
`have been selected by a user for possible purchase.) For
`example, a user can modify the contents ofthe shopping cart
`over a period of time, such as one week, and then proceed
`to a check out area ofthe site to purchase the shopping cart
`contents.
`
`The user can also create multiple shopping carts within a
`single account. For example, a user can set up separate
`shopping carts for work and home, or can set up separate
`shopping carts for each member of the user’s family. A
`preferred shopping cart scheme for allowing users to set up
`and use multiple shopping carts is disclosed in U.S. appli-
`cation Ser. No. 09/104,942,
`filed Jun. 25, 1998,
`titled
`METHOD AND SYSTEM FOR ELECTRONIC COM-
`MERCE USING MULTIPLE ROLES, the disclosure of
`which is hereby incorporated by reference.
`The site also implements a variety of different recom-
`mendation services for recommending book titles, music
`titles, and/or video titles to users. One such service, known
`as BookMatcher™, allows users to interactively rate indi-
`vidual books on a seale of 1—5 to create personal item ratings
`profiles, and applies collaborative filtering techniques to
`these profiles to generate personal recommendations. The
`BookMatcherservice is described in detail in U.S. applica-
`tion Ser. No. 09/040,171 filed Mar. 17, 1998, the disclosure
`of which is hereby incorporated by reference. The site may
`also include associated servicesthat allow users to rate other
`types of items, such as CDsandvideos. As described below,
`the ratings data collected by the BookMatcher service and
`similar services is optionally incorporated into the recom-
`mendation processes of the present invention.
`Another type of service is a recommendation service
`which operates in accordance with the invention. The ser-
`vice (“Recommendation Service”) is preferably used to
`recommend booktitles, music titles and/or videos titles to
`users, but could also be used in the context of the same Web
`site to recommendother types of items, including authors,
`artists, and groups or categories oftitles. Briefly, given a
`unary listing of items that are “known”to be of interest to
`a user (e.g., a list of items purchased, rated, and/or viewed
`by the user), the Recommendation Service generatesa list of
`additional items (“recommendations”) that are predicted to
`
`15
`
`25
`
`30
`
`40
`
`$0
`
`55
`
`60
`
`65
`
`6
`be of interest to the user. (As used herein, the term “interest”
`refers generally to a user’s liking ofor affinity for an item;
`the term “known”is used to distinguish items for which the
`user has implicitly or explicitly indicated some level of
`interest from items predicted by the Recommendation Ser-
`vice to be of interest.)
`The recommendations are generated using a table which
`maps itemsto lists of “similar” items (“similar itemslists”),
`without the need for users to rate any items (although ratings
`data may optionally be used). For example, if there are three
`items that are known to be ofinterest to a particular user
`(such asthree items the user recently purchased),the service
`may retrieve the similar itemslists for these three items from
`the table, and appropriately combinethese lists (as described
`below) to generate the recommendations.
`the
`In accordance with one aspect of the invention,
`mappings of items to similar
`items (“item-to-item
`mappings”) are generated periodically, such as once per
`week, from data whichreflects the collective interests of the
`community of users. More specifically,
`the item-to-item
`mappings are generated by an off-line process which iden-
`tifies correlations between known interests of users in par-
`ticular items. For example, in the embodiment described in
`detail below, the mappings are generating by analyzing user
`purchase histories to identify correlations between pur-
`chases of particular items (e.g., items A and B are similar
`because a relatively large portion ofthe users that purchased
`item A also bought
`item B). The item-to-item mappings
`could also reflect other types of similarities,
`including
`content-based similarities extracted by analyzing item
`descriptions or content.
`An important aspect of the Recommendation Service is
`that the relatively computation-intensive task ofcorrelating
`item interests is performed off-line, and the results of this
`task (item-to-item mappings) are stored in a mapping struc-
`ture for subsequent
`look-up. This enables the personal
`recommendations to be generated rapidly and efficiently
`(such as in real-time in response to a request by the user),
`without sacrificing breadth of analysis.
`In accordance with another aspect of the invention, the
`similar items lists read from the table are appropriately
`weighted (prior to being combined) based on indicia of the
`user’s affinity for or current
`interest in the corresponding
`items of known interest. For example, in one embodiment
`described below, if the item of known interest was previ-
`ously rated by the user (such as through use of the Book-
`Matcher service),
`the rating is used to weight the corre-
`sponding similar items list. Similarly, the similar itemslist
`for a book that was purchased in the last week may be
`weighted more heavily than the similar itemslist for a book
`that was purchased four months ago.
`Another feature of the invention involves using the cur-
`rent and/or recent contents of the user’s shopping cart as
`inputs to the Recommendation Service. For example, if the
`user currently has three items in his or her shopping cart,
`these three items can be treated as the items of known
`interest
`for purposes of generating recommendations,
`in
`which case the recommendations may be generated and
`displayed automatically when the user views the shopping
`cart contents. If the user has multiple shopping carts, the
`recommendations are preferably generated based on the
`contents of the shopping cart implicitly or explicitly desig-
`nated by the user, such as the shopping cart currently being
`viewed. This method of generating recommendations can
`also be used within other types of recommendation systems,
`including content-based systems and systemsthat donot use
`item-to-item mappings.
`
`

`

`US 6,317,722 B1
`
`15
`
`20
`
`25
`
`30
`
`40
`
`7
`Using the current and/or recent shopping cart contents as
`inputs tends to produce recommendations that are highly
`correlated to the current short-term interests of the user—
`even if these short term interests are not reflected by the
`user’s purchase history. For example, if the user is currently
`searching for a father’s day gift and has selected several
`books for prospective purchase, this method will have a
`tendency to identify othe