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]

• 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]
• 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. Boxed Permutation Pattern Matching.
2. Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction.
3. Efficient Index for Weighted Sequences.
4. Factorizing a String into Squares in Linear Time.
5. Faster Longest Common Extension Queries in Strings over General Alphabets.
6. Fully-online Construction of Suffix Trees for Multiple Texts.
7. Longest Common Substring with Approximately k Mismatches.
8. Minimal Suffix and Rotation of a Substring in Optimal Time.
9. On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching.
10. Space-Efficient Dictionaries for Parameterized and Order-Preserving Pattern Matching.
11. The Nearest Colored Node in a Tree.
12. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.

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. Analyzing Relative Lempel-Ziv Reference Construction.
3. Bookmarks in Grammar-Compressed Strings.
4. Dynamic and Approximate Pattern Matching in 2D.
5. Efficient Representation of Multidimensional Data over Hierarchical Domains.
6. Efficient and Compact Representations of Some Non-canonical Prefix-Free Codes.
7. Fully Dynamic de Bruijn Graphs.
8. GraCT: A Grammar Based Compressed Representation of Trajectories.
9. LCP Array Construction Using O(sort(n)) (or Less) I/Os.
10. Longest Common Abelian Factors and Large Alphabets.
11. Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries.
12. Parallel Computation for the All-Pairs Suffix-Prefix Problem.
13. RLZAP: Relative Lempel-Ziv with Adaptive Pointers.
14. 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.

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.

Dagstuhl Reports 2016

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

Discret. Appl. Math. 2016

1. Closed factorization.
2. Random access to Fibonacci encoded files.

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.