{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T19:52:12Z","timestamp":1780084332224,"version":"3.54.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>\n            Regret minimizing sets are a recent approach to representing a dataset\n            <jats:italic>D<\/jats:italic>\n            by a small subset\n            <jats:italic>R<\/jats:italic>\n            of size\n            <jats:italic>r<\/jats:italic>\n            of representative data points. The set\n            <jats:italic>R<\/jats:italic>\n            is chosen such that executing any top-1 query on\n            <jats:italic>R<\/jats:italic>\n            rather than\n            <jats:italic>D<\/jats:italic>\n            is minimally perceptible to any user. However, such a subset\n            <jats:italic>R<\/jats:italic>\n            may not exist, even for modest sizes,\n            <jats:italic>r.<\/jats:italic>\n            In this paper, we introduce the relaxation to\n            <jats:italic>k<\/jats:italic>\n            -regret minimizing sets, whereby a top-1 query on\n            <jats:italic>R<\/jats:italic>\n            returns a result imperceptibly close to the top-\n            <jats:italic>k<\/jats:italic>\n            on\n            <jats:italic>D.<\/jats:italic>\n          <\/jats:p>\n          <jats:p>\n            We show that, in general, with or without the relaxation, this problem is NP-hard. For the specific case of two dimensions, we give an efficient dynamic programming, plane sweep algorithm based on geometric duality to find an optimal solution. For arbitrary dimension, we give an empirically effective, greedy, randomized algorithm based on linear programming. With these algorithms, we can find subsets\n            <jats:italic>R<\/jats:italic>\n            of much smaller size that better summarize\n            <jats:italic>D<\/jats:italic>\n            , using small values of\n            <jats:italic>k<\/jats:italic>\n            larger than 1.\n          <\/jats:p>","DOI":"10.14778\/2732269.2732275","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"389-400","source":"Crossref","is-referenced-by-count":50,"title":["Computing k-regret minimizing sets"],"prefix":"10.14778","volume":"7","author":[{"given":"Sean","family":"Chester","sequence":"first","affiliation":[{"name":"University of Victoria, Victoria, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Thomo","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Venkatesh","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sue","family":"Whitesides","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/262839.262856"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142530"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_30"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335433"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37487-6_17"},{"key":"e_1_2_1_7_1","first-page":"183","volume-title":"PVLDB","author":"Das G.","year":"2007","unstructured":"G. Das , D. Gunopulos , N. Koudas , and N. Sarkas . Ad-hoc top-k query answering for data streams . In PVLDB , pages 183 -- 194 , 2007 . G. Das, D. Gunopulos, N. Koudas, and N. Sarkas. Ad-hoc top-k query answering for data streams. In PVLDB, pages 183--194, 2007."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767873"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12171"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.73"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.04.004"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367854"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.47"},{"key":"e_1_2_1_16_1","volume-title":"Proc. DBRank","author":"Magnani M.","year":"2012","unstructured":"M. Magnani , I. Assent , and M. L. Mortensen . Anytime skyline query processing for interactive systems . In Proc. DBRank , 2012 . M. Magnani, I. Assent, and M. L. Mortensen. Anytime skyline query processing for interactive systems. In Proc. DBRank, 2012."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213850"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920980"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.84"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260799"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31235-9_9"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.50"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0117-y"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099610"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.240"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732269.2732275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:27:48Z","timestamp":1672223268000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732269.2732275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.14778\/2732269.2732275"],"URL":"https:\/\/doi.org\/10.14778\/2732269.2732275","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}