{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T22:39:24Z","timestamp":1781908764910,"version":"3.54.5"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,11]]},"abstract":"<jats:p>Recently, result diversification has attracted a lot of attention as a means to improve the quality of results retrieved by user queries. In this paper, we propose a new, intuitive definition of diversity called DisC diversity. A DisC diverse subset of a query result contains objects such that each object in the result is represented by a similar object in the diverse subset and the objects in the diverse subset are dissimilar to each other. We show that locating a minimum DisC diverse subset is an NP-hard problem and provide heuristics for its approximation. We also propose adapting DisC diverse subsets to a different degree of diversification. We call this operation zooming. We present efficient implementations of our algorithms based on the M-tree, a spatial index structure, and experimentally evaluate their performance.<\/jats:p>","DOI":"10.14778\/2428536.2428538","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"13-24","source":"Crossref","is-referenced-by-count":71,"title":["DisC diversity"],"prefix":"10.14778","volume":"6","author":[{"given":"Marina","family":"Drosou","sequence":"first","affiliation":[{"name":"University of Ioannina, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Evaggelia","family":"Pitoura","sequence":"additional","affiliation":[{"name":"University of Ioannina, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Acme digital cameras database. http:\/\/acme.com\/digicams.  Acme digital cameras database. http:\/\/acme.com\/digicams."},{"key":"e_1_2_1_2_1","unstructured":"Greek cities dataset. http:\/\/www.rtreeportal.org.  Greek cities dataset. http:\/\/www.rtreeportal.org."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498759.1498766"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989405"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063684"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213580"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.07.003"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390446"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860709"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247623"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(94)90041-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213884"},{"key":"e_1_2_1_15_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman , 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526761"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90022-2"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24775-3_49"},{"key":"e_1_2_1_19_1","volume-title":"Using trees to depict a forest. PVLDB, 2(1)","author":"Liu B.","year":"2009","unstructured":"B. Liu and H. V. Jagadish . Using trees to depict a forest. PVLDB, 2(1) , 2009 . B. Liu and H. V. Jagadish. Using trees to depict a forest. PVLDB, 2(1), 2009."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009996"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124329"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.84"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2007.1034"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.025"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.991715"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497431"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767846"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2008.39"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516404"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1121569"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454008.1454030"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060754"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2428536.2428538","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:38:35Z","timestamp":1672223915000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2428536.2428538"}},"subtitle":["result diversification based on dissimilarity and coverage"],"short-title":[],"issued":{"date-parts":[[2012,11]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,11]]}},"alternative-id":["10.14778\/2428536.2428538"],"URL":"https:\/\/doi.org\/10.14778\/2428536.2428538","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,11]]}}}