StringologyTimes

Papers for stringologist (2017)

• ALENEX(2017) [dblp]
• COCOA (2)(2017) [dblp]
• COCOON(2017) [dblp]
• CPM(2017) [dblp]
• CSR(2017) [dblp]
• CiE(2017) [dblp]
• DCC(2017) [dblp]
• DLT(2017) [dblp]
• EANN(2017) [dblp]
• ESA(2017) [dblp]
• FCT(2017) [dblp]
• FOCS(2017) [dblp]
• ICALP(2017) [dblp]
• ISAAC(2017) [dblp]
• IWOCA(2017) [dblp]
• LATA(2017) [dblp]
• MFCS(2017) [dblp]
• SEA(2017) [dblp]
• SISAP(2017) [dblp]
• SODA(2017) [dblp]
• SOFSEM(2017) [dblp]
• SPIRE(2017) [dblp]
• STACS(2017) [dblp]
• STOC(2017) [dblp]
• WABI(2017) [dblp]
• WADS(2017) [dblp]
• WALCOM(2017) [dblp]

• WORDS(2017) [dblp]

• ACM J. Exp. Algorithmics(2017) [dblp]
• Algorithmica(2017) [dblp]
• Algorithms Mol. Biol.(2017) [dblp]
• BMC Bioinform.(2017) [dblp]
• Bioinform.(2017) [dblp]
• IEEE ACM Trans. Comput. Biol. Bioinform.(2017) [dblp]
• IEICE Trans. Fundam. Electron. Commun. Comput. Sci.(2017) [dblp]
• Inf. Process. Lett.(2017) [dblp]
• Inf. Retr. J.(2017) [dblp]
• Inf. Syst.(2017) [dblp]
• J. Comput. Syst. Sci.(2017) [dblp]
• J. Discrete Algorithms(2017) [dblp]
• Math. Comput. Sci.(2017) [dblp]
• Math. Struct. Comput. Sci.(2017) [dblp]
• Pattern Recognit. Lett.(2017) [dblp]
• SIAM J. Comput.(2017) [dblp]
• Theor. Comput. Sci.(2017) [dblp]

Contents

ALENEX 2017

1. CSA++: Fast Pattern Search for Large Alphabets.
2. Compact Dynamic Rewritable (CDRW) Arrays.
3. Elias-Fano meets Single-Term Top-k Document Retrieval.
4. Engineering External Memory Induced Suffix Sorting.
5. Engineering a Distributed Full-Text Index.

COCOA (2) 2017

1. Faster Algorithms for 1-Mappability of a Sequence.

COCOON 2017

1. Efficient Enumeration of Non-Equivalent Squares in Partial Words with Few Holes.

CPM 2017

1. Approximate Cover of Strings.
2. Can We Recover the Cover?.
3. Communication and Streaming Complexity of Approximate Pattern Matching.
4. Computing All Distinct Squares in Linear Time for Integer Alphabets.
5. Deterministic Indexing for Packed Strings.
6. Document Listing on Repetitive Collections with Guaranteed Performance.
7. Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings.
8. Faster STR-IC-LCS Computation via RLE.
9. From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back.
10. Lempel-Ziv Compression in a Sliding Window.
11. Longest Common Extensions with Recompression.
12. On-Line Pattern Matching on Similar Texts.
13. Palindromic Length in Linear Time.
14. Path Queries on Functions.
15. Representing the Suffix Tree with the CDAWG.
16. Tight Bounds on the Maximum Number of Shortest Unique Substrings.
17. Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing.
18. Wheeler Graphs: Variations on a Theme by Burrows and Wheeler.

CSR 2017

1. Palindromic Decompositions with Gaps and Errors.

CiE 2017

1. Flexible Indexing of Repetitive Collections.

DCC 2017

1. A Compact Index for Order-Preserving Pattern Matching.
2. A Succinct Data Structure for Multidimensional Orthogonal Range Searching.
3. Complementary Contextual Models with FM-Index for DNA Compression.
4. Compressed Dynamic Range Majority Data Structures.
5. Content Adaptive Embedded Compression.
6. Full Compressed Affix Tree Representations.
7. Improved Parallel Construction of Wavelet Trees and Rank/Select Structures.
8. Improvements on Re-Pair Grammar Compressor.
9. LZ-End Parsing in Compressed Space.
10. Making Compression Algorithms for Unicode Text.
11. Marlin: A High Throughput Variable-to-Fixed Codec Using Plurally Parsable Dictionaries.
12. Optimize Genomics Data Compression with Hardware Accelerator.
13. Space-Efficient Re-Pair Compression.
14. Stabbing Colors in One Dimension.
15. Streaming K-Mismatch with Error Correcting and Applications.
16. Symmetry-Compressible Graphs.

DLT 2017

1. On the Number of Rich Words.

EANN 2017

1. Efficient Computation of Palindromes in Sequences with Uncertainties.
2. Efficient Identification of k-Closed Strings.

ESA 2017

1. A Space-Optimal Grammar Compression.
2. An Encoding for Order-Preserving Matching.
3. Dynamic Space Efficient Hashing.
4. Fast Dynamic Arrays.
5. LZ-End Parsing in Linear Time.
6. Real-Time Streaming Multi-Pattern Search for Constant Alphabet.

FCT 2017

1. Minimal Absent Words in a Sliding Window and Applications to On-Line Pattern Matching.

FOCS 2017

1. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve.

ICALP 2017

1. Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier.
2. String Inference from Longest-Common-Prefix Array.

ISAAC 2017

1. Almost Linear Time Computation of Maximal Repetitions in Run Length Encoded Strings.
2. Fast Compressed Self-Indexes with Deterministic Linear-Time Construction.
3. On-the-Fly Array Initialization in Less Space.
4. Structural Pattern Matching - Succinctly.
5. Succinct Color Searching in One Dimension.

IWOCA 2017

1. A Faster Implementation of Online Run-Length Burrows-Wheeler Transform.
2. Computing Abelian String Regularities Based on RLE.
3. How to Answer a Small Batch of RMQs or LCA Queries in Practice.
4. Shortest Unique Palindromic Substring Queries in Optimal Time.

LATA 2017

1. Efficient Pattern Matching in Elastic-Degenerate Texts.
2. Integrated Encryption in Dynamic Arithmetic Compression.
3. Two-Dimensional Palindromes and Their Properties.

MFCS 2017

1. Binary Search in Graphs Revisited.
2. Small-Space LCE Data Structure with Constant-Time Queries.
3. The Hardness of Solving Simple Word Equations.

SEA 2017

1. A Framework of Dynamic Data Structures for String Processing.
2. Compression with the tudocomp Framework.
3. Engineering External Memory LCP Array Construction: Parallel, In-Place and Large Alphabet.
4. Fast and Scalable Minimal Perfect Hashing for Massive Key Sets.
5. Online Construction of Wavelet Trees.
6. Practical Range Minimum Queries Revisited.
7. The Quantile Index - Succinct Self-Index for Top-k Document Retrieval.

SISAP 2017

1. Practical Space-Efficient Data Structures for High-Dimensional Orthogonal Range Searching.
2. Scalable Similarity Search for Molecular Descriptors.
3. Succinct Quadtrees for Road Data.

SODA 2017

1. File Maintenance: When in Doubt, Change the Layout!
2. Hardness of Permutation Pattern Matching.
3. Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time.
4. Sparse Suffix Tree Construction in Optimal Time and Space.
5. pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems.

SOFSEM 2017

1. Computing Longest Single-arm-gapped Palindromes in a String.
2. Edit-Distance Between Visibly Pushdown Languages.
3. Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings.

SPIRE 2017

1. A Self-index on Block Trees.
2. Detecting One-Variable Patterns.
3. Distinct Squares in Circular Words.
4. Efficient Compression and Indexing of Trajectories.
5. Fast Construction of Compressed Web Graphs.
6. Fast Label Extraction in the CDAWG.
7. LZ78 Compression in Low Main Memory Space.
8. Lightweight BWT and LCP Merging via the Gap Algorithm.
9. Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression.
10. Longest Common Factor After One Edit Operation.
11. On Suffix Tree Breadth.
12. On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.
13. Optimal Skeleton Huffman Trees.
14. Order Preserving Pattern Matching on Trees and DAGs.
15. Pattern Matching on Elastic-Degenerate Text with Errors.
16. Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries.
17. Succinct Partial Sums and Fenwick Trees.
18. Tight Bounds for Top Tree Compression.

STACS 2017

1. On Long Words Avoiding Zimin Patterns.
2. On the Size of Lempel-Ziv and Lyndon Factorizations.

STOC 2017

1. Synchronization strings: codes for insertions and deletions approaching the Singleton bound.

WABI 2017

1. Optimal Computation of Overabundant Words.
2. Rainbowfish: A Succinct Colored de Bruijn Graph Representation.

WADS 2017

1. Optimal Query Time for Encoding Range Majority.

WALCOM 2017

1. A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs.

WORDS 2017

1. A de Bruijn Sequence Construction by Concatenating Cycles of the Complemented Cycling Register.
2. Burrows-Wheeler Transform and Run-Length Enconding.
3. Minimal Forbidden Factors of Circular Words.

ACM J. Exp. Algorithmics 2017

1. Practical Compact Indexes for Top-k Document Retrieval.

Algorithmica 2017

1. A Framework for Space-Efficient String Kernels.
2. Compressed Subsequence Matching and Packed Tree Coloring.
3. Efficient Computation of Substring Equivalence Classes with Suffix Arrays.
4. Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet.
5. On the Succinct Representation of Equivalence Classes.
6. String Powers in Trees.
7. Top-k Term-Proximity in Succinct Space.

Algorithms Mol. Biol. 2017

1. On avoided words, absent words, and their application to biological sequence analysis.

BMC Bioinform. 2017

1. A framework for space-efficient read clustering in metagenomic samples.

Bioinform. 2017

1. Succinct colored de Bruijn graphs.
2. emMAW: computing minimal absent words in external memory.

IEEE ACM Trans. Comput. Biol. Bioinform. 2017

1. Benchmark Dataset for Whole Genome Sequence Compression.

IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 2017

1. Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing.

Inf. Process. Lett. 2017

1. Optimal suffix sorting and LCP array construction for constant alphabets.
2. Tight lower bounds for the longest common extension problem.
3. Two strings at Hamming distance 1 cannot be both quasiperiodic.

Inf. Retr. J. 2017

1. Document retrieval on repetitive string collections.

Inf. Syst. 2017

1. Compressed representation of dynamic binary relations with applications.

J. Comput. Syst. Sci. 2017

1. Fast algorithms for Abelian periods in words and greatest common divisor queries.
2. Fingerprints in compressed strings.

J. Discrete Algorithms 2017

1. A space efficient direct access data structure.
2. A succinct data structure for self-indexing ternary relations.
3. Burrows-Wheeler transform and LCP array construction in constant space.
4. Grammar compressed sequences with rank/select support.
5. Preface - Compact Data Structures.
6. Subsequence automata with default transitions.

Math. Comput. Sci. 2017

1. Block Graphs in Practice.
2. Compressed Spaced Suffix Arrays.
3. Engineering a Lightweight External Memory Suffix Array Construction Algorithm.

Math. Struct. Comput. Sci. 2017

1. Fast circular dictionary-matching algorithm.

Pattern Recognit. Lett. 2017

1. A faster and more accurate heuristic for cyclic edit distance computation.

SIAM J. Comput. 2017

1. The “Runs” Theorem.
2. Time-Optimal Top-k Document Retrieval.

Theor. Comput. Sci. 2017

1. Covering problems for partial words and for indeterminate strings.
2. Inducing enhanced suffix arrays for string collections.
3. Inferring strings from Lyndon factorization.
4. String cadences.
5. Wheeler graphs: A framework for BWT-based data structures.

This site is open source. Improve this page.