Math @ Duke

Publications [#235620] of Pankaj K. Agarwal
Papers Published
 Wu, Y; Agarwal, PK; Li, C; Yang, J; Yu, C, On "one of the few" objects,
Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
(2012),
pp. 14871495 [doi]
(last updated on 2018/03/17)
Abstract: Objects with multiple numeric attributes can be compared within any "subspace" (subset of attributes). In applications such as computational journalism, users are interested in claims of the form: Karl Malone is one of the only two players in NBA history with at least 25,000 points, 12,000 rebounds, and 5,000 assists in one's career. One challenge in identifying such "oneofthek" claims (k = 2 above) is ensuring their "interestingness". A small k is not a good indicator for interestingness, as one can often make such claims for many objects by increasing the dimensionality of the subspace considered. We propose a uniquenessbased interestingness measure for oneofthefew claims that is intuitive for nontechnical users, and we design algorithms for finding all interesting claims (across all subspaces) from a dataset. Sometimes, users are interested primarily in the objects appearing in these claims. Building on our notion of interesting claims, we propose a scheme for ranking objects and an algorithm for computing the topranked objects. Using realworld datasets, we evaluate the efficiency of our algorithms as well as the advantage of our objectranking scheme over popular methods such as Kemeny optimal rank aggregation and weightedsum ranking. © 2012 ACM.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

