TY - JOUR

T1 - One-dimensional approximate point set pattern matching with L p-norm

AU - Wang, Hung Lung

AU - Chen, Kuan Yu

N1 - Funding Information:
The authors would like to thank Prof. Kun-Mao Chao for helpful comments. The anonymous referee also provided several helpful suggestions. Kuan-Yu Chen and Hung-Lung Wang were supported in part by NSC grants 98-2221-E-002-081-MY3 and 99-2115-M-141-003-MY2 , respectively, from the National Science Council, Taiwan .

PY - 2014/2/13

Y1 - 2014/2/13

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 pattern matching problem proposed in [19]. We generalize the measure between approximate matches from L1-norm to Lp-norm. More specifically, what requested is an optimal match which minimizes the Lp-norm of the difference vector (| p2-p1-(t2′-t1′)|,|p3- p2-(t3′-t2′)|,.,|Pm-pm-1- (tm′-tm-1′)|), where p1,p2,.,Pm is the pattern and t1′,t2′,.,tm′ is a subsequence of the text. For p→∞, we propose an O(mn)-time algorithm, where m and n denote the lengths of the pattern and the text, respectively. For arbitrary p<∞, we propose an algorithm which runs in O(mnT(p)) time, 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 pattern matching problem proposed in [19]. We generalize the measure between approximate matches from L1-norm to Lp-norm. More specifically, what requested is an optimal match which minimizes the Lp-norm of the difference vector (| p2-p1-(t2′-t1′)|,|p3- p2-(t3′-t2′)|,.,|Pm-pm-1- (tm′-tm-1′)|), where p1,p2,.,Pm is the pattern and t1′,t2′,.,tm′ is a subsequence of the text. For p→∞, we propose an O(mn)-time algorithm, where m and n denote the lengths of the pattern and the text, respectively. For arbitrary p<∞, we propose an algorithm which runs in O(mnT(p)) time, 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=84892804025&partnerID=8YFLogxK

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

U2 - 10.1016/j.tcs.2013.11.022

DO - 10.1016/j.tcs.2013.11.022

M3 - Article

AN - SCOPUS:84892804025

SN - 0304-3975

VL - 521

SP - 42

EP - 50

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -