In this paper, we introduce privacy-preserving query personalization for experience items like movies, music, games or books. While these items are rather common, describing them with semantically meaningful attribute values is challenging, thus hindering traditional database query personalization. This often leads to the use of recommender systems, which, however, have several draw-backs as for example high barriers for new users joining the system, the inability to process dynamic queries, and severe privacy concerns due to requiring extensive long-term user profiles. We propose an alternative approach, representing experience items in a perceptual space using high-dimensional and semantically rich features. In order to query this space, we provide query-by-example personalization relying on the perceived similarity between items, and learn a user’s current preferences with respect to the query on the fly. Further-more, for query execution, our approach addresses privacy issues of recommender systems as we do not require user profiles for queries, do not leak any personal information during interaction, and allow users to stay anonymous while querying. In this paper, we provide the foundations of such a system and then extensively discuss and evaluate the performance of our approach under different assumptions. Also, suitable optimizations and modifications to ensure scalability on current hardware are presented.