StringologyTimes

Papers for stringologist (2021)

Contents

ALENEX 2021

  1. A “Learned” Approach to Quicken and Compress Rank/Select Dictionaries.
  2. PFP Compressed Suffix Trees.

CIAA 2021

  1. Approximate Hashing for Bioinformatics.

CIAC 2021

  1. The Parameterized Suffix Tray.

COCOA 2021

  1. Succinct Data Structures for Series-Parallel, Block-Cactus and 3-Leaf Power Graphs.

CPM 2021

  1. A Compact Index for Cartesian Tree Matching.
  2. A Fast and Small Subsampled R-Index.
  3. A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs.
  4. AWLCO: All-Window Length Co-Occurrence.
  5. An Invertible Transform for Efficient String Matching in Labeled Digraphs.
  6. Compressed Weighted de Bruijn Graphs.
  7. Computing Covers of 2D-Strings.
  8. Computing Edit Distance (Invited Talk).
  9. Constructing Strings Avoiding Forbidden Substrings.
  10. Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time.
  11. Data Structures for Categorical Path Counting Queries.
  12. Disorders and Permutations.
  13. Efficient Algorithms for Counting Gapped Palindromes.
  14. Gapped Indexing for Consecutive Occurrences.
  15. Internal Shortest Absent Word Queries.
  16. On-Line Pattern Matching on D-Texts (Invited Talk).
  17. Optimal Completion and Comparison of Incomplete Phylogenetic Trees Under Robinson-Foulds Distance.
  18. Optimal Construction of Hierarchical Overlap Graphs.
  19. R-enum: Enumeration of Characteristic Substrings in BWT-runs Bounded Space.
  20. Ranking Bracelets in Polynomial Time.
  21. Repetitions in Strings: A “Constant” Problem (Invited Talk).
  22. String Sanitization Under Edit Distance: Improved and Generalized.
  23. The Longest Run Subsequence Problem: Further Complexity Results.
  24. The k-Mappability Problem Revisited.
  25. Weighted Ancestors in Suffix Trees Revisited.

DCC 2021

  1. A Disk-Based Index for Trajectories with an In-Memory Compressed Cache.
  2. A grammar compressor for collections of reads with applications to the construction of the BWT.
  3. Accelerating Knuth-Morris-Pratt String Matching over LZ77 Compressed Text.
  4. Approximate Hashing for Bioinformatics.
  5. Backward Weighted Coding.
  6. Compact Representation of Spatial Hierarchies and Topological Relationships.
  7. DZip: improved general-purpose loss less compression based on novel neural network modeling.
  8. Efficiently Merging r-indexes.
  9. End-to-End optimized image compression for machines, a study.
  10. Improved LZ77 Compression.
  11. Improving Run Length Encoding by Preprocessing.
  12. Neural Networks Optimally Compress the Sawbridge.
  13. On Elias-Fano for Rank Queries in FM-Indexes.
  14. On Random Editing in LZ-End.
  15. PHONI: Streamed Matching Statistics with Multi-Genome References.
  16. Parallel Processing of Grammar Compression.
  17. Smaller RLZ-Compressed Suffix Arrays.
  18. Succinct Data Structures for Small Clique-Width Graphs.
  19. Succinct representations of Intersection Graphs on a Circle.
  20. ndzip: A High-Throughput Parallel Lossless Compressor for Scientific Data.

DLT 2021

  1. Upper Bounds on Distinct Maximal (Sub-)Repetitions in Compressed Strings.
  2. Weighted Prefix Normal Words: Mind the Gap.

ESA 2021

  1. Bidirectional String Anchors: A New String Sampling Mechanism.
  2. Compression by Contracting Straight-Line Programs.
  3. Dynamic Colored Orthogonal Range Searching.
  4. Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing.
  5. Faster Algorithms for Longest Common Substring.
  6. Hypersuccinct Trees - New Universal Tree Source Codes for Optimal Compressed Tree Data Structures and Range Minima.
  7. Lyndon Words Accelerate Suffix Sorting.
  8. Minimum Common String Partition: Exact Algorithms.
  9. Space Efficient Two-Dimensional Orthogonal Colored Range Counting.

FOCS 2021

  1. Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance.
  2. Small-space and streaming pattern matching with $k$ edits.

ICALP 2021

  1. A Linear-Time n0.4-Approximation for Longest Common Subsequence.
  2. An Almost Optimal Edit Distance Oracle.
  3. Analysis of Smooth Heaps and Slim Heaps.
  4. Faster Algorithms for Bounded Tree Edit Distance.
  5. Fine-Grained Hardness for Edit Distance to a Fixed Sequence.
  6. Improved Approximation for Longest Common Subsequence over Small Alphabets.
  7. LF Successor: Compact Space Indexing for Order-Isomorphic Pattern Matching.
  8. Linear Time Runs Over General Ordered Alphabets.
  9. New Sublinear Algorithms and Lower Bounds for LIS Estimation.
  10. Optimal-Time Queries on BWT-Runs Compressed Indexes.
  11. Sorting Short Integers.
  12. Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence.

ISAAC 2021

  1. Algorithms and Complexity on Indexing Elastic Founder Graphs.
  2. Inverse Suffix Array Queries for 2-Dimensional Pattern Matching in Near-Compact Space.
  3. Pattern Masking for Dictionary Matching.
  4. Repetition- and Linearity-Aware Rank/Select Dictionaries.
  5. Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees.
  6. Streaming Pattern Matching (Invited Talk).

IWOCA 2021

  1. The Tandem Duplication Distance Problem Is Hard over Bounded Alphabets.

LATA 2021

  1. Cadences in Grammar-Compressed Strings.
  2. Succinct Representations for (Non)Deterministic Finite Automata.

MFCS 2021

  1. Matching Patterns with Variables Under Hamming Distance.

RP 2021

  1. Absent Subsequences in Words.

SEA 2021

  1. Document Retrieval Hacks.
  2. Engineering Predecessor Data Structures for Dynamic Integer Sets.

SODA 2021

  1. A Lower Bound for Dynamic Fractional Cascading.
  2. Beating the probabilistic lower bound on perfect hashing.
  3. Competitive Data-Structure Dynamization.
  4. New Data Structures for Orthogonal Range Reporting and Range Minima Queries.
  5. On Indexing and Compressing Finite Automata.
  6. On Locating Paths in Compressed Tries.
  7. Optimal Oblivious Priority Queues.

SOFSEM 2021

  1. A Normal Sequence Compressed by PPM* But Not by Lempel-Ziv 78.
  2. Blocksequences of k-local Words.
  3. Novel Results on the Number of Runs of the Burrows-Wheeler-Transform.

SOSA 2021

  1. Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets.
  2. Soft Sequence Heaps.

SPIRE 2021

  1. A Separation of γ and b via Thue-Morse Words.
  2. All Instantiations of the Greedy Algorithm for the Shortest Common Superstring Problem are Equivalent.
  3. An LMS-Based Grammar Self-index with Local Consistency Properties.
  4. Computing the Original eBWT Faster, Simpler, and with Less Memory.
  5. Exploiting Pseudo-locality of Interchange Distance.
  6. Extracting the Sparse Longest Common Prefix Array from the Suffix Binary Search Tree.
  7. Grammar Index by Induced Suffix Sorting.
  8. Improved Topic Modeling in Twitter Through Community Pooling.
  9. Longest Common Rollercoasters.
  10. Lower Bounds for the Number of Repetitions in 2D Strings.
  11. Minimal Unique Palindromic Substrings After Single-Character Substitution.
  12. On Stricter Reachable Repetitiveness Measures.
  13. On the Approximation Ratio of LZ-End to LZ77.
  14. Permutation-Constrained Common String Partitions with Applications.
  15. Position Heaps for Cartesian-Tree Matching on Strings and Tries.
  16. String Covers of a Tree.
  17. TSXor: A Simple Time Series Compression Algorithm.
  18. Unicode at Gigabytes per Second.
  19. findere: Fast and Precise Approximate Membership Query.
  20. r-Indexing the eBWT.

STACS 2021

  1. Efficiently Testing Simon’s Congruence.
  2. Finding an Optimal Alphabet Ordering for Lyndon Factorization Is Hard.
  3. The Edit Distance to k-Subsequence Universality.

STOC 2021

  1. Fully dynamic approximation of LIS in polylogarithmic time.
  2. Improved dynamic algorithms for longest increasing subsequence.
  3. Subcubic algorithms for Gomory-Hu tree in unweighted graphs.

WABI 2021

  1. Compressing and Indexing Aligned Readsets.
  2. Space-Efficient Representation of Genomic k-Mer Count Tables.

ACM Comput. Surv. 2021

  1. Predecessor Search.

ACM J. Exp. Algorithmics 2021

  1. Engineering Practical Lempel-Ziv Tries.

ACM Trans. Algorithms 2021

  1. Optimal Substring Equality Queries with Applications to Sparse Text Indexing.
  2. Optimal-Time Dictionary-Compressed Indexes.

ACM Trans. Knowl. Discov. Data 2021

  1. Combinatorial Algorithms for String Sanitization.

Algorithmica 2021

  1. Internal Dictionary Matching.
  2. Range Majorities and Minorities in Arrays.
  3. Top Tree Compression of Tries.

Algorithms 2021

  1. Compressed Communication Complexity of Hamming Distance.
  2. Lempel-Ziv Parsing for Sequences of Blocks.
  3. Non-Overlapping LZ77 Factorization and LZ78 Substring Compression Queries with Suffix Trees.
  4. Re-Pair in Small Space.
  5. Reversed Lempel-Ziv Factorization with Suffix Trees.
  6. Subpath Queries on Compressed Graphs: A Survey.

Bioinform. 2021

  1. Accurate spliced alignment of long RNA sequencing reads.

Comput. J. 2021

  1. Smaller Compressed Suffix Arrays†.

IEEE Trans. Inf. Theory 2021

  1. On the Approximation Ratio of Ordered Parsings.
  2. The Smallest Grammar Problem Revisited.

Inf. Comput. 2021

  1. Efficient pattern matching in elastic-degenerate strings.
  2. On the cost of unsuccessful searches in search trees with two-way comparisons.
  3. Wheeler languages.

Inf. Process. Lett. 2021

  1. Longest previous overlapping factor array.

Int. J. Geogr. Inf. Sci. 2021

  1. An index for moving objects with constant-time access to their compressed trajectories.

J. Comput. Syst. Sci. 2021

  1. Block trees.
  2. Circular pattern matching with k mismatches.
  3. Grammar-compressed indexes with logarithmic search time.

J. Inf. Process. 2021

  1. Towards a Complete Perspective on Labeled Tree Indexing: New Size Bounds, Efficient Constructions, and Beyond.

J. King Saud Univ. Comput. Inf. Sci. 2021

  1. A survey on data compression techniques: From the perspective of data quality, coding schemes, data type and applications.

Theor. Comput. Sci. 2021

  1. Adaptive learning of compressible strings.
  2. Computing longest palindromic substring after single-character or block-wise edits.
  3. Efficiently computing runs on a trie.
  4. Maximal unbordered factors of random strings.
  5. Space-efficient construction of compressed suffix trees.
  6. Tight upper and lower bounds on suffix tree breadth.
  7. When a dollar makes a BWT.

Theory Comput. Syst. 2021

  1. Constructing Antidictionaries of Long Texts in Output-Sensitive Space.
This site is open source. Improve this page.