## Abstract

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 (|p_{2} - p_{1} - (t′_{2} - t′_{1})|, |p_{3} - p_{2} - (t′_{3} - t′_{2})|,..., |p _{m} - p _{m - 1} - (t′_{m} - t′_{m - 1})|), where p_{1}, p_{2},..., p_{m} 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 x^{p} for x ∈ R.

Original language | English |
---|---|

Title of host publication | String Processing and Information Retrieval - 18th International Symposium, SPIRE 2011, Proceedings |

Pages | 81-86 |

Number of pages | 6 |

DOIs | |

Publication status | Published - 2011 |

Externally published | Yes |

Event | 18th International Symposium on String Processing and Information Retrieval, SPIRE 2011 - Pisa, Italy Duration: 2011 Oct 17 → 2011 Oct 21 |

### Publication series

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

Volume | 7024 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

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

Country/Territory | Italy |

City | Pisa |

Period | 2011/10/17 → 2011/10/21 |

## Keywords

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

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint

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