{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T10:14:00Z","timestamp":1781518440554,"version":"3.54.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>\n            We propose the\n            <jats:italic>k<\/jats:italic>\n            -representative regret minimization query (\n            <jats:italic>k<\/jats:italic>\n            -regret) as an operation to support multi-criteria decision making. Like top-\n            <jats:italic>k<\/jats:italic>\n            , the\n            <jats:italic>k<\/jats:italic>\n            -regret query assumes that users have some utility or scoring functions; however, it never asks the users to provide such functions. Like skyline, it filters out a set of interesting points from a potentially large database based on the users' criteria; however, it never overwhelms the users by outputting too many tuples.\n          <\/jats:p>\n          <jats:p>\n            In particular, for any number\n            <jats:italic>k<\/jats:italic>\n            and any class of utility functions, the\n            <jats:italic>k<\/jats:italic>\n            -regret query outputs\n            <jats:italic>k<\/jats:italic>\n            tuples from the database and tries to minimize the\n            <jats:italic>maximum regret ratio<\/jats:italic>\n            . This captures how disappointed a user could be had she seen\n            <jats:italic>k<\/jats:italic>\n            representative tuples instead of the whole database. We focus on the class of linear utility functions, which is widely applicable.\n          <\/jats:p>\n          <jats:p>The first challenge of this approach is that it is not clear if the maximum regret ratio would be small, or even bounded. We answer this question affirmatively. Theoretically, we prove that the maximum regret ratio can be bounded and this bound is independent of the database size. Moreover, our extensive experiments on real and synthetic datasets suggest that in practice the maximum regret ratio is reasonably small. Additionally, algorithms developed in this paper are practical as they run in linear time in the size of the database and the experiments show that their running time is small when they run on top of the skyline operation which means that these algorithm could be integrated into current database systems.<\/jats:p>","DOI":"10.14778\/1920841.1920980","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1114-1124","source":"Crossref","is-referenced-by-count":95,"title":["Regret-minimizing representative databases"],"prefix":"10.14778","volume":"3","author":[{"given":"Danupon","family":"Nanongkai","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Atish Das","family":"Sarma","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashwin","family":"Lall","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard J.","family":"Lipton","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jun","family":"Xu","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Gnu linear programming kit version 4.39 . http:\/\/www.gnu.org\/software\/glpk\/glpk.html.  Gnu linear programming kit version 4.39 . http:\/\/www.gnu.org\/software\/glpk\/glpk.html."},{"key":"e_1_2_1_2_1","volume-title":"September","author":"Theory Algorithmic Game","year":"2007","unstructured":"Algorithmic Game Theory . Cambridge University Press , September 2007 . Algorithmic Game Theory. Cambridge University Press, September 2007."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322095"},{"key":"e_1_2_1_4_1","volume-title":"Introduction to Linear Optimization","author":"Bertsimas D.","year":"1997","unstructured":"D. Bertsimas and J. Tsitsiklis . Introduction to Linear Optimization . Athena Scientific , 1997 . D. Bertsimas and J. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142530"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_30"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335433"},{"key":"e_1_2_1_9_1","volume-title":"Multiobjective programming and planning","author":"Cohon J. L.","year":"2004","unstructured":"J. L. Cohon . Multiobjective programming and planning . Dover Publications , 2004 . J. L. Cohon. Multiobjective programming and planning. Dover Publications, 2004."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1118\/1.2335486"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.3138\/FM57-6770-U75U-7727"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24627-5_7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0029-7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575863_99"},{"key":"e_1_2_1_15_1","volume-title":"Survey of polygonal surface simplification algorithms","author":"Heckbert P.","year":"1997","unstructured":"P. Heckbert and M. Garland . Survey of polygonal surface simplification algorithms , 1997 . P. Heckbert and M. Garland. Survey of polygonal surface simplification algorithms, 1997."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375690"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/PCI.2008.45"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.04.004"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516437"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367854"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687697"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2391952.2391971"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0146-664X(72)80017-0"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02238642"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.84"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260799"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497568"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00368-1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0117-y"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0162-1"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920980","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:48:02Z","timestamp":1672228082000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920980"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":32,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920980"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920980","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}