{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:54:29Z","timestamp":1775638469354,"version":"3.50.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p>\n            Query result diversification is widely used in data exploration, Web search, and recommendation systems. The problem of returning diversified query results consists of finding a small subset of valid query answers that are representative and different from one another, usually quantified by a diversity score. Most existing techniques for query diversification first compute all valid query results and then find a diverse subset. These techniques are inefficient when the set of valid query results is large. Other work has proposed efficient solutions for restricted application settings, where results are shared across multiple queries. In this paper, our goal is to support result diversification for\n            <jats:italic>general range queries over a single relation.<\/jats:italic>\n            We propose the RC-Index, a novel index structure that achieves efficiency by reducing the number of items that must be retrieved by the database to form a diverse set of the desired size (about 1 second for a dataset of 1 million items). Further, we prove that an RC-Index offers strong approximation guarantees. To the best of our knowledge, this is the first index-based diversification method with a guaranteed approximation ratio for range queries.\n          <\/jats:p>","DOI":"10.14778\/3192965.3192969","type":"journal-article","created":{"date-parts":[[2018,5,22]],"date-time":"2018-05-22T19:56:10Z","timestamp":1527018970000},"page":"773-786","source":"Crossref","is-referenced-by-count":11,"title":["RC-index"],"prefix":"10.14778","volume":"11","author":[{"given":"Yue","family":"Wang","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandra","family":"Meliou","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerome","family":"Miklau","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90117-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/356789.356797"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-1699(99)00046-0"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/290941.291025"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055541"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536354.2536358"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602136"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.44"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860709"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2428536.2428538"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247623"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(90)90297-O"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526761"},{"key":"e_1_2_1_19_1","first-page":"562","volume-title":"VLDB","author":"Hellerstein Joseph M.","year":"1995"},{"issue":"169","key":"e_1_2_1_20_1","first-page":"176","article-title":"Online decorrelation of humidity and temperature in chemical sensors for continuous monitoring","volume":"157","author":"Huerta Ramon","year":"2016","journal-title":"Chemometrics and Intelligent Laboratory Systems"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594560"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113295"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484858"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505740"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2618243.2618253"},{"key":"e_1_2_1_27_1","first-page":"798","volume-title":"SODA","author":"Krauthgamer Robert","year":"2004"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263763"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/320613.320618"},{"key":"e_1_2_1_30_1","unstructured":"M. Lichman. UCI machine learning repository 2013.  M. Lichman. UCI machine learning repository 2013."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90119-3"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009996"},{"issue":"22","key":"e_1_2_1_34_1","first-page":"31","article-title":"A data-driven approach to predict the success of bank telemarketing","volume":"62","author":"Moro S\u00e9rgio","year":"2014","journal-title":"Decision Support Systems"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202005"},{"key":"e_1_2_1_36_1","unstructured":"Stephen M. Omohundro. Five balltree construction algorithms. Technical report 1989.  Stephen M. Omohundro. Five balltree construction algorithms. Technical report 1989."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350233"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.2.299"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1561\/1500000040"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404048"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497431"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767846"},{"key":"e_1_2_1_43_1","unstructured":"Yue Wang Alexandra Meliou and Gerome Miklau. Rc-index: Diversifying answers to range queries. Technical report https:\/\/web.cs.umass.edu\/publication\/details.php?id=2445 2017.  Yue Wang Alexandra Meliou and Gerome Miklau. Rc-index: Diversifying answers to range queries. Technical report https:\/\/web.cs.umass.edu\/publication\/details.php?id=2445 2017."},{"key":"e_1_2_1_44_1","first-page":"194","volume-title":"VLDB","author":"Weber Roger","year":"1998"},{"key":"e_1_2_1_45_1","volume-title":"Outstanding Dissertations in the Computer Sciences","author":"Willard Dan E.","year":"1978"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516404"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0990-4"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3192965.3192969","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:14:02Z","timestamp":1672226042000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3192965.3192969"}},"subtitle":["diversifying answers to range queries"],"short-title":[],"issued":{"date-parts":[[2018,3]]},"references-count":47,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["10.14778\/3192965.3192969"],"URL":"https:\/\/doi.org\/10.14778\/3192965.3192969","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,3]]}}}