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
- 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 2-dimensional approximate matching of half-rectangular figures
- EFFICIENT ALGORITHMS FOR (δ,γ,α) AND (δ, kΔ, α)-MATCHING
- Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances
- Experimental and Efficient Algorithms
- Function Matching
- Generalized function matching
- scientific article; zbMATH DE number 1142294 (Why is no real title available?)
- scientific article; zbMATH DE number 2087053 (Why is no real title available?)
- 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
(44)- An \(O(n^2\log m)\)-time algorithm for the boxed-mesh permutation pattern matching problem
- Order-preserving pattern matching indeterminate strings
- Position heaps for Cartesian-tree matching on strings and tries
- Finding patterns and periods in Cartesian tree matching
- Fast algorithms for single and multiple pattern Cartesian tree matching
- A framework for designing space-efficient dictionaries for parameterized and order-preserving matching
- String periods in the order-preserving model
- The order-preserving pattern matching problem in practice
- On representations of ternary order relations in numeric strings
- 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
- Improved algorithms for the boxed-mesh permutation pattern matching problem
- Order-preserving indexing
- Order-preserving pattern matching with \(k\) mismatches
- Longest common subsequence in at least k length order-isomorphic substrings
- Maximum number of distinct and nonequivalent nonstandard squares in a word
- Parallel duel-and-sweep algorithm for the order-preserving pattern matching
- String Periods in the Order-Preserving Model
- Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
- A fast algorithm for order-preserving pattern matching
- Generalized pattern matching and periodicity under substring consistent equivalence relations
- Sufficient conditions for efficient indexing under different matchings
- Cartesian Tree Matching and Indexing
- An encoding for order-preserving matching
- Order-preserving pattern matching indeterminate strings
- Order preserving pattern matching on trees and DAGs
- Fast Cartesian tree matching
- Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm
- On the complexity of indeterminate strings matching
- Approximate Cartesian tree pattern matching
- Computing maximal palindromes in non-standard matching models
- The longest wave subsequence problem: generalizations of the longest increasing subsequence problem
- Computing longest common subsequence under Cartesian-tree matching model
- Computing maximal palindromes in non-standard matching models
- Approximate Cartesian tree pattern matching
- Subsequence matching and LCS under Cartesian-tree equivalence
- The ceBWT index: an index for circular Cartesian tree matching on multiple texts
- LF successor: compact space indexing for order-isomorphic pattern matching
- Approximate Cartesian tree matching with one difference
- Extending the Burrows-Wheeler transform for Cartesian tree matching and constructing it
- Fast computation of k-runs, parameterized squares, and other generalised squares
- A filtration method for order-preserving matching
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)
