Fast multiple order-preserving matching algorithms

DOI10.1007/978-3-319-29516-9_21MaRDI QIDQ2798237zbMATH OpenOpenAlexFDO

Authors Myoungji Han, Munseong Kang, Sukhyeun Cho, Geonmo Gu, J. S. Sim, Kunsoo Park

Publication date 4 April 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Abstract: Given a text $T$ and a pattern $P$, the order-preserving matching problem is to find all substrings in $T$ which have the same relative orders as $P$. Order-preserving matching has been an active research area since it was introduced by Kubica et al. cite{kubica2013linear} and Kim et al. cite{kim2014order}. In this paper we present two algorithms for the multiple order-preserving matching problem, one of which runs in sublinear time on average and the other in linear time on average. Both algorithms run much faster than the previous algorithms.

Recommendations

• A fast algorithm for order-preserving pattern matching
• Fast order-preserving pattern matching
• Order-preserving matching
• Efficient algorithms for the order preserving pattern matching problem
• Order-preserving indexing

Cited in

(17)

• Fast algorithms for single and multiple pattern Cartesian tree matching
• String periods in the order-preserving model
• On representations of ternary order relations in numeric strings
• Order-preserving matching
• Order-preserving pattern matching with scaling
• Efficient algorithms for the order preserving pattern matching problem
• Fast order-preserving pattern matching
• Single and multiple consecutive permutation motif search
• Order-preserving pattern matching with \(k\) mismatches
• Parallel duel-and-sweep algorithm for the order-preserving pattern matching
• scientific article; zbMATH DE number 5540281 (Why is no real title available?)
• A fast algorithm for order-preserving pattern matching
• An encoding for order-preserving matching
• Order preserving pattern matching on trees and DAGs
• Order-preserving pattern matching with \(k\) mismatches
• A filtration method for order-preserving matching
• Fast profile matching algorithms - A survey

This page was built for publication: Fast multiple order-preserving matching algorithms

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