Disclosed are various embodiments for a similarity service. Multiple samplings of user accounts are randomly selected from a pool of user accounts. Interaction history data for each of the user accounts is used to determine item similarities corresponding to each of the user account samplings. The item similarity data is aggregated to determine similar items.