{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:46:30Z","timestamp":1759682790261,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,3,25]],"date-time":"2015-03-25T00:00:00Z","timestamp":1427241600000},"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":[[2015,3,25]]},"abstract":"<jats:p>\n            Recently, result diversification has attracted a lot of attention as a means to improve the quality of results retrieved by user queries. In this article, we introduce a novel definition of diversity called DisC diversity. Given a tuning parameter\n            <jats:italic>r<\/jats:italic>\n            , which we call radius, we consider two items to be similar if their distance is smaller than or equal to\n            <jats:italic>r<\/jats:italic>\n            . A DisC diverse subset of a result contains items such that each item in the result is represented by a similar item in the diverse subset and the items 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 algorithms for its approximation. We extend our definition to the multiple radii case, where each item is associated with a different radius based on its importance, relevance, or other factors. We also propose adapting DisC diverse subsets to a different degree of diversification by adjusting\n            <jats:italic>r<\/jats:italic>\n            , that is, increasing the radius (or zooming-out) and decreasing the radius (or zooming-in). We present efficient implementations of our algorithms based on the M-tree, a spatial index structure, and experimentally evaluate their performance.\n          <\/jats:p>","DOI":"10.1145\/2699499","type":"journal-article","created":{"date-parts":[[2015,3,25]],"date-time":"2015-03-25T16:03:43Z","timestamp":1427299423000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Multiple Radii DisC Diversity"],"prefix":"10.1145","volume":"40","author":[{"given":"Marina","family":"Drosou","sequence":"first","affiliation":[{"name":"University of Ioannina, Ipiros, Greece"}]},{"given":"Evaggelia","family":"Pitoura","sequence":"additional","affiliation":[{"name":"University of Ioannina, Ipiros, Greece"}]}],"member":"320","published-online":{"date-parts":[[2015,3,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462401"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498759.1498766"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989405"},{"key":"e_1_2_1_4_1","unstructured":"Claude Berge. 1962. The Theory of Graphs and Its Applications. Methuen.  Claude Berge. 1962. The Theory of Graphs and Its Applications. Methuen."},{"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.dam.2012.01.003"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/1988776.1988781"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/290941.291025"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487259.2487262"},{"volume-title":"Proceedings of the 5th Scandinavian Workshop on Algorithm Theory (SWAT'96)","author":"Chandra Barun","key":"e_1_2_1_11_1","unstructured":"Barun Chandra and Magnus M. Halldorsson . 1996. Facility dispersion and remote subgraphs . In Proceedings of the 5th Scandinavian Workshop on Algorithm Theory (SWAT'96) . 53--65. Barun Chandra and Magnus M. Halldorsson. 1996. Facility dispersion and remote subgraphs. In Proceedings of the 5th Scandinavian Workshop on Algorithm Theory (SWAT'96). 53--65."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00232-5"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.07.003"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB'97)","author":"Ciaccia Paolo","year":"1997","unstructured":"Paolo Ciaccia , Marco Patella , and Pavel Zezula . 1997 . M-tree: An efficient access method for similarity search in metric spaces . In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB'97) . 426--435. Paolo Ciaccia, Marco Patella, and Pavel Zezula. 1997. M-tree: An efficient access method for similarity search in metric spaces. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB'97). 426--435."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390446"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Guilherme Dias da Fonseca Celina M. Herrera de Figueiredo Vinicius G. P. de Sa and Raphael Machado. 2012. Linear time approximation for dominating sets and independent dominating sets in unit disk graphs. http:\/\/www.uniriotec.br\/&sim;fonseca\/domudg_conf.pdf.  Guilherme Dias da Fonseca Celina M. Herrera de Figueiredo Vinicius G. P. de Sa and Raphael Machado. 2012. Linear time approximation for dominating sets and independent dominating sets in unit disk graphs. http:\/\/www.uniriotec.br\/&sim;fonseca\/domudg_conf.pdf.","DOI":"10.1007\/978-3-642-38016-7_8"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536354.2536358"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860709"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2428536.2428538"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247623"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(94)90041-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873624"},{"key":"e_1_2_1_24_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_25_1","volume-title":"Pirwani","author":"Gibson Matt","year":"2010","unstructured":"Matt Gibson and Imran A . Pirwani . 2010 . Approximation algorithms for dominating set in disk graphs. http:\/\/arxiv.org\/pdf\/1004.3320v1.pdf Matt Gibson and Imran A. Pirwani. 2010. Approximation algorithms for dominating set in disk graphs. http:\/\/arxiv.org\/pdf\/1004.3320v1.pdf"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526761"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90022-2"},{"key":"e_1_2_1_28_1","first-page":"15","article-title":"The KNDN problem: A quest for unity in diversity","volume":"32","author":"Haritsa Jayant R.","year":"2009","unstructured":"Jayant R. Haritsa . 2009 . The KNDN problem: A quest for unity in diversity . IEEE Data Engin. Bull. 32 , 4, 15 -- 22 . Jayant R. Haritsa. 2009. The KNDN problem: A quest for unity in diversity. IEEE Data Engin. Bull. 32, 4, 15--22.","journal-title":"IEEE Data Engin. Bull."},{"volume-title":"Proceedings of the 8th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD'04)","author":"Jain Anoop","key":"e_1_2_1_29_1","unstructured":"Anoop Jain , Parag Sarda , and Jayant R. Haritsa . 2004. Providing diversity in k-nearest neighbor query results . In Proceedings of the 8th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD'04) . 404--413. Anoop Jain, Parag Sarda, and Jayant R. Haritsa. 2004. Providing diversity in k-nearest neighbor query results. In Proceedings of the 8th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD'04). 404--413."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.027"},{"volume-title":"Proceedings of the 24th International Conference on Very Large Data Bases (VLDB'98)","author":"Edwin","key":"e_1_2_1_31_1","unstructured":"Edwin M. Knorr and Raymond T. Ng. 1998. Algorithms for mining distance-based outliers in large datasets . In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB'98) . 392--403. Edwin M. Knorr and Raymond T. Ng. 1998. Algorithms for mining distance-based outliers in large datasets. In Proceedings of the 24th International Conference on Very Large Data Bases (VLDB'98). 392--403."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536373"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687643"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788692"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009996"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2010.06.009"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124329"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350233"},{"key":"e_1_2_1_39_1","volume-title":"Reddy and Bhanukiran Vinzamuri","author":"Chandan","year":"2013","unstructured":"Chandan K. Reddy and Bhanukiran Vinzamuri . 2013 . A survey of partitional and hierarchical clustering algorithms. In Data Clustering: Algorithms and Applications, Chapman and Hall\/CRC , 87--110. Chandan K. Reddy and Bhanukiran Vinzamuri. 2013. A survey of partitional and hierarchical clustering algorithms. In Data Clustering: Algorithms and Applications, Chapman and Hall\/CRC, 87--110."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.2.299"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484854"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488497"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404048"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.84"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2007.1034"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.025"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.991715"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452424"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497431"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767846"},{"key":"e_1_2_1_51_1","unstructured":"Isaac Ottoni Wilhelm. 2008. Packing triangles on a sphere. http:\/\/www.math.uchicago.edu\/&sim;may\/VIGRE2008\/REUPapers\/Wilhelm.pdf.  Isaac Ottoni Wilhelm. 2008. Packing triangles on a sphere. http:\/\/www.math.uchicago.edu\/&sim;may\/VIGRE2008\/REUPapers\/Wilhelm.pdf."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2008.39"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516404"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454008.1454030"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/564376.564393"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060754"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.022"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699499","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699499","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:58Z","timestamp":1750227418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699499"}},"subtitle":["Result Diversification Based on Dissimilarity and Coverage"],"short-title":[],"issued":{"date-parts":[[2015,3,25]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,3,25]]}},"alternative-id":["10.1145\/2699499"],"URL":"https:\/\/doi.org\/10.1145\/2699499","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2015,3,25]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}