Title: Embedding and Similarity Search for Point Sets under Translation

Speaker:  Dave Mount
University of Maryland

Date: Friday, August 15, 2008
Time 11:00-12:00PM
Venue: Room 3501, HKUST

Abstract:
Pattern matching in point sets is a well studied problem with numerous applications. 
We assume that the point sets may contain outliers (missing or spurious points) 
and are subject to an unknown translation.  The distance between any two point 
sets is defined to be the minimum size of their symmetric difference over all 
translations of one set relative to the other. We consider the problem in the 
context of similarity search. In particular, there is large database of point 
sets to be preprocessed, so that given any query point set, the closest matches 
in the database can be computed efficiently. Our approach is based on showing 
that there is a algorithm that computes a translation-invariant embedding of 
any point set of size at most n into the L_1 metric, so that with high probability, 
distances are subject to a distortion that is O(log2 n). The algorithm is randomized, 
and the distortion bounds holds with a probability bound that can be set by the user. 
(This is joint work with Minkyoung Cho.)