TY - CONF
T1 - Embedding and similarity search for point sets under translation
T2 - Proceedings of the twenty-fourth annual symposium on Computational geometry
Y1 - 2008
A1 - Cho,Minkyoung
A1 - Mount, Dave
KW - EMBEDDING
KW - point pattern matching
KW - randomized algorithms
KW - Similarity Search
AB - 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. We define the distance between any two point sets 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. We assume that a large database of point sets is 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 randomized 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).
JA - Proceedings of the twenty-fourth annual symposium on Computational geometry
T3 - SCG '08
PB - ACM
CY - New York, NY, USA
SN - 978-1-60558-071-5
UR - http://doi.acm.org/10.1145/1377676.1377731
M3 - 10.1145/1377676.1377731
ER -