Summary
The study presents improved core-set construction algorithms for maximizing diversity under partition constraints.
Two diversity measures were considered: sum-of-pairwise distances and sum-of-nearest-neighbor distances.
The algorithms are validated through real-world application to time-sensitive message data, resulting in a 100x speedup and minor diversity loss while improving space usage in streaming settings.
Strengths
Algorithms 2, 3, and 4, despite their relative simplicity, provide significant insights, primarily stemming from the proofs of approximations related to their definitions.
These algorithms' straightforward yet effective design and the resultant analytical insights shed new light on the problem. These aspects, therefore, make these algorithms especially appealing to a broad research community. Conference attendees will find these insights valuable, sparking potential discussions around their contributions and their implications in the field.
Weaknesses
While the paper offers some contributions, its structure requires revision for improved clarity, particularly moving the detailed 'Overview of the Algorithms' from the first section to the respective sessions dealing with the algorithms and balancing the disproportionate length of the first section within the overall context.
The renaming of 'Diversity Maximization under Partition Constraints' to 'Fair Diversity Maximization' is somewhat perplexing. The 'fairness constraints' applied in this study do not differ significantly from the 'partition constraints' defined in the existing literature. Moreover, in other works (e.g., [22]), the term' fairness' is applied based on specific definitions like group fairness or statistical parity. The decision to redefine 'partition constraints' as' fairness constraints' without a clear distinction is somewhat confusing, making it more difficult to discern the precise contributions of this paper.
Still, regarding the use of "fairness constraints" throughout the paper, the paper presents two main experiments. The first involves grouping a dataset of messages by creation time to compute a diverse summary that favors recently over older messages. The second uses the method to control each genre's contribution to a movie recommendation system. However, neither of these experiments demonstrates the necessity of applying fairness constraints (as defined in the literature) to solve the proposed problem.
The GMM Algorithm, a fundamental building block of the method, must be correctly defined. Since it initially selects some arbitrary point as the first element of S, [11]'s definition is accurate. In fact, because S begins as an empty set, the execution of line 3 in the authors' definition is inconsistent.
The text contains some English usage errors that affect clarity. Specifically, the phrase "based on greedy" found in line 107 could benefit from a more explicit definition. The part containing "along the way" in line 101 is vague and could be replaced with a more descriptive phrase. Furthermore, key terminologies, such as the "aspect ratio" of the dataset mentioned in lines 9, 86, and 94, are misused or not sufficiently defined.
Some details of the experiments in the main text, such as the choice of 21,474 samples mentioned in line 294, appear arbitrary, and the rationale for their selection is buried in the appendix.
Finally, the paper would greatly benefit from maintaining consistent naming and notation across all sections, enhancing its comprehensibility and overall cohesiveness.
For example, the "div" definition in line 231 should use the same notation as in line 238; many references to core-set vs. coreset.
Questions
Section 1.3 defines the problem as selecting subsets S_i of k_i points from P_i to maximize div(S). However, the subsets S_i don't strictly contain k_i points in your final results. Instead, they include the core-set and the closest k_i points to each seed, effectively increasing the core-set size to k_i^2, as observed in the 'Core-set for SUM-PAIRWISE DIST' case. Could you please clarify how these results align with your original problem definition? Furthermore, could you please provide additional detail in your problem definition to help readers understand how the algorithm's results can serve as a potential solution to the problem?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The authors adequately addressed the limitations. There are no potential negative societal impacts from their work.