Skip to yearly menu bar Skip to main content


A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes

Jennifer Gillenwater · Alex Kulesza · Zelda Mariet · Sergei Vassilvitskii

Pacific Ballroom #230

Keywords: [ Structured Prediction ] [ Recommender Systems ] [ Approximate Inference ]


It is often desirable in recommender systems and other information retrieval applications to provide diverse results, and determinantal point processes (DPPs) have become a popular way to capture the trade-off between the quality of individual results and the diversity of the overall set. However, sampling from a DPP is inherently expensive: if the underlying collection contains N items, then generating each DPP sample requires time linear in N following a one-time preprocessing phase. Additionally, results often need to be personalized to a user, but standard approaches to personalization invalidate the preprocessing, making personalized samples especially expensive. In this work we address both of these shortcomings. First, we propose a new algorithm for generating DPP samples in time logarithmic in N, following a slightly more expensive preprocessing phase. We then extend the algorithm to support arbitrary query-time feature weights, allowing us to generate samples customized to individual users while still retaining logarithmic runtime; experiments show our approach runs over 300 times faster than traditional DPP sampling on collections of 100,000 items for samples of size 10.

Live content is unavailable. Log in and register to view live content