Guangyi Zhang

We propose a single-pass streaming algorithm to find personalized high-quality tuples among a database of n d-dimension tuples by adaptively making O(log n) pairwise comparisons. This is the first non-trivial worst-case guarantee for more than a decade!

This is a continuation of our previous DAMI '22 paper. We study the problem of ranking with multiple submodular functions in two different streaming settings, item-arriving and function-arriving settings. We also propose multiple novel applications for them.

In a streaming setting, how to maximize a non-decreasing submodular function in the presence of unexpected item deletion? Remembering all items and re-computing a new solution would help, but can we do better? We show that it suffices to remember a small deletion-robust coreset, and we are the first to find such a coreset with the (asymptotically) smallest possible size. For a deletion of d items, the coreset size is only O(d).

Do popular greedy algorithms such as C4.5 and CART produce "small" and more interpretable trees? We prove such a complexity guarantee if the greedy algorithm is guided by a regularized impurity function.

How to find a ranking of items that simultaneously maximizes a sum of multiple non-decreasing submodular functions, each of which is associated with a different budget? We devise a novel 4-approximation algorithm that returns the best between a greedy solution and a dynamic program.

How to find a set of decision rules that "overlap" less, so that the classification decision made on each example is unambiguous? Try the maximum-diversity approach proposed by us, which can be optimized provably.

We study the classic Max-Sum diversification problem over (potentially overlapping) clustered input. The goal is to maximize the sum of intra-cluster diversity. Existing algorithms fall short and we propose a novel 6-approximation algorithm.