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

Hung Lung Wang*, Kuan Yu Chen


研究成果: 雜誌貢獻期刊論文同行評審


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.

頁(從 - 到)42-50
期刊Theoretical Computer Science
出版狀態已發佈 - 2014 2月 13

ASJC Scopus subject areas

  • 理論電腦科學
  • 電腦科學(全部)


深入研究「One-dimensional approximate point set pattern matching with L p-norm」主題。共同形成了獨特的指紋。