Research Projects NTT-MIT Research Collaboration: a partnership in the future of communication and computation

Research in Algorithms for Geometric Pattern Matching


Start date: 11/2001

Piotr Indyk

Kiyoshi Shirayanagi

Project summary

The goal of this project is to develop efficient algorithms for a variety of geometric pattern matching problems.

Project description


Geometric pattern matching (GPM) involves searching for geometric patterns in a set of geometric structures. In the simplest setting, it reduces to computing similarity between two geometric objects (e.g., handwritten signatures, letters etc). More elaborate versions of the problem allow for searching for an occurrence of a pattern in a large scene, or computing the similarities between the pattern and many objects stored in a large database.

Geometric pattern matching is pervasive in many areas of computer science.It is of special importance in computer vision, where it directly corresponds to fundamental vision problems like object registration and recognition. It is also of importance in computational drug design and computational biology, where it has been successfully used for identification of drug molecules with similar shapes (and therefore similar chemical properties).

The goal of this project is to develop efficient algorithms for fundamental GPM problems.

Demos, movies and other examples

The principal investigators

Presentations and posters


P. Indyk, "Approximate Nearest Neighbor Algorithms for Frechet Distance via Product Metrics", ACM Symposium on Computational Geometry, 2002.

P. Indyk and N. Thaper, "Embedding Earth-Mover distance into the Euclidean space", manuscript, 2001.

Proposals and progress reports


NTT Bi-Annual Progress Report, July to December 2001:

NTT Bi-Annual Progress Report, January to June 2002:

NTT Bi-Annual Progress Report, July to December 2002:

For more information