{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T07:32:15Z","timestamp":1779262335973,"version":"3.51.4"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61832003"],"award-info":[{"award-number":["61832003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>A top-k query retrieves the k tuples with highest scores according to a user preference, defined as a scoring function. It is difficult for a user to precisely specify the scoring function. Instead, obtaining the distribution on scoring functions, i.e., the preference distribution, has been extensively explored in many fields.<\/jats:p>\n          <jats:p>Motivated by this, we introduce the uniform (r,k)-hit (UrkHit) problem. Given a preference distribution, UrkHit aims to select a representative set of r tuples to maximize the probability of containing a tuple attractive to the user. We say a tuple attracts a user, if it is a top-k tuple for the scoring function adopted by the user. Further, we generalize UrkHit and propose the (r,k)-hit (rkHit) problem with an additional penalty function to model the user satisfaction with the tuple ranked i-th. rkHit aims to maximize the expected user satisfaction with the representative set. In 2D space, we design an exact algorithm 2DH for rkHit, indicating rkHit is in P for d=2. We show that rkHit is NP-hard when d\\ge3. In 3D space, assuming a uniform preference distribution, we propose a (1-1\/e)-approximation algorithm 3DH based on space partitioning. In addition, we propose an approximate algorithm MDH suitable for any dimension and distribution, which creatively combines the ideas of sampling and clustering. It relaxes the approximation guarantee slightly. Comprehensive experiments demonstrate the efficiency and effectiveness of our algorithms.<\/jats:p>","DOI":"10.1145\/3589271","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["rkHit: Representative Query with Uncertain Preference"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3364-8471","authenticated-orcid":false,"given":"Xingxing","family":"Xiao","sequence":"first","affiliation":[{"name":"Harbin Institute of Technology &amp; Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Harbin, Heilongjiang, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4119-0571","authenticated-orcid":false,"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen, Guangdong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"16th International Symposium on Experimental Algorithms (SEA 2017) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"23","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 16th International Symposium on Experimental Algorithms (SEA 2017) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 75). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 7:1--7:23."},{"key":"e_1_2_2_2_1","volume-title":"Agarwal and Micha Sharir","author":"Pankaj","year":"2000","unstructured":"Pankaj K. Agarwal and Micha Sharir. 2000. Arrangements and Their Applications. In Handbook of Computational Geometry. North-Holland, Amsterdam, 49--119."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325909"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3531054"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3291264.3291269"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300079"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035932"},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of the 2019 International Conference on Management of Data","author":"Asudeh Abolfazl","unstructured":"Abolfazl Asudeh, Azade Nazi, Nan Zhang, Gautam Das, and H. V. Jagadish. 2019b. RRR: Rank-Regret Representative. In Proceedings of the 2019 International Conference on Management of Data (Amsterdam, Netherlands) (SIGMOD '19). Association for Computing Machinery, New York, NY, USA, 263--280."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261274"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188711"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1005356"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the 17th International Conference on Data Engineering, April 2--6","author":"Stephan","year":"2001","unstructured":"Stephan B\u00f6 rzs\u00f6 nyi, Donald Kossmann, and Konrad Stocker. 2001. The Skyline Operator. In Proceedings of the 17th International Conference on Data Engineering, April 2--6, 2001, Heidelberg, Germany. IEEE Computer Society, 421--430."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2002.994751"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90156-7"},{"key":"e_1_2_2_15_1","volume-title":"20th International Conference on Database Theory (ICDT 2017)","volume":"19","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 20th International Conference on Database Theory (ICDT 2017) (LIPIcs, Vol. 68). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 11:1--11:19."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732275"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102369"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137653"},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the 26th Italian Symposium on Advanced Database Systems, Castellaneta Marina (Taranto), Italy, June 24--27, 2018 (CEUR Workshop Proceedings","author":"Ciaccia Paolo","year":"2018","unstructured":"Paolo Ciaccia and Davide Martinenghi. 2018. Beyond Skyline and Ranking Queries: Restricted Skylines (Extended Abstract). In Proceedings of the 26th Italian Symposium on Advanced Database Systems, Castellaneta Marina (Taranto), Italy, June 24--27, 2018 (CEUR Workshop Proceedings, Vol. 2161). CEUR-WS.org."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406113"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1325851.1325875"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164167"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24627-5_7"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/261342.571216"},{"key":"e_1_2_2_27_1","unstructured":"Leonard Kaufman and Peter Rousseeuw. 1987. Clustering by means of medoids. Statistical Data Analysis Based on the L1-Norm and Related Methods Y. Dodge Ed."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367854"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407809"},{"key":"e_1_2_2_30_1","volume-title":"Optimization techniques","author":"Minoux Michel","unstructured":"Michel Minoux. 1978. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization techniques. Springer, Berlin, Heidelberg, 234--243."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457299"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204031"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920980"},{"key":"e_1_2_2_34_1","volume-title":"Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research","author":"Nemhauser George L","year":"1978","unstructured":"George L Nemhauser and Laurence A Wolsey. 1978. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, Vol. 3, 3 (1978), 177--188."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723735"},{"key":"e_1_2_2_37_1","volume-title":"Chernoff-Hoeffding Inequality and Applications. CoRR","author":"Phillips Jeff M.","year":"2012","unstructured":"Jeff M. Phillips. 2012. Chernoff-Hoeffding Inequality and Applications. CoRR, Vol. abs\/1209.6396 (2012). showeprint[arXiv]1209.6396 http:\/\/arxiv.org\/abs\/1209.6396"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809992"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/245108.245121"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0--387--85820--3_1"},{"key":"e_1_2_2_41_1","volume-title":"Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11--16","author":"Sarma Atish Das","year":"2011","unstructured":"Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Richard J. Lipton, and Jun (Jim) Xu. 2011. Representative skylines using threshold-based preference distributions. In Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11--16, 2011, Hannover, Germany. IEEE Computer Society, 387--398."},{"key":"e_1_2_2_42_1","first-page":"3","article-title":"A Unified Optimization Algorithm for Solving \"Regret-Minimizing Representative","volume":"13","author":"Shetiya Suraj","year":"2019","unstructured":"Suraj Shetiya, Abolfazl Asudeh, Sadia Ahmed, and Gautam Das. 2019. A Unified Optimization Algorithm for Solving \"Regret-Minimizing Representative\" Problems. Proc. VLDB Endow., Vol. 13, 3 (nov 2019), 239--251.","journal-title":"Problems. Proc. VLDB Endow."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3207692.3207708"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989408"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722205"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452832"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339500"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.84"},{"key":"e_1_2_2_49_1","volume-title":"On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Theory of Probability and its Applications","author":"Vapnik VN","year":"1971","unstructured":"VN Vapnik and A Ya Chervonenkis. 1971. On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Theory of Probability and its Applications, Vol. 16, 2 (1971), 264."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457322"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00144"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458322"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830922500240"},{"key":"e_1_2_2_54_1","volume-title":"Rank-Regret Minimization. In 38th IEEE International Conference on Data Engineering, ICDE 2022","author":"Xiao Xingxing","year":"2022","unstructured":"Xingxing Xiao and Jianzhong Li. 2022. Rank-Regret Minimization. In 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9--12, 2022. IEEE, 1848--1860."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00570-z"},{"key":"e_1_2_2_56_1","volume-title":"36th IEEE International Conference on Data Engineering, ICDE 2020","author":"Xie Min","year":"2020","unstructured":"Min Xie, Raymond Chi-Wing Wong, Peng Peng, and Vassilis J. Tsotras. 2020b. Being Happy with the Least: Achieving (\u03b1)-happiness with Minimum Number of Tuples. In 36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20--24, 2020. IEEE, 1009--1020."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300068"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164149"},{"key":"e_1_2_2_59_1","volume-title":"Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017","author":"Yang Guolei","year":"2017","unstructured":"Guolei Yang and Ying Cai. 2017. Querying Improvement Strategies. In Proceedings of the 20th International Conference on Extending Database Technology, EDBT 2017, Venice, Italy, March 21--24, 2017. OpenProceedings.org, 294--305."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589271","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:54Z","timestamp":1750182534000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589271"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":58,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589271"],"URL":"https:\/\/doi.org\/10.1145\/3589271","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}