Pattern masking for dictionary matching: theory and practice

DOI10.1007/S00453-024-01213-8MaRDI QIDQ6547212zbMATH OpenFDO

Authors Panagiotis Charalampopoulos, Huiping Chen, Peter Christen, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski

Publication date 30 May 2024

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-024-01213-8

zbMATH Keywords

dictionary matchingquery term droppingrecord linkagestring algorithmswildcards

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Cites work

• An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence
• Cell-probe lower bounds for the partial match problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Compressed indexes for approximate string matching
• Compressed string dictionary search with edit distance one
• Data Quality and Record Linkage Techniques
• Data structure lower bounds for document indexing problems
• Dictionary Look-Up with One Error
• Dictionary matching and indexing with errors and don't cares
• Efficient string matching
• Faster and Space-Optimal Edit Distance “1” Dictionary
• Higher lower bounds for near-neighbor and further rich problems
• scientific article; zbMATH DE number 2086643 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 7788370 (Why is no real title available?)
• If the current clique algorithms are optimal, so is Valiant's parser
• Improved bounds for dictionary look-up with one error
• Less space: indexing for queries with wildcards
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Lower bounds for high dimensional nearest neighbor search and related problems
• Lower bounds for text indexing with mismatches and differences
• Masking patterns in sequences: A new class of motif discovery with don't cares
• Mathematical Foundations of Computer Science 2003
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• Motif trie: an efficient text index for pattern discovery with don't cares
• On data structures and asymmetric communication complexity
• On some fine-grained questions in algorithms and complexity
• On the complexity of k-SAT
• Parameterized algorithms
• Partial-Match Retrieval Algorithms
• Pattern masking for dictionary matching
• Powers of tensors and fast matrix multiplication
• Pseudorandom generators with long stretch and low locality from random local one-way functions
• Reducibility among combinatorial problems
• Space-efficient string indexing for wildcard pattern matching
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Strong computational lower bounds via parameterized complexity
• Suffix tree characterization of maximal motifs in biological sequences
• The complexity of satisfiability of small depth circuits
• The densest k-subhypergraph problem
• Tight hardness for shortest cycles and paths in sparse graphs
• Unifying the landscape of cell-probe lower bounds
• Weighted ancestors in suffix trees

This page was built for publication: Pattern masking for dictionary matching: theory and practice

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