A computer-implemented service recommends digital works (and/or creators of works) to a user based on works currently or previously played or downloaded by the user on a player device or based on playlists stored on the player device. The works may be, for example, music files, video files, electronic books, or other digital content for playing by users. A user may thus obtain personalized recommendations that are based on works obtained from sources (web sites, physical CDs, etc.) that are independent of the recommendations system. In one embodiment, the service identifies pairs of works (and/or work creators) that are similar to each other by virtue of the relatively high frequency with which they co-occur on playlists or within play histories of users. The resulting mappings are used to provide recommendations to users.