Skip to main content

Finding diverse, high-value representatives on a surface of answers

Publication ,  Conference
Wu, Y; Gao, J; Agarwal, PK; Yang, J
Published in: Proceedings of the VLDB Endowment
January 1, 2017

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.

Duke Scholars

Published In

Proceedings of the VLDB Endowment

DOI

EISSN

2150-8097

Publication Date

January 1, 2017

Volume

10

Issue

7

Start / End Page

793 / 804

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Wu, Y., Gao, J., Agarwal, P. K., & Yang, J. (2017). Finding diverse, high-value representatives on a surface of answers. In Proceedings of the VLDB Endowment (Vol. 10, pp. 793–804). https://doi.org/10.14778/3067421.3067428
Wu, Y., J. Gao, P. K. Agarwal, and J. Yang. “Finding diverse, high-value representatives on a surface of answers.” In Proceedings of the VLDB Endowment, 10:793–804, 2017. https://doi.org/10.14778/3067421.3067428.
Wu Y, Gao J, Agarwal PK, Yang J. Finding diverse, high-value representatives on a surface of answers. In: Proceedings of the VLDB Endowment. 2017. p. 793–804.
Wu, Y., et al. “Finding diverse, high-value representatives on a surface of answers.” Proceedings of the VLDB Endowment, vol. 10, no. 7, 2017, pp. 793–804. Scopus, doi:10.14778/3067421.3067428.
Wu Y, Gao J, Agarwal PK, Yang J. Finding diverse, high-value representatives on a surface of answers. Proceedings of the VLDB Endowment. 2017. p. 793–804.

Published In

Proceedings of the VLDB Endowment

DOI

EISSN

2150-8097

Publication Date

January 1, 2017

Volume

10

Issue

7

Start / End Page

793 / 804

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics