What is it about?

Many real-world problems can be formulated as the alignment between two geometric patterns. However, in the alignment research of high dimension patterns, most existing approaches are still rather limited due to the issue of high computational complexities. We propose an effective framework to compress the geometric patterns for high dimension patterns, which can apply the existing alignment algorithms and reduce the time complexity.

Featured Image

Why is it important?

Most existing approaches about alignments focus on 2D or 3D patterns, which suffer from high computational complexities for their extensions of high dimensional geometric patterns. In our observation, high dimensional data often has a low intrinsic dimension. Based on this observation, our framework can compress the patterns to reduce the time of running alignment algorithms, which can achieve similar qualities. Also, we extend our work for solving the robust alignment problem of partial matching between two patterns.


The alignment of high dimensional patterns often emerges in the fields of machine learning and bioinformatics. This work mainly solves the computational complexities in high dimensional patterns, which helps a lot for matching problems on these fields.

Wenjie Liu
University of Science and Technology of China

Read the Original

This page is a summary of: A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignment, ACM Journal of Experimental Algorithmics, June 2023, ACM (Association for Computing Machinery), DOI: 10.1145/3604910.
You can read the full text:



The following have contributed to this page