{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:01Z","timestamp":1750220161642,"version":"3.41.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,8,18]],"date-time":"2022-08-18T00:00:00Z","timestamp":1660780800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>Selecting the best items in a dataset is a common task in data exploration. However, the concept of \u201cbest\u201d lies in the eyes of the beholder: Different users may consider different attributes more important and, hence, arrive at different rankings. Nevertheless, one can remove \u201cdominated\u201d items and create a \u201crepresentative\u201d subset of the data, comprising the \u201cbest items\u201d in it. A Pareto-optimal representative is guaranteed to contain the best item of each possible ranking, but it can be a large portion of data. A much smaller representative can be found if we relax the requirement of including the best item for each user and instead just limit the users\u2019 \u201cregret.\u201d Existing work defines regret as the loss in score by limiting consideration to the representative instead of the full dataset, for any chosen ranking function.<\/jats:p>\n          <jats:p>\n            However, the score is often not a meaningful number, and users may not understand its absolute value. Sometimes small ranges in score can include large fractions of the dataset. In contrast, users do understand the notion of rank ordering. Therefore, we consider items\u2019 positions in the ranked list in defining the regret and propose the\n            <jats:italic>rank-regret representative<\/jats:italic>\n            as the minimal subset of the data containing at least one of the top-\n            <jats:italic>k<\/jats:italic>\n            of any possible ranking function. This problem is polynomial time solvable in two-dimensional space but is NP-hard on three or more dimensions. We design a suite of algorithms to fulfill different purposes, such as whether relaxation is permitted on\n            <jats:italic>k<\/jats:italic>\n            , the result size, or both, whether a distribution is known, whether theoretical guarantees or practical efficiency is important, and so on. Experiments on real datasets demonstrate that we can efficiently find small subsets with small rank-regrets.\n          <\/jats:p>","DOI":"10.1145\/3531054","type":"journal-article","created":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T06:31:37Z","timestamp":1651127497000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["On Finding Rank Regret Representatives"],"prefix":"10.1145","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5251-6186","authenticated-orcid":false,"given":"Abolfazl","family":"Asudeh","sequence":"first","affiliation":[{"name":"University of Illinois Chicago, Chicago, Illinois"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4627-9065","authenticated-orcid":false,"given":"Gautam","family":"Das","sequence":"additional","affiliation":[{"name":"University of Texas at Arlington, Arlington, Texas"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0724-5214","authenticated-orcid":false,"given":"H. V.","family":"Jagadish","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, Michigan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7517-7252","authenticated-orcid":false,"given":"Shangqi","family":"Lu","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4027-6250","authenticated-orcid":false,"given":"Azade","family":"Nazi","sequence":"additional","affiliation":[{"name":"Google Brain, Mountain View, California"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3883-5452","authenticated-orcid":false,"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8929-0395","authenticated-orcid":false,"given":"Nan","family":"Zhang","sequence":"additional","affiliation":[{"name":"American University, Washington DC"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0454-7885","authenticated-orcid":false,"given":"Jianwen","family":"Zhao","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong, China"}]}],"member":"320","published-online":{"date-parts":[[2022,8,18]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/3116258.3116371"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281840"},{"key":"e_1_3_3_4_2","first-page":"7:1\u20137:23","volume-title":"Proceedings of the International Symposium on Experimental Algorithms","author":"Agarwal Pankaj K.","year":"2017","unstructured":"Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos, and Subhash Suri. 2017. Efficient algorithms for k-regret minimizing sets. In Proceedings of the International Symposium on Experimental Algorithms. 7:1\u20137:23."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000225"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90122-6"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48447-7_1"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035932"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300080"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904491"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806451"},{"issue":"11","key":"e_1_3_3_13_2","article-title":"Query reranking as a service","volume":"9","author":"Asudeh Abolfazl","year":"2016","unstructured":"Abolfazl Asudeh, Nan Zhang, and Gautam Das. 2016. Query reranking as a service. Proc. VLDB 9, 11 (2016), 888\u2013899.","journal-title":"Proc. VLDB"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2001.914855"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796260321"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/568518.568519"},{"key":"e_1_3_3_17_2","first-page":"11:1\u201311:19","volume-title":"Proceedings of the International Conference on Database Theory (ICDT\u201917)","author":"Cao Wei","year":"2017","unstructured":"Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, and Wei Zhan. 2017. k-regret minimizing set: Efficient algorithms and hardness. In Proceedings of the International Conference on Database Theory (ICDT\u201917). 11:1\u201311:19."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142530"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712874"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.125"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-016-9784-4"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335433"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732275"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187740"},{"key":"e_1_3_3_25_2","volume-title":"Proceedings of Very Large Data Bases (VLDB)","author":"Das Gautam","year":"2006","unstructured":"Gautam Das, Dimitrios Gunopulos, Nick Koudas, and Dimitris Tsirogiannis. 2006. Answering top-k queries using views. In Proceedings of Very Large Data Bases (VLDB). 451\u2013462."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009354"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161148"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/28905"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00181432"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(85)90017-2"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-7204-2262-7.50018-1"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/160985.160994"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102412856"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00199"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.5555\/2031416"},{"key":"e_1_3_3_38_2","article-title":"On the expected complexity of random convex hulls","volume":"1111","author":"Har-Peled Sariel","year":"2011","unstructured":"Sariel Har-Peled. 2011. On the expected complexity of random convex hulls. CoRR abs\/1111.5340 (2011).","journal-title":"CoRR"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0099-8"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"issue":"13","key":"e_1_3_3_42_2","article-title":"k-regret queries with nonlinear utilities","volume":"8","author":"Faulkner Taylor Kessler","year":"2015","unstructured":"Taylor Kessler Faulkner, Will Brackenbury, and Ashwin Lall. 2015. k-regret queries with nonlinear utilities. VLDB J. 8, 13 (2015), 2098\u20132109.","journal-title":"VLDB J."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187833"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975055.6"},{"key":"e_1_3_3_45_2","first-page":"54:1\u201354:16","volume-title":"Proceedings of the Symposium on Computational Geometry (SoCG\u201916)","author":"Kupavskii Andrey","year":"2016","unstructured":"Andrey Kupavskii, Nabil H. Mustafa, and Janos Pach. 2016. New lower bounds for epsilon-nets. In Proceedings of the Symposium on Computational Geometry (SoCG\u201916). 54:1\u201354:16."},{"key":"e_1_3_3_46_2","first-page":"107","article-title":"On the number of halving lines","volume":"14","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1971","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. 1971. On the number of halving lines. Ann. Univ. Sci. Budapest, E\u00f6tv\u00f6s, Sec. Math 14 (1971), 107\u2013108.","journal-title":"Ann. Univ. Sci. Budapest, E\u00f6tv\u00f6s, Sec. Math"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1005566.1005569"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90006-E"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1023"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574692"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213850"},{"key":"e_1_3_3_52_2","doi-asserted-by":"crossref","unstructured":"Danupon Nanongkai Atish Das Sarma Ashwin Lall Richard J. Lipton and Jun Xu. 2010. Regret-minimizing representative databases. Proc. VLDB Endow. 3 1 (2010) 1114\u20131124.","DOI":"10.14778\/1920841.1920980"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187829"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816699"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3133012"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304993"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-001-0005-3"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389245"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010022"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806777"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2010.03.008"},{"key":"e_1_3_3_63_2","volume-title":"Proceedings of Very Large Data Bases (VLDB)","author":"Xin Dong","year":"2006","unstructured":"Dong Xin, Chen Chen, and Jiawei Han. 2006. Towards robust indexing for ranked queries. In Proceedings of Very Large Data Bases (VLDB). 235\u2013246."},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2914831"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531054","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531054","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:27Z","timestamp":1750186827000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531054"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,18]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3531054"],"URL":"https:\/\/doi.org\/10.1145\/3531054","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2022,8,18]]},"assertion":[{"value":"2020-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}