Order-preserving indexing

DOI10.1016/j.tcs.2015.06.050zbMath1345.68300OpenAlexW4297851495WikidataQ61677834 ScholiaQ61677834MaRDI QIDQ294954

Solon P. Pissis, Tomasz Kociumaka, Maxime Crochemore, Alessio Langiu, Costas S. Iliopoulos, Jakub Radoszewski, Marcin Kubica, Wojciech Rytter, Tomasz Walen

Publication date: 16 June 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.06.050

zbMATH Keywords

suffix treeorder-preserving indexingorder-preserving matching

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Algorithms on strings (68W32)

Related Items (13)

On representations of ternary order relations in numeric strings ⋮ Maximum number of distinct and nonequivalent nonstandard squares in a word ⋮ Position heaps for Cartesian-tree matching on strings and tries ⋮ String Periods in the Order-Preserving Model ⋮ Order-preserving pattern matching with scaling ⋮ Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings ⋮ Finding patterns and periods in Cartesian tree matching ⋮ Unnamed Item ⋮ String periods in the order-preserving model ⋮ Cartesian Tree Matching and Indexing ⋮ Searching Long Repeats in Streams ⋮ An Encoding for Order-Preserving Matching. ⋮ Structural Pattern Matching - Succinctly.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding pattern matchings for permutations
• Pattern matching for permutations
• A linear time algorithm for consecutive permutation pattern matching
• A fast algorithm for order-preserving pattern matching
• Stack sortable permutations
• Computing the longest previous factor
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Log-logarithmic worst-case range queries are possible in space theta(N)
• On-line construction of suffix trees
• Parameterized pattern matching: Algorithms and applications
• On-line construction of parameterized suffix trees for large alphabets
• Order-preserving matching
• Efficient Algorithms for the Order Preserving Pattern Matching Problem
• Single and Multiple Consecutive Permutation Motif Search
• Sorted Range Reporting
• Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word
• The computational landscape of permutation patterns
• Fast Algorithms for Finding Nearest Common Ancestors
• An O(n log n) algorithm for finding all repetitions in a string
• Dynamic ordered sets with exponential search trees
• Pattern Matching for 321-Avoiding Permutations
• Linear Algorithm for Data Compression via String Matching
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Faster Suffix Tree Construction with Missing Suffix Links
• Deterministic sorting in O(nloglogn) time and linear space
• Order-Preserving Pattern Matching with k Mismatches
• Wavelet Trees Meet Suffix Trees
• Finding small patterns in permutations in linear time
• Simple and flexible detection of contiguous repeats using a suffix tree

This page was built for publication: Order-preserving indexing