This project is for developing algorithmic solutions to three fundamental geometric problems arising in biomedical imaging applications: (1) Clustering Induced Voronoi Diagrams, (2) Earth Mover?s Distance Based Geometric Matching, and (3) Clustering Constrained Data without Locality Property. The first problem is for investigating a significant generalization of the fundamental geometric structure, Voronoi diagram, and is motivated by the biomedical problem of developing a mathematical model for understanding the immune system. The second problem is for studying the most generalized form of matching in geometric settings and is motivated by a medical application of matching images with different modalities. The third problem is for developing unified approach for a large class of constrained clustering problems, and is motivated by an image classification problem with a priori knowledge. 

Outcomes related to Intellectual Merits:

The PI of this project and his students have developed state-of-the-art solutions to each of the proposed problem. For the first problem, they have used the concept of joint influence to generalize Voronoi diagram, for the first time, from a distance-based to influence-based structure, and obtained efficient algorithms for constructing two types of diagrams called Clustering Induced Voronoi Diagrams (CIVD) and Influence-based Voronoi Diagrams (IVD) for ungrouped and grouped points, respectively. The associated joint influence techniques also enable them to achieve the best algorithms for several important problems, such as truth discovery, influence estimation, distributed and robust SVM, and fast pattern search. As by-products of these algorithms, a set of general techniques, such as Approximate Influence (AI) Decomposition, Range Cover, and Sum Query, were also obtained, which have the potential to be used for solving other problems. 

For the second problem, they have focused on computing earth mover?s distance under rigid transformation.  This is a longstanding open problem in the field of computational geometry. Based on a number of new techniques, they have achieved the first near optimal solution (FPTAS) for matching two sets of points in any fixed dimensional space. As a consequence of this breakthrough, they have also obtained the best solutions to several related problems, such as the alignment problem, and matching under other metrics and transformations, such as Hausdorff distance, similarity transformation, and affine transformation.

 For the third problem, they have obtained a unified framework called Peeling-and-Enclosing (PnE) for a large class of constrained clustering problems, where the constraints can be very general. This is a rather powerful technique as most of the clustering problems in real world applications are constrained in some ways. Their PnE technique is able to achieve near optimal ((1+epsilon)-approximation)) solution for each of them for two types of clustering, k-means clustering and k-median clustering. An important theoretical result from this framework is a Simplex Lemma which can be used as a general technique for many high dimensional problems.     

To obtain the aforementioned algorithms, they have also studied a number of related problems, such as Clustering-Based Collaborative Filtering, Random Gradient Descent Tree, Geometric Approach for Global Alignment of PPI Networks, Online and Distributed SVM, Large Scale Constrained Linear Regression, and Differentially Private Empirical Risk Minimization.
A number of quality guaranteed techniques have been obtained. 

All the designed algorithmic techniques have been disseminated through publications in peer-reviewed journals and conferences. Due to their fundamental nature, these algorithms have the potential to be used to solve various problems in computer science and other related areas.  

Outcomes related to Broader Impacts:

The obtained computer algorithms have been used to analyze several types of biomedical data. Particularly, they have used the obtained algorithms to analyze biomedical data related to skin cancer. This study aims to determine what kinds of mutations are likely caused by sun exposure and will eventually lead to skin cancer. Some interesting results have already been obtained which will be disseminated soon.

The CIVD technique has been used to solve an important truth discovery problem in data science and achieve the first quality guaranteed solution for two popular models of this problem. The obtained truth discovery algorithms have been used for analyzing teaching evaluation data in the PI?s department and thus brings positive impact to the quality of education. One of the truth discovery paper won the best paper award in the 24th International Computing and Combinatorics Conference (COCOON 2018). 

This project has provided educational and research opportunity to 9 PhD students (including 2 underrepresented female students). 6 of them have completed their doctoral dissertations. Three of them are now assistant professors in academia, including Michigan State University and Penn State University-Behrend. 

Last Modified: 01/02/2019
Modified by: Jinhui Xu