License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.7
URN: urn:nbn:de:0030-drops-76321
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7632/
Go to the corresponding LIPIcs Volume Portal

Agarwal, Pankaj K. ; Kumar, Nirman ; Sintos, Stavros ; Suri, Subhash

Efficient Algorithms for k-Regret Minimizing Sets

pdf-format:
LIPIcs-SEA-2017-7.pdf (4 MB)

Abstract

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 k-regret minimizing set has the property that the regret ratio between the score of the top-1 item in Q and the score of the top-k 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 k-regret minimization is NP-Complete 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 real-world 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.

BibTeX - Entry

@InProceedings{agarwal_et_al:LIPIcs:2017:7632,
  author =	{Pankaj K. Agarwal and Nirman Kumar and Stavros Sintos and Subhash Suri},
  title =	{{Efficient Algorithms for k-Regret Minimizing Sets}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7632},
  URN =		{urn:nbn:de:0030-drops-76321},
  doi =		{10.4230/LIPIcs.SEA.2017.7},
  annote =	{Keywords: regret minimizing sets, skyline, top-k query, coreset, hitting set}
}

Keywords: regret minimizing sets, skyline, top-k query, coreset, hitting set
Collection: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 07.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI