Approximate point set pattern matching with Lp-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 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.

原文英語
主出版物標題String Processing and Information Retrieval - 18th International Symposium, SPIRE 2011, Proceedings
頁面81-86
頁數6
DOIs
出版狀態已發佈 - 2011
對外發佈
事件18th International Symposium on String Processing and Information Retrieval, SPIRE 2011 - Pisa, 意大利
持續時間: 2011 10月 172011 10月 21

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
7024 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

會議

會議18th International Symposium on String Processing and Information Retrieval, SPIRE 2011
國家/地區意大利
城市Pisa
期間2011/10/172011/10/21

ASJC Scopus subject areas

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

指紋

深入研究「Approximate point set pattern matching with Lp-norm」主題。共同形成了獨特的指紋。

引用此