StringologyTimes

Papers for stringologist (2016)

• ALENEX(2016) [dblp]
• COCOA(2016) [dblp]
• CPM(2016) [dblp]
• DCC(2016) [dblp]
• DLT(2016) [dblp]
• ESA(2016) [dblp]
• FOCS(2016) [dblp]
• FSTTCS(2016) [dblp]
• ICALP(2016) [dblp]
• ISAAC(2016) [dblp]
• ITCS(2016) [dblp]
• IWOCA(2016) [dblp]
• KDD(2016) [dblp]
• LATA(2016) [dblp]
• LATIN(2016) [dblp]
• MFCS(2016) [dblp]
• SEA(2016) [dblp]
• SIGIR(2016) [dblp]
• SODA(2016) [dblp]
• SOFSEM(2016) [dblp]
• SPIRE(2016) [dblp]
• STACS(2016) [dblp]
• STOC(2016) [dblp]
• SWAT(2016) [dblp]
• Stringology(2016) [dblp]

• WABI(2016) [dblp]

• ACM J. Exp. Algorithmics(2016) [dblp]
• ACM Trans. Algorithms(2016) [dblp]
• ACM Trans. Archit. Code Optim.(2016) [dblp]
• Algorithmica(2016) [dblp]
• Algorithms(2016) [dblp]
• Algorithms Mol. Biol.(2016) [dblp]
• BMC Bioinform.(2016) [dblp]
• CoRR(2016) [dblp]
• Dagstuhl Reports(2016) [dblp]
• Discret. Appl. Math.(2016) [dblp]
• IEEE ACM Trans. Comput. Biol. Bioinform.(2016) [dblp]
• IEEE Trans. Parallel Distributed Syst.(2016) [dblp]
• Inf.(2016) [dblp]
• Inf. Process. Lett.(2016) [dblp]
• Inf. Syst.(2016) [dblp]
• J. Discrete Algorithms(2016) [dblp]
• SIAM J. Discret. Math.(2016) [dblp]
• Softw. Pract. Exp.(2016) [dblp]
• Theor. Comput. Sci.(2016) [dblp]

Contents

ALENEX 2016

1. A General Framework for Dynamic Succinct and Compressed Data Structures.

COCOA 2016

1. On-Line Pattern Matching on Uncertain Sequences and Applications.

CPM 2016

1. A 7/2-Approximation Algorithm for the Maximum Duo-Preservation String Mapping Problem.
2. A Linear-Time Algorithm for the Copy Number Transformation Problem.
3. Boxed Permutation Pattern Matching.
4. Color-Distance Oracles and Snippets.
5. Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction.
6. Efficient Index for Weighted Sequences.
7. Efficient Non-Binary Gene Tree Resolution with Weighted Reconciliation Cost.
8. Encoding Two-Dimensional Range Top-k Queries.
9. Estimating Statistics on Words Using Ambiguous Descriptions.
10. Factorizing a String into Squares in Linear Time.
11. Fast Compatibility Testing for Rooted Phylogenetic Trees.
12. Faster Longest Common Extension Queries in Strings over General Alphabets.
13. Finding Maximal 2-Dimensional Palindromes.
14. Front Matter, Table of Contents, Preface.
15. Fully-online Construction of Suffix Trees for Multiple Texts.
16. Genomic Scaffold Filling Revisited.
17. Graph Motif Problems Parameterized by Dual.
18. Hardness of RNA Folding Problem With Four Symbols.
19. Linear-time Suffix Sorting - A New Approach for Suffix Array Construction.
20. Longest Common Substring with Approximately k Mismatches.
21. Minimal Suffix and Rotation of a Substring in Optimal Time.
22. On Almost Monge All Scores Matrices.
23. On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching.
24. Optimal Prefix Free Codes with Partial Sorting.
25. Reconstruction of Trees from Jumbled and Weighted Subtrees.
26. Space-Efficient Dictionaries for Parameterized and Order-Preserving Pattern Matching.
27. Succinct Online Dictionary Matching with Improved Worst-Case Guarantees.
28. The Nearest Colored Node in a Tree.
29. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
30. Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.

DCC 2016

1. A Simple and Efficient Approach for Adaptive Entropy Coding over Large Alphabets.
2. A Space Efficient Direct Access Data Structure.
3. Analysis of a Rewriting Compression System for Flash Memory.
4. Approximate String Matching for Self-Indexes.
5. Burrows-Wheeler Transform for Terabases.
6. CS2A: A Compressed Suffix Array-Based Method for Short Read Alignment.
7. Compressing Combinatorial Objects.
8. Computing LZ77 in Run-Compressed Space.
9. Efficient Compression of Genomic Sequences.
10. Efficient Environmental Temperature Monitoring Using Compressed Sensing.
11. Faster, Minuter.
12. Grammatical Ziv-Lempel Compression: Achieving PPM-Class Text Compression Ratios with LZ-Class Decompression Speed.
13. Hardware Based Compression in Big Data.
14. Improved Range Minimum Queries.
15. Induced Suffix Sorting for String Collections.
16. Lempel-Ziv Computation in Compressed Space (LZ-CICS).
17. Linear Time Succinct Indexable Dictionary Construction with Applications.
18. Lossy Compression of Unordered Rooted Trees.
19. Online Grammar Transformation Based on Re-Pair Algorithm.
20. Parallel Lightweight Wavelet Tree, Suffix Array and FM-Index Construction.
21. Positional Inverted Self-index.
22. Quick Access to Compressed Data in Storage Systems.
23. Self-Indexing RDF Archives.
24. Shortest DNA Cyclic Cover in Compressed Space.
25. Small Polygon Compression.
26. Timeliness in Lossless Block Coding.
27. When Less is More - Using Restricted Repetition Search in Fast Compressors.

DLT 2016

1. Ternary Square-Free Partial Words with Many Wildcards.

ESA 2016

1. BlockQuicksort: Avoiding Branch Mispredictions in Quicksort.
2. Faster External Memory LCP Array Construction.
3. Streaming Pattern Matching with d Wildcards.

FOCS 2016

1. Edit Distance: Sketching, Streaming, and Document Exchange.

FSTTCS 2016

1. Finger Search in Grammar-Compressed Strings.
2. LZ77 Factorisation of Trees.

ICALP 2016

1. Approximate Hamming Distance in a Stream.
2. Data Structure Lower Bounds for Document Indexing Problems.
3. Towards Tight Lower Bounds for Range Reporting on the RAM.

ISAAC 2016

1. Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation.
2. Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap.
3. Pattern Matching and Consensus Problems on Weighted Sequences and Profiles.
4. Space-Time Trade-Offs for the Shortest Unique Substring Problem.

ITCS 2016

1. Is There an Oblivious RAM Lower Bound?

IWOCA 2016

1. Finding Gapped Palindromes Online.
2. Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing.
3. Partial Covering Arrays: Algorithms and Asymptotics.

KDD 2016

1. Scalable Partial Least Squares Regression on Grammar-Compressed Data Matrices.

LATA 2016

1. On Del-Robust Primitive Partial Words with One Hole.
2. Optimal Bounds for Computing \alpha α -gapped Repeats.

LATIN 2016

1. Bidirectional Variable-Order de Bruijn Graphs.
2. Compressing Bounded Degree Graphs.
3. Deterministic Sparse Suffix Sorting on Rewritable Texts.
4. Linear-Time Sequence Comparison Using Minimal Absent Words & Applications.
5. The Grandmama de Bruijn Sequence for Binary Strings.
6. Tree Compression Using String Grammars.

MFCS 2016

1. Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets.
2. Dividing by Zero - How Bad Is It, Really?.
3. Fully Dynamic Data Structure for LCE Queries in Compressed Space.
4. Shortest Unique Substring Queries on Run-Length Encoded Strings.

SEA 2016

1. CHICO: A Compressed Hybrid Index for Repetitive Collections.
2. Fast Scalable Construction of (Minimal Perfect Hash) Functions.
3. Lempel-Ziv Decoding in External Memory.
4. Practical Dynamic Entropy-Compressed Bitvectors with Applications.
5. Practical Variable Length Gap Pattern Matching.
6. Worst-Case-Efficient Dynamic Arrays in Practice.

SIGIR 2016

1. Fast and Compact Hamming Distance Index.
2. Succinct Data Structures in Information Retrieval: Theory and Practice.

SODA 2016

1. Range Predecessor and Lempel-Ziv Parsing.
2. The k-mismatch problem revisited.
3. Weighted dynamic finger in binary search trees.

SOFSEM 2016

1. Compacting a Dynamic Edit Distance Table by RLE Compression.
2. Subsequence Automata with Default Transitions.

SPIRE 2016

1. A Linear-Space Algorithm for the Substring Constrained Alignment Problem.
2. AC-Automaton Update Algorithm for Semi-dynamic Dictionary Matching.
3. Analyzing Relative Lempel-Ziv Reference Construction.
4. Bookmarks in Grammar-Compressed Strings.
5. Compact Trip Representation over Networks.
6. Dynamic and Approximate Pattern Matching in 2D.
7. Efficient Representation of Multidimensional Data over Hierarchical Domains.
8. Efficient and Compact Representations of Some Non-canonical Prefix-Free Codes.
9. Fast Classification of Protein Structures by an Alignment-Free Kernel.
10. Fragmented BWT: An Extended BWT for Full-Text Indexing.
11. Fully Dynamic de Bruijn Graphs.
12. GraCT: A Grammar Based Compressed Representation of Trajectories.
13. Inverse Range Selection Queries.
14. LCP Array Construction Using O(sort(n)) (or Less) I/Os.
15. Lexical Matching of Queries and Ads Bid Terms in Sponsored Search.
16. Longest Common Abelian Factors and Large Alphabets.
17. Low Space External Memory Construction of the Succinct Permuted Longest Common Prefix Array.
18. Maximal Unbordered Factors of Random Strings.
19. Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries.
20. Parallel Computation for the All-Pairs Suffix-Prefix Problem.
21. Parallel Lookups in String Indexes.
22. Pattern Matching for Separable Permutations.
23. RLZAP: Relative Lempel-Ziv with Adaptive Pointers.
24. The Smallest Grammar Problem Revisited.
25. XBWT Tricks.

STACS 2016

1. Efficiently Finding All Maximal alpha-gapped Repeats.
2. External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates.
3. Periods and Borders of Random Words.

STOC 2016

1. Streaming algorithms for embedding and computing edit distance in the low distance regime.

SWAT 2016

1. A Framework for Dynamic Parameterized Dictionary Matching.
2. A Simple Mergeable Dictionary.
3. Cuckoo Filter: Simplification and Analysis.
4. Lower Bounds for Approximation Schemes for Closest String.

Stringology 2016

1. A Family of Data Compression Codes with Multiple Delimiters.
2. A Resource-frugal Probabilistic Dictionary and Applications in (Meta)Genomics.
3. Accelerated Partial Decoding in Wavelet Trees.
4. Algorithms to Compute the Lyndon Array.
5. Computing All Approximate Enhanced Covers with the Hamming Distance.
6. Computing Smallest and Largest Repetition Factorizations in O(n log n) Time.
7. Dynamic Index and LZ Factorization in Compressed Space.
8. Fast Full Permuted Pattern Matching Algorithms on Multi-track Strings.
9. Forced Repetitions over Alphabet Lists.
10. Generating All Minimal Petri Net Unsolvable Binary Words.
11. Interpreting the Subset Construction Using Finite Sublanguages.
12. Jumbled Matching with SIMD.
13. The String Matching Algorithms Research Tool.
14. The Use and Usefulness of Fibonacci Codes.
15. Using Human Computation in Dead-zone based 2D Pattern Matching.

WABI 2016

1. A Graph Extension of the Positional Burrows-Wheeler Transform and Its Applications.
2. A Natural Encoding of Genetic Variation in a Burrows-Wheeler Transform to Enable Mapping and Genome Inference.
3. Optimal Computation of Avoided Words.

ACM J. Exp. Algorithmics 2016

1. Faster Compressed Suffix Trees for Repetitive Collections.
2. Inducing Suffix and LCP Arrays in External Memory.
3. LCP Array Construction in External Memory.
4. Lazy Lempel-Ziv Factorization Algorithms.

ACM Trans. Algorithms 2016

1. Compressed Cache-Oblivious String B-Tree.
2. Data Structures for Path Queries.
3. Sparse Text Indexing in Small Space.

ACM Trans. Archit. Code Optim. 2016

1. Yet Another Compressed Cache: A Low-Cost Yet Effective Compressed Cache.

Algorithmica 2016

1. Compressed String Dictionary Search with Edit Distance One.
2. Optimal Encodings for Range Majority Queries.

Algorithms 2016

1. siEDM: An Efficient String Index and Search Algorithm for Edit Distance with Moves.

Algorithms Mol. Biol. 2016

1. Circular sequence comparison: algorithms and applications.
2. Erratum to: Circular sequence comparison: algorithms and applications.

BMC Bioinform. 2016

1. libFLASM: a software library for fixed-length approximate string matching.

CoRR 2016

1. A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs.
2. A New Lightweight Algorithm to compute the BWT and the LCP array of a Set of Strings.
3. A Self-Index on Block Trees.
4. A Simpler Bit-parallel Algorithm for Swap Matching.
5. A family of fast exact pattern matching algorithms.
6. A hardness result and new algorithm for the longest common palindromic subsequence problem.
7. A loopless and branchless $O(1)$ algorithm to generate the next Dyck word.
8. Access Time Tradeoffs in Archive Compression.
9. Aggregated 2D Range Queries on Clustered Points.
10. Algorithms to Compute the Lyndon Array.
11. An Estimation of the Size of Non-Compact Suffix Trees.
12. An Optimal Algorithm for Range Search on Multidimensional Points.
13. Approximate Hamming distance in a stream.
14. Asymmetric Rényi Problem and PATRICIA Tries.
15. Average Size of a Suffix Tree for Markov Sources.
16. Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort.
17. Burrows-Wheeler transform and LCP array construction in constant space.
18. CSA++: Fast Pattern Search for Large Alphabets.
19. Comments on Dumitrescu’s “A Selectable Sloppy Heap”.
20. Compressed Dynamic Range Majority Data Structures.
21. Compressing Graphs and Indexes with Recursive Graph Bisection.
22. Compressing and Indexing Stock Market Data.
23. Computing All Distinct Squares in Linear Time for Integer Alphabets.
24. Computing Longest Increasing Subsequence Over Sequential Data Streams.
25. Computing longest single-arm-gapped palindromes in a string.
26. Data Structure Lower Bounds for Document Indexing Problems.
27. Designing optimal- and fast-on-average pattern matching algorithms.
28. Detecting Unary Patterns.
29. Deterministic Indexing for Packed Strings.
30. Deterministic sub-linear space LCE data structures with efficient construction.
31. Distortion-Resistant Hashing for rapid search of similar DNA subsequence.
32. Document Retrieval on Repetitive String Collections.
33. Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths.
34. Dynamic Time Warping: Breaking the Quadratic Barrier.
35. Dynamic index and LZ factorization in compressed space.
36. Edit Distance: Sketching, Streaming and Document Exchange.
37. Efficient Index Maintenance Under Dynamic Genome Modification.
38. Efficient Index for Weighted Sequences.
39. Efficient Pattern Matching in Elastic-Degenerate Strings.
40. Efficient Representation of Multidimensional Data over Hierarchical Domains.
41. Efficient and Compact Representations of Some Non-Canonical Prefix-Free Codes.
42. Encoding Arguments.
43. Energy-Efficient Algorithms.
44. Engineering a Distributed Full-Text Index.
45. Fast Longest Common Extensions in Small Space.
46. Faster Longest Common Extension Queries in Strings over General Alphabets.
47. From H&M to Gap for Lightweight BWT Merging.
48. Fully Dynamic de Bruijn Graphs.
49. Fully dynamic data structure for LCE queries in compressed space.
50. Games from Basic Data Structures.
51. GateKeeper: Enabling Fast Pre-Alignment in DNA Short Read Mapping with a New Streaming Accelerator Architecture.
52. GraCT: A Grammar based Compressed representation of Trajectories.
53. Hardness of Permutation Pattern Matching.
54. Improved Space efficient algorithms for BFS, DFS and applications.
55. In-Place Longest Common Extensions.
56. LZ-End Parsing in Compressed Space.
57. Lempel-Ziv Decoding in External Memory.
58. Lightweight LCP Construction for Very Large Collections of Strings.
59. Linear-time string indexing and analysis in small space.
60. Longest Common Extensions with Recompression.
61. Longest Common Subsequence in at Least k Length Order-isomorphic Substrings.
62. Low Space External Memory Construction of the Succinct Permuted Longest Common Prefix Array.
63. Minimal Suffix and Rotation of a Substring in Optimal Time.
64. Monte Carlo Sort for unreliable human comparisons.
65. Multi-view pattern matching.
66. Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries.
67. New Error Tolerant Method to Search Long Repeats in Symbol Sequences.
68. Oblivious Sorting and Queues.
69. On pattern matching with k mismatches and few don’t cares.
70. On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching.
71. On the Size of Lempel-Ziv and Lyndon Factorizations.
72. On the circuit complexity of the standard and the Karatsuba methods of multiplying integers.
73. Online Grammar Compression for Frequent Pattern Discovery.
74. Optimal Computation of Avoided Words.
75. Optimal In-Place Suffix Sorting.
76. Optimal Prefix Free Codes With Partial Sorting.
77. Optimizing run-length algorithm using octonary repetition tree.
78. Pachinko.
79. Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing.
80. Parameterized Pattern Matching - Succinctly.
81. Practical Data Compression for Modern Memory Hierarchies.
82. Practical combinations of repetition-aware data structures.
83. RLZAP: Relative Lempel-Ziv with Adaptive Pointers.
84. Randomized Ternary Search Tries.
85. Range Majorities and Minorities in Arrays.
86. Rank and select: Another lesson learned.
87. Representing Pattern Matching Algorithms by Polynomial-Size Automata.
88. Scalable Construction of Text Indexes.
89. Scalable Partial Least Squares Regression on Grammar-Compressed Data Matrices.
90. Shortest unique palindromic substring queries in optimal time.
91. Simple and Efficient Fully-Functional Succinct Trees.
92. Sort Race.
93. Sort well with energy-constrained comparisons.
94. Sorting Discrete i.i.d. Inputs: Quicksort is Optimal.
95. Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time.
96. Space-Efficient Re-Pair Compression.
97. Sparse Suffix Tree Construction in Optimal Time and Space.
98. Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees.
99. Streaming k-mismatch with data recovery and applications.
100. String Cadences.
101. String Inference from the LCP Array.
102. Succinct Choice Dictionaries.
103. Succinct data-structure for nearest colored node in a tree.
104. Suffix arrays with a twist.
105. The Generalized Smallest Grammar Problem.
106. The complexity of bit retrieval.
107. The landscape of bounds for binary search trees.
108. Tight Lower Bounds for the Longest Common Extension Problem.
109. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
110. Tight bound on the maximum number of shortest unique substrings.
111. Toward a Succinct Index for Order-Preserving Pattern Matching.
112. Twenty (simple) questions.
113. Two-stage algorithms for covering array construction.
114. TwoPaCo: An efficient algorithm to build the compacted de Bruijn graph from many complete genomes.
115. Universal Indexes for Highly Repetitive Document Collections.
116. Variance of the Internal Profile in Suffix Trees.
117. Word Existence Algorithm.
118. siEDM: an efficient string index and search algorithm for edit distance with moves.

Dagstuhl Reports 2016

1. Computation over Compressed Structured Data (Dagstuhl Seminar 16431).

Discret. Appl. Math. 2016

1. A computational substantiation of the d-step approach to the number of distinct squares problem.
2. A multiobjective optimization algorithm for the weighted LCS.
3. A note on easy and efficient computation of full abelian periods of a word.
4. Closed factorization.
5. Computing covers using prefix tables.
6. Editorial: Stringology Algorithms.
7. New tabulation and sparse dynamic programming based techniques for sequence similarity problems.
8. Optimal partitioning of data chunks in deduplication systems.
9. Random access to Fibonacci encoded files.
10. Sequence binary decision diagram: Minimization, relationship to acyclic automata, and complexities of Boolean set operations.
11. Similarity based deduplication with small data chunks.
12. The New Periodicity Lemma revisited.
13. The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings.

IEEE ACM Trans. Comput. Biol. Bioinform. 2016

1. Parallel and Space-Efficient Construction of Burrows-Wheeler Transform and Suffix Array for Big Genome Data.

IEEE Trans. Parallel Distributed Syst. 2016

1. A Survey Of Architectural Approaches for Data Compression in Cache and Main Memory Systems.

Inf. 2016

1. Lazy Management for Frequency Table on Hardware-Based Stream Lossless Data Compression.

Inf. Process. Lett. 2016

1. Computing runs on a general alphabet.
2. On the greedy algorithm for the Shortest Common Superstring problem with reversals.

Inf. Syst. 2016

1. Aggregated 2D range queries on clustered points.
2. New dynamic metric indices for secondary memory.
3. Practical compressed string dictionaries.
4. Universal indexes for highly repetitive document collections.

J. Discrete Algorithms 2016

1. An improved algorithm for the all-pairs suffix-prefix problem.

SIAM J. Discret. Math. 2016

1. Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence.

Softw. Pract. Exp. 2016

1. Improving a lightweight LZ77 computation algorithm for running faster.

Theor. Comput. Sci. 2016

1. A really simple approximation of smallest grammar.
2. Computing minimal and maximal suffixes of a substring.
3. Document retrieval with one wildcard.
4. Dynamic range majority data structures.
5. Fast computation of abelian runs.
6. Fast construction of wavelet trees.
7. Faster Lyndon factorization algorithms for SLP and LZ78 compressed text.
8. Finding the leftmost critical factorization on unordered alphabet.
9. Generalized pattern matching and periodicity under substring consistent equivalence relations.
10. Linear-time computation of prefix table for weighted strings & applications.
11. Linear-time superbubble identification algorithm for genome assembly.
12. Longest common extensions in trees.
13. Maximum number of distinct and nonequivalent nonstandard squares in a word.
14. Order-preserving indexing.
15. Order-preserving pattern matching with k mismatches.
16. Permuted scaled matching.
17. Reporting consecutive substring occurrences under bounded gap constraints.
18. Simple and efficient fully-functional succinct trees.
19. Tighter bounds for the sum of irreducible LCP values.

This site is open source. Improve this page.