{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:03:44Z","timestamp":1755839024153},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>\n            Given a database with numeric attributes, it is often of interest to rank the tuples according to linear scoring functions. For a scoring function and a subset of tuples, the\n            <jats:italic>regret<\/jats:italic>\n            of the subset is defined as the (relative) difference in scores between the top-1 tuple of the subset and the top-1 tuple of the entire database. Finding the\n            <jats:italic>regret-ratio minimizing set<\/jats:italic>\n            (RRMS), i.e., the subset of a required size\n            <jats:italic>k<\/jats:italic>\n            that minimizes the maximum regret-ratio across all possible ranking functions, has been a well-studied problem in recent years. This problem is known to be NP-complete and there are several approximation algorithms for it. Other NP-complete variants have also been investigated, e.g., finding the set of size\n            <jats:italic>k<\/jats:italic>\n            that minimizes the\n            <jats:italic>average regret ratio<\/jats:italic>\n            over all linear functions. Prior work have designed customized algorithms for different variants of the problem, and are unlikely to easily generalize to other variants.\n          <\/jats:p>\n          <jats:p>\n            In this paper we take a different path towards tackling these problems. In contrast to the prior, we propose a unified algorithm for solving different problem variants. Unification is done by localizing the customization to the design of variant-specific subroutines or \"oracles\" that are called by our algorithm. Our unified algorithm takes inspiration from the seemingly unrelated problem of\n            <jats:italic>clustering<\/jats:italic>\n            from data mining, and the corresponding k-medoid algorithm. We make several innovative contributions in designing our algorithm, including various techniques such as linear programming, edge sampling in graphs, volume estimation of multi-dimensional convex polytopes, and several others. We provide rigorous theoretical analysis, as well as substantial experimental evaluations over real and synthetic data sets to demonstrate the practical feasibility of our approach.\n          <\/jats:p>","DOI":"10.14778\/3368289.3368291","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T03:17:35Z","timestamp":1599794255000},"page":"239-251","source":"Crossref","is-referenced-by-count":6,"title":["A unified optimization algorithm for solving \"regret-minimizing representative\" problems"],"prefix":"10.14778","volume":"13","author":[{"given":"Suraj","family":"Shetiya","sequence":"first","affiliation":[{"name":"University of Texas at Arlington"}]},{"given":"Abolfazl","family":"Asudeh","sequence":"additional","affiliation":[{"name":"University of Illinois at Chicago"}]},{"given":"Sadia","family":"Ahmed","sequence":"additional","affiliation":[{"name":"University of Texas at Arlington"}]},{"given":"Gautam","family":"Das","sequence":"additional","affiliation":[{"name":"University of Texas at Arlington"}]}],"member":"320","published-online":{"date-parts":[[2019,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_3_1","volume-title":"VLDB","author":"Das G.","year":"2006","unstructured":"G. Das , D. Gunopulos , N. Koudas , and D. Tsirogiannis . Answering top-k queries using views . In VLDB , 2006 . G. Das, D. Gunopulos, N. Koudas, and D. Tsirogiannis. Answering top-k queries using views. In VLDB, 2006."},{"key":"e_1_2_1_4_1","volume-title":"Query reranking as a service. PVLDB, 9(11)","author":"Asudeh A.","year":"2016","unstructured":"A. Asudeh , N. Zhang , and G. Das . Query reranking as a service. PVLDB, 9(11) , 2016 . A. Asudeh, N. Zhang, and G. Das. Query reranking as a service. PVLDB, 9(11), 2016."},{"issue":"3","key":"e_1_2_1_5_1","first-page":"237","article-title":"On obtaining stable rankings","volume":"12","author":"Asudeh A.","year":"2018","unstructured":"A. Asudeh , H. Jagadish , G. Miklau , and J. Stoyanovich . On obtaining stable rankings . PVDLB , 12 ( 3 ): 237 -- 250 , 2018 . A. Asudeh, H. Jagadish, G. Miklau, and J. Stoyanovich. On obtaining stable rankings. PVDLB, 12(3):237--250, 2018.","journal-title":"PVDLB"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300079"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904491"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806451"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920980"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035932"},{"key":"e_1_2_1_12_1","volume-title":"LIPIcs","author":"Agarwal P. K.","year":"2017","unstructured":"P. K. Agarwal , N. Kumar , S. Sintos , and S. Suri . Efficient algorithms for k-regret minimizing sets . LIPIcs , 2017 . P. K. Agarwal, N. Kumar, S. Sintos, and S. Suri. Efficient algorithms for k-regret minimizing sets. LIPIcs, 2017."},{"key":"e_1_2_1_13_1","volume-title":"Computing k-regret minimizing sets. VLDB, 7(5)","author":"Chester S.","year":"2014","unstructured":"S. Chester , A. Thomo , S. Venkatesh , and S. Whitesides . Computing k-regret minimizing sets. VLDB, 7(5) , 2014 . S. Chester, A. Thomo, S. Venkatesh, and S. Whitesides. Computing k-regret minimizing sets. VLDB, 7(5), 2014."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2914831"},{"key":"e_1_2_1_15_1","first-page":"1722","volume-title":"Finding average regret ratio minimizing set in database","author":"Zeighami S.","year":"2019","unstructured":"S. Zeighami and R. C.-W. Wong . Finding average regret ratio minimizing set in database . pages 1722 -- 1725 , 2019 . S. Zeighami and R. C.-W. Wong. Finding average regret ratio minimizing set in database. pages 1722--1725, 2019."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196903"},{"key":"e_1_2_1_17_1","volume-title":"North-Holland","author":"Kaufman L.","year":"1987","unstructured":"L. Kaufman and P. J. Rousseeuw . Clustering by means of medoids, statistical data analysis based on the l1 norm and related methods. Y. Dodge , North-Holland , 1987 . L. Kaufman and P. J. Rousseeuw. Clustering by means of medoids, statistical data analysis based on the l1 norm and related methods. Y. Dodge, North-Holland, 1987."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217060"},{"issue":"1","key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.21136\/AM.1995.134279","article-title":"On a linearization of regression models","volume":"40","author":"Kub\u00e1\u010dek L.","year":"1995","unstructured":"L. Kub\u00e1\u010dek . On a linearization of regression models . Applications of Mathematics , 40 ( 1 ): 61 -- 78 , 1995 . L. Kub\u00e1\u010dek. On a linearization of regression models. Applications of Mathematics, 40(1):61--78, 1995.","journal-title":"Applications of Mathematics"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582152"},{"key":"e_1_2_1_21_1","first-page":"2012","article-title":"A detailed introduction to k-nearest neighbor (knn) algorithm","volume":"20","author":"Thirumuruganathan S.","year":"2010","unstructured":"S. Thirumuruganathan . A detailed introduction to k-nearest neighbor (knn) algorithm . Retrieved March , 20 : 2012 , 2010 . S. Thirumuruganathan. A detailed introduction to k-nearest neighbor (knn) algorithm. Retrieved March, 20:2012, 2010.","journal-title":"Retrieved March"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102412856"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_2_1_24_1","volume-title":"Monte carlo methods","author":"Hammersley J.","year":"2013","unstructured":"J. Hammersley . Monte carlo methods . Springer Science & Business Media , 2013 . J. Hammersley. Monte carlo methods. Springer Science & Business Media, 2013."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized algorithms","author":"Motwani R.","year":"1995","unstructured":"R. Motwani and P. Raghavan . Randomized algorithms . Cambridge university press , 1995 . R. Motwani and P. Raghavan. Randomized algorithms. Cambridge university press, 1995."},{"key":"e_1_2_1_26_1","unstructured":"Color dataset. https:\/\/archive.ics.uci.edu\/ml\/datasets\/corel+image+features.  Color dataset. https:\/\/archive.ics.uci.edu\/ml\/datasets\/corel+image+features."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412343"},{"key":"e_1_2_1_28_1","unstructured":"US Department of Transportation's dataset. http:\/\/www.transtats.bts.gov\/DL_SelectFields.asp?Table_ID=236&DB_Short_Name=On-Time.  US Department of Transportation's dataset. http:\/\/www.transtats.bts.gov\/DL_SelectFields.asp?Table_ID=236&DB_Short_Name=On-Time."},{"key":"e_1_2_1_29_1","unstructured":"NBA dataset. www.databasebasketball.com\/.  NBA dataset. www.databasebasketball.com\/."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367854"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-010-4041-6"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.84"},{"key":"e_1_2_1_33_1","first-page":"204","volume-title":"ICDT","author":"Koltun V.","year":"2005","unstructured":"V. Koltun and C. H. Papadimitriou . Approximately dominating representatives . In ICDT , pages 204 -- 214 . Springer , 2005 . V. Koltun and C. H. Papadimitriou. Approximately dominating representatives. In ICDT, pages 204--214. Springer, 2005."},{"key":"e_1_2_1_34_1","first-page":"1","volume-title":"COMAD","author":"Aggarwal S.","year":"2016","unstructured":"S. Aggarwal , S. Mitra , and A. Bhattacharya . Skycover: Finding range-constrained approximate skylines with bounded quality guarantees . In COMAD , pages 1 -- 12 , 2016 . S. Aggarwal, S. Mitra, and A. Bhattacharya. Skycover: Finding range-constrained approximate skylines with bounded quality guarantees. In COMAD, pages 1--12, 2016."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213850"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3133012"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/358315.358392"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2015.07.007"},{"key":"e_1_2_1_40_1","first-page":"255","volume-title":"PKDD","author":"Jin W.","year":"2004","unstructured":"W. Jin , J. Han , and M. Ester . Mining thick skylines over large databases . In PKDD , pages 255 -- 266 . Springer , 2004 . W. Jin, J. Han, and M. Ester. Mining thick skylines over large databases. In PKDD, pages 255--266. Springer, 2004."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452424"},{"issue":"7","key":"e_1_2_1_42_1","first-page":"991","article-title":"Flexible and efficient resolution of skyline query size constraints","volume":"23","author":"Lu H.","year":"2010","unstructured":"H. Lu , C. S. Jensen , and Z. Zhang . Flexible and efficient resolution of skyline query size constraints . TKDE , 23 ( 7 ): 991 -- 1005 , 2010 . H. Lu, C. S. Jensen, and Z. Zhang. Flexible and efficient resolution of skyline query size constraints. TKDE, 23(7):991--1005, 2010.","journal-title":"TKDE"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316801","volume-title":"Finding groups in data: An introduction to cluster analysis","author":"Kaufman L.","year":"1990","unstructured":"L. Kaufman and P. Rousseeuw . Finding groups in data: An introduction to cluster analysis . 1990 . L. Kaufman and P. Rousseeuw. Finding groups in data: An introduction to cluster analysis. 1990."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1033770"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3368289.3368291","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:42:25Z","timestamp":1672220545000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3368289.3368291"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["10.14778\/3368289.3368291"],"URL":"https:\/\/doi.org\/10.14778\/3368289.3368291","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}