TY - GEN

T1 - Approximate point set pattern matching with Lp-norm

AU - Wang, Hung Lung

AU - Chen, Kuan Yu

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - dynamic programming

KW - L -norm

KW - point set pattern matching

UR - http://www.scopus.com/inward/record.url?scp=80053955464&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80053955464&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-24583-1_9

DO - 10.1007/978-3-642-24583-1_9

M3 - Conference contribution

AN - SCOPUS:80053955464

SN - 9783642245824

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 81

EP - 86

BT - String Processing and Information Retrieval - 18th International Symposium, SPIRE 2011, Proceedings

T2 - 18th International Symposium on String Processing and Information Retrieval, SPIRE 2011

Y2 - 17 October 2011 through 21 October 2011

ER -