Embedding and similarity search for point sets under translation

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. 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(log² n).

REFERENCES

• 1: Helmut Alt , Oswin Aichholzer , Günter Rote, Matching shapes with a reference point, Proceedings of the tenth annual symposium on Computational geometry, p.85-92, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177555]
• 2: H. Alt and L. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In Handbook of Computational Geometry, pages 121--153. 1999.
• 3: M. Boutin and G. Kemper. Which point configurations are determined by the distribution of their pairwise distances? Int. J. Comput. Geometry Appl., 17(1):31--44, 2007.
• 4: L. Carter and M.N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci., 18(2):143--154, 1979.
• 5: Fang-Hsuan Cheng, Point pattern matching algorithm invariant to geometrical transformation and distortion, Pattern Recognition Letters, v.17 n.14, p.1429-1435, Dec. 30, 1996 [doi>10.1016/S0167-8655(96)00115-8]
• 6: Scott Cohen , Leonidas Guibas, The Earth Mover's Distance under Transformation Sets, Proceedings of the International Conference on Computer Vision-Volume 2, p.1076, September 20-25, 1999
• 7: Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, ACM Transactions on Algorithms (TALG), v.3 n.1, February 2007 [doi>10.1145/1186810.1186812]
• 8: Tamara Dakic , Arvind Gupta, On the turnpike problem, 2000
• 9: Oded Goldreich , Avi Wigderson, Tiny families of functions with random properties: a quality-size trade-off for hashing, Random Structures & Algorithms, v.11 n.4, p.315-343, Dec. 1997
• 10: W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58:13--30, 1963.
• 11: D. P. Huttenlocher , G. A. Klanderman , W. A. Rucklidge, Comparing Images Using the Hausdorff Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.850-863, September 1993 [doi>10.1109/34.232073]
• 12: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 13: P. Indyk and N. Thaper. Fast image retrieval via embeddings. In 3rd Int'l Workshop on Stat. and Comput. Theories of Vision, 2003.
• 14: Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
• 15: Haibin Ling , David W. Jacobs, Deformation Invariant Image Matching, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1466-1473, October 17-20, 2005 [doi>10.1109/ICCV.2005.67]
• 16: J. Rosenblatt and P. Seymour. The structure of homometric sets. In SIAM J. Alg. Disc. Methods, volume 3,3, pages 343--350, 1982.
• 17: B. Rosser. Explicit bounds for some functions of prime numbers. Amer. J. Mathematics, 63(1):211--232, 1941.
• 18: Steven S. Skiena , Warren D. Smith , Paul Lemke, Reconstructing sets from interpoint distances (extended abstract), Proceedings of the sixth annual symposium on Computational geometry, p.332-339, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98598]
• 19: Zhe Wang , Wei Dong , William Josephson , Qin Lv , Moses Charikar , Kai Li, Sizing sketches: a rank-based analysis for similarity search, ACM SIGMETRICS Performance Evaluation Review, v.35 n.1, June 2007
• 20: Haim J. Wolfson , Isidore Rigoutsos, Geometric Hashing: An Overview, IEEE Computational Science & Engineering, v.4 n.4, p.10-21, October 1997 [doi>10.1109/99.641604]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

General Terms:
Algorithms, Theory

Keywords:
embedding, point pattern matching, randomized algorithms, similarity search