The DisC Diversity Model.
Marina Drosou, Evaggelia Pitoura · 2014
In this paper, we summarize our work on diversification based on dissimilarity and coverage (DisC diversity) by presenting our main theoretical results and contributions. 1. DISC DIVERSITY Diversification has attracted considerable attention, often as a means of enhancing the quality of the query results presented to users [3]. Most diversification approaches rely on assigning a diversity score to each data item and then selecting as diverse either the k items with the largest score for a given k (e.g., [1]), or the items with score larger than some predefined threshold (e.g., [9]). In our work [4, 5], we address diversity through a di↵erent perspective and aim at selectinga representativesubsetthat contains items that are both dissimilar with each other and cover the whole result set. Let P be a set of items. We define similarity between two items using a distance metric d. Forarealnumberr, r 0, we use Nr(pi) todenotethesetofneighbors (or, the neighborhood) ofanitempi2 P, i.e., the items lying at distance at most r from pi: Nr(pi) ={pj | pi 6 = pj ^ d(pi,pj) apple r} We use N + r (pi) todenotethesetNr(pi) [{pi}. Itemsinthe neighborhood of pi are considered similar to pi, whileitems outside its neighborhood are considered dissimilar to pi. We define an r-DisC diverse subset as follows: Definition 1. (r-DisC Diverse Subset) Let P be a set of items and r, r 0, a real number. A subset S of P is an r-Dissimilar-and-Covering diverse subset, or r-DisC diverse subset, of P, if the following two conditions hold: (i) (coverage condition) 8pi 2P, 9 pj 2 N + r (pi), suchthat pj 2 S and (ii) (dissimilarity condition) 8 pi, pj 2 S with pi 6 = pj, itholdsthatd(pi,pj)>r. This work was supported by “Epirus on Android ” a research project co-financed by the European Union (European Regional Development Fund-ERDF) and Greek national funds through the