Efficient algorithms for the order preserving pattern matching problem

DOI10.1007/978-3-319-41168-2_16MaRDI QIDQ2830069zbMATH OpenOpenAlexFDO

Authors Simone Faro, M. Oğuzhan Külekci

Publication date 9 November 2016

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.04001

zbMATH Keywords

approximate text analysisexperimental algorithmsfiltering algorithmstext processing

Mathematics Subject Classification ID

Computing methodologies for text processing; mathematical typography (68U15) Algorithms on strings (68W32)

Abstract: Given a pattern x of length m and a text y of length n, both over an ordered alphabet, the order-preserving pattern matching problem consists in finding all substrings of the text with the same relative order as the pattern. It is an approximate variant of the well known exact pattern matching problem which has gained attention in recent years. This interesting problem finds applications in a lot of fields as time series analysis, like share prices on stock markets, weather data analysis or to musical melody matching. In this paper we present two new filtering approaches which turn out to be much more effective in practice than the previously presented methods. From our experimental results it turns out that our proposed solutions are up to 2 times faster than the previous solutions reducing the number of false positives up to 99%

Recommendations

• The order-preserving pattern matching problem in practice
• Fast order-preserving pattern matching
• A fast algorithm for order-preserving pattern matching
• Fast multiple order-preserving matching algorithms
• A filtration method for order-preserving matching

Cites work

• A fast string searching algorithm
• A filtration method for order-preserving matching
• A linear time algorithm for consecutive permutation pattern matching
• Efficient algorithms for the order preserving pattern matching problem
• Fast order-preserving pattern matching
• Fast Pattern Matching in Strings
• Order-preserving matching
• Single and multiple consecutive permutation motif search

Cited in

(19)

• Order-preserving pattern matching indeterminate strings
• String periods in the order-preserving model
• The order-preserving pattern matching problem in practice
• Order-preserving matching
• Order-preserving pattern matching with scaling
• Fast multiple order-preserving matching algorithms
• Efficient algorithms for the order preserving pattern matching problem
• Fast order-preserving pattern matching
• Order-preserving indexing
• Parallel duel-and-sweep algorithm for the order-preserving pattern matching
• String Periods in the Order-Preserving Model
• scientific article; zbMATH DE number 176147 (Why is no real title available?)
• A fast algorithm for order-preserving pattern matching
• An encoding for order-preserving matching
• Duel and sweep algorithm for order-preserving pattern matching
• Order-preserving pattern matching indeterminate strings
• Order preserving pattern matching on trees and DAGs
• Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm
• A filtration method for order-preserving matching

This page was built for publication: Efficient algorithms for the order preserving pattern matching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830069)