Order-preserving matching
From MaRDI portal
Abstract: We introduce a new string matching problem called order-preserving matching on numeric strings where a pattern matches a text if the text contains a substring whose relative orders coincide with those of the pattern. Order-preserving matching is applicable to many scenarios such as stock price analysis and musical melody matching in which the order relations should be matched instead of the strings themselves. Solving order-preserving matching has to do with representations of order relations of a numeric string. We define prefix representation and nearest neighbor representation, which lead to efficient algorithms for order-preserving matching. We present efficient algorithms for single and multiple pattern cases. For the single pattern case, we give an O(n log m) time algorithm and optimize it further to obtain O(n + m log m) time. For the multiple pattern case, we give an O(n log m) time algorithm.
Recommendations
Cites work
- scientific article; zbMATH DE number 1142294 (Why is no real title available?)
- scientific article; zbMATH DE number 2087053 (Why is no real title available?)
- A fast string searching algorithm
- A theory of parameterized pattern matching
- Algorithms For Computing Approximate Repetitions In Musical Sequences
- Algorithms on Extended (δ, γ)-Matching
- Alphabet dependence in parameterized matching
- Approximate matching in the \(L_{\infty }\) metric
- Approximate string matching for music analysis
- Approximating general metric distances between a pattern and a text
- Combinatorial Pattern Matching
- Combinatorial Pattern Matching
- EFFICIENT ALGORITHMS FOR (δ,γ,α) AND (δ, kΔ, α)-MATCHING
- Efficient 2-dimensional approximate matching of half-rectangular figures
- Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances
- Experimental and Efficient Algorithms
- Function Matching
- Generalized function matching
- Introduction to algorithms.
- Jewels of Stringology
- Log-logarithmic worst-case range queries are possible in space theta(N)
- On special families of morphisms related to \(\delta \)-matching and don't care symbols
- Overlap matching.
- Pattern Matching with Swaps
- Preserving order in a forest in less than logarithmic time and linear space
Cited in
(31)- Fast algorithms for single and multiple pattern Cartesian tree matching
- Parallel duel-and-sweep algorithm for the order-preserving pattern matching
- Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
- An \(O(n^2\log m)\)-time algorithm for the boxed-mesh permutation pattern matching problem
- scientific article; zbMATH DE number 7559174 (Why is no real title available?)
- A fast algorithm for order-preserving pattern matching
- Improved algorithms for the boxed-mesh permutation pattern matching problem
- Efficient algorithms for the order preserving pattern matching problem
- Cartesian Tree Matching and Indexing
- Order preserving pattern matching on trees and DAGs
- Finding patterns and periods in Cartesian tree matching
- String Periods in the Order-Preserving Model
- A filtration method for order-preserving matching
- A framework for designing space-efficient dictionaries for parameterized and order-preserving matching
- Fast Cartesian tree matching
- Longest common subsequence in at least \(k\) length order-isomorphic substrings
- The order-preserving pattern matching problem in practice
- Order-preserving pattern matching with scaling
- Fast multiple order-preserving matching algorithms
- Maximum number of distinct and nonequivalent nonstandard squares in a word
- Order-preserving pattern matching indeterminate strings
- On representations of ternary order relations in numeric strings
- Order-preserving pattern matching indeterminate strings
- Generalized pattern matching and periodicity under substring consistent equivalence relations
- Order-preserving indexing
- Order-preserving pattern matching with \(k\) mismatches
- Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm
- An encoding for order-preserving matching
- Position heaps for Cartesian-tree matching on strings and tries
- Fast order-preserving pattern matching
- String periods in the order-preserving model
This page was built for publication: Order-preserving matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437748)
