DisC Diversity: Result Diversification based on Dissimilarity and Coverage

1. INTRODUCTION

• A DisC diverse subset represents every result object with a similar selected object while ensuring that selected objects are pairwise dissimilar.Similarity is defined by distance at most radius r.Source: §1 · p. 1
• Unlike approaches that select objects by diversity scores, DisC diversity combines dissimilarity among selected objects with coverage of the whole result set.The introduction describes prior models based on content, novelty, or semantic coverage, often selecting objects by score.Source: §1 · p. 1
• Radius r sets the diversification level: increasing it yields smaller, more diverse subsets, while decreasing it yields larger, less diverse subsets.The paper calls these operations zooming-out and zooming-in, respectively, and also allows local zooming around a selected object.Source: §1 · p. 1
• Incremental zooming produces sets of similar sizes to recomputing from scratch, closer to users’ intuitive expectations and at lower computational cost.The basic heuristic runs faster than its greedy variation but produces larger sets; relaxing dissimilarity does not considerably reduce result size.Source: §1 · p. 2
• Finding a minimum DisC diverse subset is NP-hard; the paper provides heuristics, approximation bounds, and incremental algorithms for adapting subsets to new radii.It formalizes the problem as an independent dominating set problem on graphs.Source: §1 · pp. 1–2
• The paper develops M-tree-based algorithms and experimentally evaluates its diversification and zooming methods.The M-tree implementation targets neighbor searches, a central operation in computing DisC diverse subsets.Source: §1 · pp. 1–2

2.1 Definition of DisC Diversity

• Each object must be covered by a selected object within radius r, while selected objects must be more than r apart.The paper calls such a set an r-DisC diverse subset and seeks one with minimum size.Source: §2.1 · p. 2

2.2 Graph Representation and NP-hardness

• Minimum r-DisC subset selection is equivalent to finding a minimum independent dominating set in the graph connecting objects within distance r.For Euclidean distances, this graph is a unit disk graph, and the problem is NP-hard even for unit disk graphs.Source: §2.2 · p. 3

2.3 Computing DisC Diverse Objects

• Basic-DisC repeatedly selects an arbitrary uncovered object and marks its neighbors covered, producing a valid but not necessarily minimum subset.The produced set is a maximal independent set, which is also dominating.Source: §2.3 · p. 3, §2.2 · p. 3
• Any r-DisC diverse subset is at most B times larger than a minimum subset, where B is the maximum number of independent neighbors of any object.For Euclidean distance in two dimensions, each object has at most 5 mutually independent neighbors; for Manhattan distance in two dimensions, the bound is 7.Source: §2.3 · pp. 3–4
• The paper provides theoretical size bounds for its DisC-diversification heuristics and considers bounds for particular distance metrics and dimensions.The bound B depends on the distance metric and data dimensionality.Source: §2.3 · pp. 3–4
• Greedy-DisC chooses the white object with the most white neighbors, whereas Greedy-C may also choose grey objects to cover more uncovered objects.Greedy-C relaxes dissimilarity and produces an r-C subset at most ln ∆ times larger than the minimum r-DisC subset, where ∆ is the maximum number of neighbors.Source: §2.3 · p. 4

3. ADAPTIVE DIVERSIFICATION

• Changing the radius can change the DisC subset non-monotonically, so an existing subset may not contain or be contained in a valid subset at the new radius.For zooming in, the new subset can be built as a superset; for zooming out, no subset of the old solution may be valid.Source: §3 · p. 5

3.1 Incremental Zooming-in

• Zooming-in keeps the existing representatives and adds eligible objects to cover newly uncovered areas at the smaller radius.Zoom-In adds candidates arbitrarily, while Greedy-Zoom-In selects the candidate covering the largest number of uncovered objects; the size increase is expected to be smaller in practice than the theoretical bound.Source: §3.1 · p. 5

3.2 Incremental Zooming-out

• Zooming-out uses two passes: remove old representatives that become too close at the larger radius, then add objects to cover resulting gaps.Greedy-Zoom-Out has variants that aim to reduce additions or maximize the overlap with the old subset.Source: §3.2 · p. 5
• For zooming-out, preserving old representatives does not guarantee that the new solution will be smaller.The authors note there is no theoretical guarantee of a size reduction when adapting to a larger radius while maintaining some common objects.Source: §3.2 · pp. 5–6

4. COMPARISON WITH OTHER MODELS

• Unlike MaxMin and MaxSum, which maximize pairwise-distance objectives, DisC selects a covering subset without requiring its size as an input.For a fixed subset size k, the paper proves the optimal MaxMin distance λ* is at most 3λ, where λ is the DisC subset's minimum pairwise distance.Source: §4 · p. 6
• DisC gives priority to dense areas and represents them better than MaxMin, which can omit dense cluster centers while seeking widely separated objects.MaxSum tends toward dataset outskirts, and k-medoids toward central points, leaving some areas uncovered.Source: §4 · pp. 6–7
• MaxSum and k-medoids may leave dataset areas uncovered, whereas DisC aims to cover the whole dataset, including distant objects.MaxSum tends to select outskirts and k-medoids central points; MaxMin performs better at coverage but can miss dense areas.Source: §4 · pp. 6–7
• For the reported example, r-C diversity selects one fewer object than DisC, but its selected objects are less widely spread.The example uses k = 15 for r = 0.7 when setting the comparison methods' k to the DisC solution size.Source: §4 · pp. 6–7

5. IMPLEMENTATION

• The M-tree indexes metric-space objects in a balanced tree whose pivot-centered covering balls bound the objects in each subtree.Its range queries locate neighbors, a central operation in computing DisC diverse subsets.Source: §5 · p. 7

5.1 Computing Diverse Subsets

• Basic-DisC traverses leaf objects, selecting a white object and coloring its neighbors grey; pruning skips tree nodes that contain no white objects.The Greedy-DisC variations select the white object with the largest white neighborhood and update neighborhood sizes; computing those sizes during tree construction reduces node accesses by up to 45%.Source: §5.1 · p. 7
• Fast-C uses bottom-up range queries that stop at a grey internal node, which can miss distant neighbors and produce larger results.With small tree overlap, the authors expect the number of missed neighbors to be small.Source: §5.1 · pp. 7–8

5.2 Adapting the Radius

• For zooming-in, the algorithms preserve black objects and retain grey objects only while they remain covered at the smaller radius; newly uncovered objects can enter the subset.Zoom-In makes one leaf pass, while Greedy-Zoom-In maintains and sorts a structure of uncovered white objects by neighborhood size.Source: §5.2 · p. 8
• Zooming-in stores each object's distance to its closest black neighbor so coverage can be checked at a smaller radius.Because construction-time pruning interferes with computing these distances, a post-processing step is needed.Source: §5.2 · p. 8
• Zooming-out uses sorted structures to process red and then white objects, while local zooming-in runs on the selected object's neighborhood.The reported procedure for local zooming-in takes N_r(p_i) rather than all of P as input.Source: §5.2 · p. 8

6. EXPERIMENTAL EVALUATION

• The experiments use normalized synthetic and real datasets, with Euclidean distance for synthetic data and Cities, and Hamming distance for categorical Cameras attributes.The real datasets comprise 5,922 Greek cities and villages and 579 digital cameras with seven characteristics.Source: §6 · p. 8
• Grey-Greedy-DisC finds smaller subsets than Basic-DisC but costs more, while Greedy-C has similar subset sizes to Grey-Greedy-DisC.Pruning saves up to 50% of node accesses for small radii; Fast-C uses up to 30% fewer accesses than Greedy-C but produces similar-sized solutions with a larger percentage of independent objects.Source: §6 · pp. 8, 10, Figure 7 · p. 9, Figure 8 · p. 9
• White-Greedy-DisC performs well on clustered data as radius increases, and lazy variations reduce computation at the cost of slightly larger subsets.The evaluation compares these variants with Grey-Greedy-DisC using node accesses and solution size.Source: Figure 8 · p. 9, §6 · p. 10, Table 3 · p. 10
• Increasing dimensionality selects more objects as diverse because higher-dimensional space becomes sparser.Computational cost can vary with dimensionality because it depends on the cost of computing neighborhood sizes for grey objects.Source: Figure 9 · p. 9, §6 · p. 10
• For uniform data, a higher M-tree fat-factor leads to more node accesses for the same solution; this effect is not seen in clustered data.The comparison uses uniform and clustered two-dimensional datasets of cardinality 10,000; increasing node capacity also reduced computational cost by almost 45%.Source: §6 · p. 11, Figure 10 · p. 11
• Zooming-in heuristics produce solution sizes similar to Greedy-DisC in most cases, at lower computational cost, and yield adapted sets closer to the previous solution than recomputing from scratch.Their Jaccard distance from the previous solution is much smaller than that of a new Greedy-DisC solution at the smaller radius.Source: §6 · p. 11, Figure 13 · p. 11
• For zooming-out, Greedy-Zoom-Out(a) achieves solution sizes similar to Greedy-Zoom-Out(c) at much lower computational cost; the non-greedy heuristic is cheapest.Greedy-Zoom-Out(c) yields the smallest adapted subsets, but its cost generally exceeds computing a new solution from scratch; all zooming-out variants have lower Jaccard distances to the prior solution than Greedy-DisC.Source: §6 · p. 11, Figure 14 · p. 12, Figure 15 · p. 12

7. RELATED WORK

• Similarity-based MaxMin and MaxSum methods optimize pairwise distances, while novelty and semantic-coverage methods commonly rank objects by scores.DisC instead treats the result as a whole and selects a subset that fully covers it.Source: §7 · p. 12
• Nearest-neighbor diversification selects k close but attribute-different neighbors of one query object, whereas DisC seeks an independent, covering subset of the whole dataset.The cited approach is.Source: §7 · p. 12
• K-medoids can provide representative objects but may fail to cover all available space; priority medoids add a sense of relevance.The paper distinguishes its goal of covering the whole dataset from representative subsets that may omit outliers.Source: §7 · p. 12
• The minimum independent dominating set formulation is equivalent to minimum r-DisC diversity and has strong negative approximation results in general graphs.The paper focuses on efficiently computing small, non-minimum subsets rather than polynomial approximation bounds.Source: §7 · p. 12

• An r-DisC subset covers each result object through similarity while keeping selected objects mutually dissimilar, and radius r controls diversification.Source: §8 · pp. 12–13
• Minimum r-DisC diverse subset selection is NP-hard, so the paper provides approximation heuristics, incremental zooming algorithms, and theoretical bounds.Source: §8 · p. 13
• Future directions include relevance-weighted subsets, object-specific radii, alternative data structures, and online algorithms.Source: §8 · p. 13

• In the Euclidean proof, independent neighbors must be separated by angles greater than π/4, limiting a point to at most 7 such neighbors.Source: Appendix · pp. 13–14
• Greedy-DS charges covered nodes by degree-based fractions, bounding the cost for each optimal star by ln ∆.Source: Appendix · p. 14
• The Euclidean annulus proof partitions the region between radii r1 and r2 and uses angular separation to bound independent nodes in each annulus.Source: Appendix · p. 14
• For Manhattan distance, the proof partitions the area into annuli and counts 4(2i + 1) independent neighbors in annulus i.Source: Appendix · p. 14