pBWT: achieving succinct data structures for parameterized pattern matching and related problems

DOI10.1137/1.9781611974782.25MaRDI QIDQ4575762zbMATH OpenOpenAlexFDO

Authors Arnab Ganguly, Rahul Shah, Sharma V. Thankachan

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.25

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Recommendations

• Structural Pattern Matching - Succinctly.
• A framework for dynamic parameterized dictionary matching
• A framework for designing space-efficient dictionaries for parameterized and order-preserving matching
• Space-efficient dictionaries for parameterized and order-preserving pattern matching
• Geometric BWT: compressed text indexing via sparse suffixes and range searching

Cited in

(22)

• Wheeler graphs: a framework for BWT-based data structures
• On the complexity of recognizing Wheeler graphs
• A framework for designing space-efficient dictionaries for parameterized and order-preserving matching
• Simpler FM-index for parameterized string matching
• Succinct non-overlapping indexing
• A brief history of parameterized matching problems
• Geometric BWT: compressed text indexing via sparse suffixes and range searching
• Parameterized DAWGs: efficient constructions and bidirectional pattern searches
• The parameterized suffix tray
• Succinct indexes for circular patterns
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• An encoding for order-preserving matching
• Structural Pattern Matching - Succinctly.
• A framework for dynamic parameterized dictionary matching
• Space-efficient dictionaries for parameterized and order-preserving pattern matching
• Computing the parameterized Burrows-Wheeler transform online
• Direct linear time construction of parameterized suffix and LCP arrays for constant alphabets
• Data structures for SMEM-finding in the PBWT
• Breaking a barrier in constructing compact indexes for parameterized pattern matching
• Inverting parameterized Burrows-Wheeler transform
• LF successor: compact space indexing for order-isomorphic pattern matching
• Two-dimensional longest common extension queries in compact space

Describes a project that uses

Uses Software

• CLICS

This page was built for publication: pBWT: achieving succinct data structures for parameterized pattern matching and related problems

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