Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#330829] of Pankaj K. Agarwal

Papers Published

  1. Wu, Y; Gao, J; Agarwal, PK; Yang, J, Finding diverse, high-value representatives on a surface of answers, Proceedings of the Vldb Endowment, vol. 10 no. 7 (March, 2017), pp. 793-804, VLDB Endowment [doi]
    (last updated on 2019/01/22)

    © 2017 VLDB Endowment. In many applications, the system needs to selectively present a small subset of answers to users. The set of all possible answers can be seen as an elevation surface over a domain, where the elevation measures the quality of each answer, and the dimensions of the domain correspond to attributes of the answers with which similarity between answers can be measured. This paper considers the problem of finding a diverse set of k high-quality representatives for such a surface. We show that existing methods for diversified top-k and weighted clustering problems are inadequate for this problem. We propose k-DHR as a better formulation for the problem. We show that k-DHR has a submodular and monotone objective function, and we develop efficient algorithms for solving k-DHR with provable guarantees. We conduct extensive experiments to demonstrate the usefulness of the results produced by k-DHR for applications in computational lead-finding and fact-checking, as well as the efficiency and effectiveness of our algorithms.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320