Efficient approximate and dynamic matching of patterns using a labeling paradigm

No abstract is available for this paper.

• Publication year

  1996

• Venue

  Proceedings of 37th Conference on Foundations of Computer Science

• Publication date

  1996-10-14

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1109/SFCS.1996.548491
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Introduction to parallel algorithms

  1998cited by this paper
• Optimal Parallel Suux Tree Construction

  1997cited by this paper
• Improved dynamic dictionary matching

  1995cited by this paper
• Optimal on-line search and sublinear time update in string matching

  1995cited by this paper
• Real-time pattern matching and quasi-real-time construction of suffix trees (preliminary version)

  1994cited by this paper
• Symmetry breaking for suffix tree construction

  1994influential reference
• String Searching Algorithms

  1994cited by this paper
• Optimal parallel suffix tree construction

  1994cited by this paper
• Dynamic Dictionary Matching

  1994cited by this paper
• An efficient algorithm for dynamic text indexing

  1994cited by this paper
• Suffix arrays: a new method for on-line string searches

  1993cited by this paper
• Efficient Randomized Dictionary Matching Algorithms (Extended Abstract)

  1992cited by this paper
• Introduction to Parallel Algorithms

  1992cited by this paper
• Adaptive dictionary matching

  1991cited by this paper
• Approximate string matching in sublinear expected time

  1990cited by this paper
• An Improved Algorithm for Approximate String Matching

  1989cited by this paper
• Fast Parallel and Serial Approximate String Matching

  1989cited by this paper
• Data structures and algorithms for approximate string matching

  1988cited by this paper
• Fast String Matching with k Differences

  1988cited by this paper
• Introducing efficient parallelism into approximate string matching and a new serial algorithm

  1986cited by this paper
• Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms

  1986cited by this paper
• Efficient string matching in the presence of errors

  1985cited by this paper
• Applying parallel computation algorithms in the design of serial algorithms

  1981cited by this paper
• The Theory and Computation of Evolutionary Distances: Pattern Recognition

  1980cited by this paper
• A fast string searching algorithm

  1977cited by this paper
• Fast Pattern Matching in Strings

  1977cited by this paper
• A Space-Economical Suffix Tree Construction Algorithm

  1976cited by this paper
• Efficient string matching

  1975cited by this paper
• Linear Pattern Matching Algorithms

  1973cited by this paper
• Rapid identification of repeated patterns in strings, trees and arrays

  1972cited by this paper

• Dynamic Pattern Matching with Wildcards

  2026cites this paper
• Time-Optimal Construction of String Synchronizing Sets

  2026cites this paper
• Text Indexing and Pattern Matching with Ephemeral Edits

  2025cites this paper
• LCPan: efficient variation graph construction using Locally Consistent Parsing.

  2025cites this paper
• Locally Consistent Parsing for Text Indexing in Small Space

  2025cites this paper
• Approximate Circular Pattern Matching Under Edit Distance

  2024cites this paper
• Efficient mapping of accurate long reads in minimizer space with mapquik

  2023cites this paper
• Nearly Optimal Internal Dictionary Matching

  2023cites this paper
• Dynamic suffix array with polylogarithmic queries and updates

  2022cites this paper
• CMIC: an efficient quality score compressor with random access functionality

  2022cites this paper
• Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices

  2022cites this paper
• mapquik: Efficient low-divergence mapping of long reads in minimizer space

  2022cites this paper
• Grammar Index By Induced Suffix Sorting

  2021cites this paper
• The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time

  2020cites this paper
• Detecting Pattern Efficiently with Don't Cares

  2020cites this paper
• Dynamic Longest Common Substring in Polylogarithmic Time

  2020cites this paper
• Update Query Time Trade-off for dynamic Suffix Arrays

  2020influential citation
• Technology dictates algorithms: recent developments in read alignment

  2020cites this paper
• Approximating text-to-pattern Hamming distances

  2020cites this paper
• Faster Approximate Pattern Matching: A Unified Approach

  2020cites this paper
• Dynamic and Internal Longest Common Substring

  2020cites this paper
• Dynamic Palindrome Detection

  2019cites this paper
• Dynamic Dictionary Matching in the Online Model

  2019influential citation
• Efficient data structures for internal queries in texts

  2019cites this paper
• Repetition Detection in a Dynamic String

  2019cites this paper
• supporting time-optimal queries with O ( log 2 n ) time for updates

  2019cites this paper
• Longest Common Substring Made Fully Dynamic

  2018cites this paper
• Compressed and Practical Data Structures for Strings

  2018cites this paper
• Locally Consistent Parsing for Text Indexing in Small Space

  2018cites this paper
• BdBG: a bucket-based method for compressing genome sequencing data with dynamic de Bruijn graphs

  2018cites this paper
• Searching for a Modified Pattern in a Changing Text

  2018cites this paper
• Compressed and efficient algorithms and data structures for strings

  2018cites this paper
• Algorithms for Next-Generation Sequencing Data

  2017influential citation
• Compressed Indexing with Signature Grammars

  2017cites this paper
• Designing small universal k-mer hitting sets for improved analysis of high-throughput sequencing

  2017cites this paper
• Novel Algorithms for Big Data Analytics

  2017cites this paper
• De Novo NGS Data Compression

  2017cites this paper
• Dynamic Alignment-Free and Reference-Free Read Compression

  2017cites this paper
• Efficient Index Maintenance Under Dynamic Genome Modification

  2016cites this paper
• A Survey on Data Compression Methods for Biological Sequences

  2016cites this paper
• Advances in high throughput DNA sequence data compression

  2016cites this paper
• Compact Universal k-mer Hitting Sets

  2016cites this paper
• Using Abstraction Methods to Improve String Matching Algorithms

  2016cites this paper
• Dynamic Index and LZ Factorization in Compressed Space

  2016cites this paper
• Dynamic index, LZ factorization, and LCE queries in compressed space

  2015cites this paper
• Light-weight reference-based compression of FASTQ data

  2015cites this paper
• Optimal Dynamic Strings

  2015cites this paper
• Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems

  2015cites this paper
• NRRC: A Non-referential Reads Compression Algorithm

  2015cites this paper
• High-throughput DNA sequence data compression

  2015cites this paper
• A Grouping Approach for Succinct Dynamic Dictionary Matching

  2015influential citation
• Language Edit Distance&Scored Parsing: Faster Algorithms&Connection to Fundamental Graph Problems

  2014cites this paper
• A New Linear-Time Dynamic Dictionary Matching Algorithm

  2014cites this paper
• An Improved Query Time for Succinct Dynamic Dictionary Matching

  2014influential citation
• Various Algorithms for High Throughput Sequencing

  2014cites this paper
• Compressive biological sequence analysis and archival in the era of high-throughput sequencing technologies

  2014cites this paper
• Hypertext Searching - A Survey

  2014cites this paper
• Language Edit Distance & Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms & Connection to Fundamental Graph Problems

  2014cites this paper
• Applying Agrep to r-NSA to solve multiple sequences approximate matching

  2014cites this paper
• Efficient algorithms for the compression of FASTQ files

  2014cites this paper
• The Dyck Language Edit Distance Problem in Near-Linear Time

  2014cites this paper
• Efficiently Computing Edit Distance to Dyck Language

  2013cites this paper
• Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to Online Indexing

  2013cites this paper
• Internal Pattern Matching Queries in a Text and Applications

  2013cites this paper
• Dynamic 2D Dictionary Matching in Small Space

  2013influential citation
• Boosting high throughput sequencing data compression algorithms using reordering

  2013cites this paper
• High-throughput DNA sequence data

  2013cites this paper
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares

  2012cites this paper
• Small-Space Dictionary Matching Dissertation Proposal

  2012cites this paper
• 2d dictionary matching in small space

  2012influential citation
• SCALCE: boosting sequence compression algorithms using locally consistent encoding

  2012cites this paper
• String Indexing for Patterns with Wildcards

  2011cites this paper
• ESP-index: A compressed index based on edit-sensitive parsing

  2011cites this paper
• Searching for Compact Hierarchical Structures in DNA by means of the Smallest Grammar Problem

  2011cites this paper
• The property suffix tree with dynamic properties

  2010cites this paper
• Indexing Textual Information

  2009cites this paper
• Efficient computations of ℓ[subscript 1] and ℓ[subscript ∞] rearrangement distances

  2009cites this paper
• Approximating edit distance in near-linear time

  2009cites this paper
• Efficient computations of l1 and l∞ rearrangement distances

  2009cites this paper
• Faster Approximate String Matching for Short Patterns

  2008cites this paper
• In-Place Update of Suffix Array while Recoding Words

  2008cites this paper
• An algorithmic perspective on problems in biological imaging

  2008cites this paper
• Edit Distance Under Block Operations

  2008cites this paper
• Compressed Index for Dictionary Matching

  2008cites this paper
• Dictionary Matching and Indexing (Exact and with Errors)

  2008cites this paper
• Parallel Algorithms on Strings

  2007cites this paper
• Efficient search in large textual collections with redundancy

  2007cites this paper
• Compressed indexes for dynamic text collections

  2007influential citation
• Grid's confidential outsourcing of string matching

  2007cites this paper
• Dynamic dictionary matching using inverted lists

  2007cites this paper
• Pattern Matching Algorithms with Don't Cares

  2007cites this paper
• Ìó Ôôö Ò Èöó Blockinº Øø Ëë¸ëëëööö Ù Blockinò¸öññòý¸¾¼¼¼

  2007cites this paper
• Secure outsourcing of DNA sequences comparisons in a Grid environment

  2007cites this paper
• Efficient Computations of l1 and linfinity Rearrangement Distances

  2007cites this paper
• Pattern matching with address errors: rearrangement distances

  2006cites this paper
• Property matching and weighted matching

  2006cites this paper
• Faster Algorithm of String Comparison

  2006cites this paper
• Finding Patterns with Variable Length Gaps or Don't Cares

  2006cites this paper
• Oblivious string embeddings and edit distance approximations

  2006cites this paper
• Asynchronous Pattern Matching

  2006cites this paper