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]
• Stringology(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]
• CoRR(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. A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem.
2. Approximate Cover of Strings.
3. Beyond Adjacency Maximization: Scaffold Filling for New String Distances.
4. Can We Recover the Cover?.
5. Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars.
6. Communication and Streaming Complexity of Approximate Pattern Matching.
7. Computing All Distinct Squares in Linear Time for Integer Alphabets.
8. Deterministic Indexing for Packed Strings.
9. Document Listing on Repetitive Collections with Guaranteed Performance.
10. Dynamic Elias-Fano Representation.
11. Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings.
12. Faster STR-IC-LCS Computation via RLE.
13. From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back.
14. Front Matter, Table of Contents, Preface, Conference Organization, External Reviewers.
15. Gapped Pattern Statistics.
16. Lempel-Ziv Compression in a Sliding Window.
17. Longest Common Extensions with Recompression.
18. On the Weighted Quartet Consensus Problem.
19. On-Line Pattern Matching on Similar Texts.
20. Optimal Omnitig Listing for Safe and Complete Contig Assembly.
21. Palindromic Length in Linear Time.
22. Path Queries on Functions.
23. Position Heaps for Parameterized Strings.
24. Recompression of SLPs.
25. Representing the Suffix Tree with the CDAWG.
26. Revisiting the Parameterized Complexity of Maximum-Duo Preservation String Mapping.
27. Shortest Superstring.
28. Synergistic Solutions on MultiSets.
29. The Longest Filled Common Subsequence Problem.
30. Tight Bounds on the Maximum Number of Shortest Unique Substrings.
31. Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing.
32. 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. Constructing a Consensus Phylogeny from a Leaf-Removal Distance (Extended Abstract).
3. Counting Palindromes in Substrings.
4. Detecting One-Variable Patterns.
5. Distinct Squares in Circular Words.
6. Efficient Compression and Indexing of Trajectories.
7. Fast Construction of Compressed Web Graphs.
8. Fast Label Extraction in the CDAWG.
9. Faster Practical Block Compression for Rank/Select Dictionaries.
10. Greedy Shortest Common Superstring Approximation in Compact Space.
11. LZ78 Compression in Low Main Memory Space.
12. Lightweight BWT and LCP Merging via the Gap Algorithm.
13. Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression.
14. Listing Maximal Independent Sets with Minimal Space and Bounded Delay.
15. Longest Common Factor After One Edit Operation.
16. Mining Bit-Parallel LCS-length Algorithms.
17. On Suffix Tree Breadth.
18. On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.
19. Optimal Skeleton Huffman Trees.
20. Order Preserving Pattern Matching on Trees and DAGs.
21. Pattern Matching on Elastic-Degenerate Text with Errors.
22. Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries.
23. Practical Implementation of Space-Efficient Dynamic Keyword Dictionaries.
24. Regular Abelian Periods and Longest Common Abelian Factors on Run-Length Encoded Strings.
25. Succinct Partial Sums and Fenwick Trees.
26. 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.

Stringology 2017

1. A Family of Exact Pattern Matching Algorithms with Multiple Adjacent Search Windows.
2. A Lempel-Ziv-style Compression Method for Repetitive Texts.
3. Counting Mismatches with SIMD.
4. Dismantling DivSufSort.
5. Dynamic Succinct Data Structures and Compressed Random Access Memory.
6. Faster Batched Range Minimum Queries.
7. Many-MADFAct: Concurrently Constructing MADFAs.
8. On Reverse Engineering the Lyndon Tree.
9. Online Recognition of Dictionary with One Gap.
10. Range Queries Using Huffman Wavelet Trees.
11. Regular Expressions with Backreferences Re-examined.
12. Speeding Up String Matching by Weak Factor Recognition.
13. The Linear Equivalence of the Suffix Array and the Partially Sorted Lyndon Array.
14. Trade-offs in Query and Target Indexing for the Selection of Candidates in Protein Homology Searches.

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.

CoRR 2017

1. A Faster Implementation of Online Run-Length Burrows-Wheeler Transform.
2. A Framework of Dynamic Data Structures for String Processing.
3. A Grammar Compression Algorithm based on Induced Suffix Sorting.
4. A Separation Between Run-Length SLPs and LZ77.
5. A compressed dynamic self-index for highly repetitive text collections.
6. A family of approximation algorithms for the maximum duo-preservation string mapping problem.
7. A local search 2.917-approximation algorithm for duo-preservation string mapping.
8. A succinct data structure for self-indexing ternary relations.
9. Alphabet-dependent Parallel Algorithm for Suffix Tree Construction for Pattern Searching.
10. Approximation ratio of RePair.
11. Assembling sequences of DNA using an on-line algorithm based on DeBruijn graphs.
12. At the Roots of Dictionary Compression: String Attractors.
13. B-slack trees: Highly Space Efficient B-trees.
14. Better Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees.
15. Biased Predecessor Search.
16. Bloom Filters, Adaptivity, and the Dictionary Problem.
17. Bubble-Flip - A New Generation Algorithm for Prefix Normal Words.
18. Cartesian trees and Lyndon trees.
19. Closing in on Time and Space Optimal Construction of Compressed Indexes.
20. Compaction of Church Numerals for Higher-Order Compression.
21. Comparison of LZ77-type Parsings.
22. Compressed Indexing with Signature Grammars.
23. Compressed Representation of Dynamic Binary Relations with Applications.
24. Compression with the tudocomp Framework.
25. Computing Abelian regularities on RLE strings.
26. Dismantling DivSufSort.
27. Distinct Squares in Circular Words.
28. Document Listing on Repetitive Collections with Guaranteed Performance.
29. Duel and sweep algorithm for order-preserving pattern matching.
30. Efficient Compression and Indexing of Trajectories.
31. Efficient Dynamic Dictionary Matching with DAWGs and AC-automata.
32. Efficient pattern matching in degenerate strings with the Burrows-Wheeler transform.
33. Even faster sorting of (not only) integers.
34. Exact Mean Computation in Dynamic Time Warping Spaces.
35. Exploiting Computation-Friendly Graph Compression Methods.
36. FAMOUS: Fast Approximate string Matching using OptimUm search Schemes.
37. FMtree: A fast locating algorithm of FM-indexes for genomic data.
38. Fast Compressed Self-Indexes with Deterministic Linear-Time Construction.
39. Fast Computation of Graph Edit Distance.
40. Fast Dynamic Arrays.
41. Fast Label Extraction in the CDAWG.
42. Fast Locating with the RLBWT.
43. Fast and Simple Jumbled Indexing for Binary RLE Strings.
44. Fast and Simple Parallel Wavelet Tree and Matrix Construction.
45. Faster STR-IC-LCS computation via RLE.
46. Faster algorithms for 1-mappability of a sequence.
47. Faster batched range minimum queries.
48. Faster range minimum queries.
49. Faster truncated integer multiplication.
50. From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back.
51. Grammar-Based Graph Compression.
52. Greedy Shortest Common Superstring Approximation in Compact Space.
53. How to answer a small batch of RMQs or LCA queries in practice.
54. Hybridizing Non-dominated Sorting Algorithms: Divide-and-Conquer Meets Best Order Sort.
55. HyperMinHash: Jaccard index sketching in LogLog space.
56. Improved Average Complexity for Comparison-Based Sorting.
57. Improved Bounds for Testing Forbidden Order Patterns.
58. Improved bounds for testing Dyck languages.
59. In-Place Initializable Arrays.
60. Indexing Weighted Sequences: Neat and Efficient.
61. Inverse Lyndon words and Inverse Lyndon factorizations of words.
62. Lempel-Ziv: a “one-bit catastrophe” but not a tragedy.
63. Linear-size CDAWG: new repetition-aware indexing and grammar compression.
64. Longest common substring with approximately k mismatches.
65. Lyndon Array Construction during Burrows-Wheeler Inversion.
66. Maximal Unbordered Factors of Random Strings.
67. Multiresolution Priority Queues.
68. Near-Optimal Compression for the Planar Graph Metric.
69. Near-optimal linear decision trees for k-SUM and related problems.
70. New Cardinality Estimation Methods for HyperLogLog Sketches.
71. New Variants of Pattern Matching with Constants and Variables.
72. New cardinality estimation algorithms for HyperLogLog sketches.
73. On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.
74. On the Decision Tree Complexity of String Matching.
75. On-line Assembling Mitochondrial DNA from de novo transcriptome.
76. On-the-Fly Array Initialization in Less Space.
77. Optimal Computation of Overabundant Words.
78. Optimal Time and Space Construction of Suffix Arrays and LCP Arrays for Integer Alphabets.
79. Optimal top dag compression.
80. Optimal trade-offs for pattern matching with k mismatches.
81. Order preserving pattern matching on trees and DAGs.
82. Ordered Dags: HypercubeSort.
83. Orthogonal Vectors Indexing.
84. Palindromic Decompositions with Gaps and Errors.
85. Persistent Cache-oblivious Streaming Indexes.
86. Position Heaps for Parameterized Strings.
87. Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries.
88. Practical and Effective Re-Pair Compression.
89. Probabilistic Analysis of the Dual-Pivot Quicksort “Count”.
90. Relations Between Greedy and Bit-Optimal LZ77 Encodings.
91. Reoptimization of the Closest Substring Problem under Pattern Length Modification.
92. Representing the suffix tree with the CDAWG.
93. Run Compressed Rank/Select for Large Alphabets.
94. Small-space encoding LCE data structure with constant-time queries.
95. Space-Efficient Algorithms for Longest Increasing Subsequence.
96. Space-efficient K-MER algorithm for generalized suffix tree.
97. Streaming Pattern Matching with d Wildcards.
98. Streaming Periodicity with Mismatches.
99. String Attractors.
100. Succinct Approximate Rank Queries.
101. Succinct Partial Sums and Fenwick Trees.
102. Text Indexing and Searching in Sublinear Time.
103. The Case for Learned Index Structures.
104. The Compressed Overlap Index.
105. The Hidden Binary Search Tree: A Balanced Rotation-Free Search Tree in the AVL RAM Model.
106. The complexity of the Multiple Pattern Matching Problem for random strings.
107. The streaming k-mismatch problem.
108. Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing.
109. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can).
110. Trie Compression for GPU Accelerated Multi-Pattern Matching.
111. Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.
112. Twin Sort Technique.
113. Whole Genome Phylogenetic Tree Reconstruction Using Colored de Bruijn Graphs.
114. m-Bonsai: a Practical Compact Dynamic Trie.

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.