Differential privacy preserving recommendation

#Recommendation systems based on collaborative filtering are a popular and useful way to recommend items and things (e.g., movies, music, products, restaurants, services, websites, etc.) to users. Typically, a user is recommended one or more items based on the items that the user has used and/or rated in view of the items that have been used and/or rated by other users. For example, a user may have provided ratings for a set of movies that the user has viewed. The user may then be recommended other movies to view based on the movies rated by other users who have provided at least some similar ratings of the movies rated by the user. Other examples of collaborative filtering systems may be systems that recommend websites to a user based on the websites that the user has visited, systems that recommend items for purchasing by a user based on items that the user has purchased, and systems that recommend restaurants to a user based on ratings of restaurants that the user has submitted.

#While collaborative filtering is useful for making recommendations, there are also privacy concerns associated with collaborative filtering. For example, a user of an online store may not object to the use of their ordering history or ratings to make anonymous recommendations to other users and to themselves, but the user may not want other users to know the particular items that the user purchased or rated.

#Previous solutions to this problem have focused on protecting the data that includes the user ratings. For example, user purchase histories may be kept in a secure encrypted database to keep malicious users from obtaining the user purchase histories. However, these systems may be ineffective at protecting the differential privacy of its users. A system is said to provide differential privacy if the presence or absence of a particular record or value cannot be determined based on an output of the system. For example, in the case of a website that allows users to rate movies, a curious user may attempt to make inferences about the movies a particular user has rated by creating multiple accounts, repeatedly changing the movie ratings submitted, and observing the changes to the movies that are recommended by the system. Such a system may not provide differential privacy because the presence or absence of a rating by a user (i.e., a record) may be inferred from the movies that are recommended (i.e., output).

#The foregoing summary, as well as the following detailed description of illustrative embodiments, is better understood when read in conjunction with the appended drawings. For the purpose of illustrating the embodiments, there are shown in the drawings example constructions of the embodiments; however, the embodiments are not limited to the specific methods and instrumentalities disclosed. In the drawings:

#FIG. 1 is a block diagram of an implementation of a system that may be used to provide differential privacy for user rating data;

#FIG. 2 is an operational flow of an implementation of a method for generating correlation data from user rating data while providing differential privacy;

#FIG. 1 is a block diagram of an implementation of a system 100 that may be used to provide differential privacy for user rating data 102. The user rating data 102 may include data describing a plurality of items and a plurality of user generated ratings of those items. The items may include objects, purchased items, websites, restaurants, books, services, places, etc. There is no limit to the types of items that may be included and that may be rated by the users. In some implementations, the ratings may be scores that are generated by the user and assigned to the particular items that are being rated. The ratings may be made in a variety of scales and formats. For example, in an implementation where users rate movies, the ratings may be a score between two numbers, such as 0 and 5. Other types of rating systems and rating scales may also be used.

#In some implementations, the user rating data 102 may be stored in a user rating data storage 105 of the system 100. As illustrated, the user rating data storage 105 may be accessible to the various components of the system 100 through a network 110. The network 110 may be a variety of network types including the public switched telephone network (PSTN), a cellular telephone network, and a packet switched network (e.g., the Internet). The user rating data storage 105 protects the stored user rating data 102 from being viewed or accessed by unauthorized users. For example, the user rating data 102 may be stored in the user rating data storage 105 in an encrypted form. Other methods for protecting the user rating data 102 may also be used.

#The system 100 may further include a correlation engine 115 that processes the user rating data 102 from the user rating data storage 105 to generate correlation data 109. This generated correlation data 109 may be used by a recommendation engine 120 to generate and provide item recommendations 135 to users based on the user's own ratings and/or item consumption history. The item recommendations 135 may be presented to a user at a client 130. The correlation engine 115, recommendation engine 120, and the client 130 may be implemented using one or more computing devices such as the computing device 600 illustrated in FIG. 6.