Math @ Duke

Publications [#328996] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Kumar, N; Sintos, S; Suri, S, Efficient algorithms for kregret minimizing sets,
Leibniz International Proceedings in Informatics, Lipics, vol. 75
(August, 2017), ISBN 9783959770361 [doi]
(last updated on 2018/11/14)
Abstract: © Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos, and Subhash Suri. A regret minimizing set Q is a small size representation of a much larger database P so that user queries executed on Q return answers whose scores are not much worse than those on the full dataset. In particular, a kregret minimizing set has the property that the regret ratio between the score of the top1 item in Q and the score of the topk item in P is minimized, where the score of an item is the inner product of the item's attributes with a user's weight (preference) vector. The problem is challenging because we want to find a single representative set Q whose regret ratio is small with respect to all possible user weight vectors. We show that kregret minimization is NPComplete for all dimensions d ≥ 3, settling an open problem from Chester et al. [VLDB 2014]. Our main algorithmic contributions are two approximation algorithms, both with provable guarantees, one based on coresets and another based on hitting sets. We perform extensive experimental evaluation of our algorithms, using both realworld and synthetic data, and compare their performance against the solution proposed in [VLDB 14] . The results show that our algorithms are significantly faster and scalable to much larger sets than the greedy algorithm of Chester et al. for comparable quality answers.


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

