Approximate point set pattern matching with Lp-norm

Hung Lung Wang*, Kuan Yu Chen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Given two sets of points, the text and the pattern, determining whether the pattern "appears" in the text is modeled as the point set pattern matching problem. Applications usually ask for not only exact matches between these two sets, but also approximate matches. In this paper, we investigate a one-dimensional approximate point set matching problem proposed in [T. Suga and S. Shimozono, Approximate point set pattern matching on sequences and planes, CPM'04]. What requested is an optimal match which minimizes the L p -norm of the difference vector (|p2 - p1 - (t′2 - t′1)|, |p3 - p2 - (t′3 - t′2)|,..., |p m - p m - 1 - (t′m - t′m - 1)|), where p1, p2,..., pm is the pattern and t′1, t′2,..., t′m is a subsequence of the text. For p → ∞, the proposed algorithm is of time complexity O(mn), where m and n denote the lengths of the pattern and the text, respectively. For arbitrary p < ∞, the time complexity is O(mnT(p)), where T(p) is the time of evaluating xp for x ∈ R.

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 18th International Symposium, SPIRE 2011, Proceedings
Number of pages6
Publication statusPublished - 2011
Externally publishedYes
Event18th International Symposium on String Processing and Information Retrieval, SPIRE 2011 - Pisa, Italy
Duration: 2011 Oct 172011 Oct 21

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7024 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th International Symposium on String Processing and Information Retrieval, SPIRE 2011


  • L -norm
  • dynamic programming
  • point set pattern matching

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Approximate point set pattern matching with Lp-norm'. Together they form a unique fingerprint.

Cite this