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

Research in Algorithms for Geometric Pattern Matching

MIT2001-06

Start date: 11/2001

 Piotr Indyk
MIT LCS

Kiyoshi Shirayanagi
NTT

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

Publications

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

Proposals:

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