An encoding for order-preserving matching

DOI10.4230/LIPICS.ESA.2017.38MaRDI QIDQ5111725zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Giovanni Manzini, Rossano Venturini

Publication date 27 May 2020

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

zbMATH Keywords

pattern matchingorder-preserving matchingcompact data structuresencodings

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: Encoding data structures store enough information to answer the queries they are meant to support but not enough to recover their underlying datasets. In this paper we give the first encoding data structure for the challenging problem of order-preserving pattern matching. This problem was introduced only a few years ago but has already attracted significant attention because of its applications in data analysis. Two strings are said to be an order-preserving match if the {em relative order} of their characters is the same: e.g., $4,1,3,2$ and $10,3,7,5$ are an order-preserving match. We show how, given a string $S[\mathrm{1..}n]$ over an arbitrary alphabet and a constant $cgeq1$, we can build an $O(nloglogn)$-bit encoding such that later, given a pattern $P[\mathrm{1..}m]$ with $mleql{g}^{c}n$, we can return the number of order-preserving occurrences of $P$ in $S$ in $O(m)$ time. Within the same time bound we can also return the starting position of some order-preserving match for $P$ in $S$ (if such a match exists). We prove that our space bound is within a constant factor of optimal; our query time is optimal if $logsigma=Omega(logn)$. Our space bound contrasts with the $Omega(nlogn)$ bits needed in the worst case to store $S$ itself, an index for order-preserving pattern matching with no restrictions on the pattern length, or an index for standard pattern matching even with restrictions on the pattern length. Moreover, we can build our encoding knowing only how each character compares to $O(l{g}^{c}n)$ neighbouring characters.

Recommendations

• Order-preserving indexing
• Fast multiple order-preserving matching algorithms
• Order-preserving matching
• Efficient algorithms for the order preserving pattern matching problem
• The order-preserving pattern matching problem in practice

Cites work

• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• A fast algorithm for order-preserving pattern matching
• A filtration method for order-preserving matching
• A linear time algorithm for consecutive permutation pattern matching
• An experimental study of a compressed index
• Asymptotically optimal encodings for range selection
• Bit-Parallel Approximate Matching of Circular Strings with k Mismatches
• Combined data structure for previous- and next-smaller-values
• Compact encodings and indexes for the nearest larger neighbor problem
• Efficient Storage and Retrieval by Content and Address of Static Files
• Efficient algorithms for the order preserving pattern matching problem
• Encoding data structures
• Encoding range minima and range top-2 queries
• Encodings for range majority queries
• Encodings for range selection and top-\(k\) queries
• Encodings of range maximum-sum segment queries and applications
• Fast prefix search in little space, with applications
• Optimal encodings for range top-\(k\), selection, and min-max
• Order-preserving indexing
• Order-preserving matching
• Order-preserving pattern matching with \(k\) mismatches
• Parameterized pattern matching: Algorithms and applications
• Single and multiple consecutive permutation motif search
• Space efficient data structures for nearest larger neighbor
• Space-efficient substring occurrence estimation
• Theory and practice of monotone minimal perfect hashing
• pBWT: achieving succinct data structures for parameterized pattern matching and related problems

Cited in

(6)

• The effective entropy of next/previous larger/smaller value queries
• An encoding method for multifield sorting and indexing
• Wheeler graphs: a framework for BWT-based data structures
• String Periods in the Order-Preserving Model
• Order-preserving indexing
• String periods in the order-preserving model

This page was built for publication: An encoding for order-preserving matching

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