StringologyTimes

Papers for stringologist (2013)

• ALENEX(2013) [dblp]
• CIAA(2013) [dblp]
• CIAC(2013) [dblp]
• CPM(2013) [dblp]
• CSR(2013) [dblp]
• CiE(2013) [dblp]
• DCC(2013) [dblp]
• Developments in Language Theory(2013) [dblp]
• ESA(2013) [dblp]
• ICALP (1)(2013) [dblp]
• ICCS(2013) [dblp]
• IEEE BigData(2013) [dblp]
• ISAAC(2013) [dblp]
• IWOCA(2013) [dblp]
• Information Theory, Combinatorics, and Search Theory(2013) [dblp]
• LATA(2013) [dblp]
• MFCS(2013) [dblp]
• MICRO(2013) [dblp]
• PPAM (2)(2013) [dblp]
• SEA(2013) [dblp]
• SIGIR(2013) [dblp]
• SODA(2013) [dblp]
• SOFSEM(2013) [dblp]
• SPIRE(2013) [dblp]
• STACS(2013) [dblp]
• Stringology(2013) [dblp]
• WABI(2013) [dblp]

• WADS(2013) [dblp]

• ACM Comput. Surv.(2013) [dblp]
• ACM J. Exp. Algorithmics(2013) [dblp]
• ACM Trans. Algorithms(2013) [dblp]
• Algorithmica(2013) [dblp]
• Algorithms(2013) [dblp]
• Algorithms Mol. Biol.(2013) [dblp]
• BMC Bioinform.(2013) [dblp]
• CoRR(2013) [dblp]
• Eur. J. Comb.(2013) [dblp]
• IEICE Trans. Inf. Syst.(2013) [dblp]
• Inf. Comput.(2013) [dblp]
• Inf. Process. Manag.(2013) [dblp]
• Inf. Syst.(2013) [dblp]
• Int. J. Comput. Biol. Drug Des.(2013) [dblp]
• Int. J. Comput. Geom. Appl.(2013) [dblp]
• J. Discrete Algorithms(2013) [dblp]
• SIAM J. Comput.(2013) [dblp]
• Theor. Comput. Sci.(2013) [dblp]

Contents

ALENEX 2013

1. Fast Packed String Matching for Short Patterns.
2. Inducing Suffix and Lcp Arrays in External Memory.
3. Lempel-Ziv factorization: Simple, fast, practical.

CIAA 2013

1. Compressed Automata for Dictionary Matching.

CIAC 2013

1. Average Optimal String Matching in Packed Strings.

CPM 2013

1. A Bit-Parallel, General Integer-Scoring Sequence Alignment Algorithm.
2. A Constant-Space Comparison-Based Algorithm for Computing the Burrows-Wheeler Transform.
3. A Succinct Grammar Compression.
4. Approximating Shortest Superstring Problem Using de Bruijn Graphs.
5. Approximation of Grammar-Based Compression via Recompression.
6. Compact q-Gram Profiling of Compressed Strings.
7. Converting SLP to LZ78 in almost Linear Time.
8. Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings.
9. Discrete Methods for Image Analysis Applied to Molecular Biology.
10. Document Listing on Repetitive Collections.
11. Efficient All Path Score Computations on Grid Graphs.
12. Efficient Lyndon Factorization of Grammar Compressed Text.
13. External Memory Generalized Suffix and LCP Arrays Construction.
14. Fast Algorithm for Partial Covers in Words.
15. Forty Years of Text Indexing.
16. LCP Magic.
17. Linear Time Lempel-Ziv Factorization: Simple, Fast, Small.
18. Local Search for String Problems: Brute Force Is Essentially Optimal.
19. Locating All Maximal Approximate Runs in a String.
20. New Algorithms for Position Heaps.
21. On Minimal and Maximal Suffixes of a Substring.
22. Pattern Matching with Variables: A Multivariate Complexity Analysis.
23. Space-Efficient Construction Algorithm for the Circular Suffix Tree.
24. Time-Space Trade-Offs for the Longest Common Substring Problem.

CSR 2013

1. Alphabetic Minimax Trees in Linear Time.

CiE 2013

1. Discovering Hidden Repetitions in Words.

DCC 2013

1. A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support.
2. Algorithms for Compressed Inputs.
3. An Adaptive Difference Distribution-Based Coding with Hierarchical Tree Structure for DNA Sequence Compression.
4. Compressed Parameterized Pattern Matching.
5. Compressing Huffman Models on Large Alphabets.
6. Computing Convolution on Grammar-Compressed Text.
7. Effective Variable-Length-to-Fixed-Length Coding via a Re-Pair Algorithm.
8. Faster Compact Top-k Document Retrieval.
9. Faster Compressed Top-k Document Retrieval.
10. From Run Length Encoding to LZ78 and Back Again.
11. Partition Tree Weighting.
12. Practical Parallel Lempel-Ziv Factorization.
13. Quadratic Similarity Queries on Compressed Data.
14. Random Extraction from Compressed Data - A Practical Study.
15. Simpler and Faster Lempel Ziv Factorization.
16. Space-Efficient Construction Algorithm for the Circular Suffix Tree.
17. Texture Compression.
18. The Rightmost Equal-Cost Position Problem.
19. Variable-to-Fixed-Length Encoding for Large Texts Using Re-Pair Algorithm with Shared Dictionaries.

Developments in Language Theory 2013

1. Abelian Repetitions in Sturmian Words.
2. On the Number of Abelian Bordered Words.
3. Repetition Avoidance in Circular Factors.
4. Suffixes, Conjugates and Lyndon Words.

ESA 2013

1. Binary Jumbled Pattern Matching on Trees and Tree-Like Structures.
2. Compressed Cache-Oblivious String B-tree.
3. Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet.
4. Encodings for Range Selection and Top-k Queries.
5. Optimal Color Range Reporting in One Dimension.
6. Parallel String Sample Sort.
7. The Encoding Complexity of Two Dimensional Range Minimum Data Structures.
8. Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform.

ICALP (1) 2013

1. Combining Binary Search Trees.
2. Dynamic Compressed Strings with Random Access.
3. Sparse Suffix Tree Construction in Small Space.
4. Tree Compression with Top Trees.

ICCS 2013

1. n-step FM-Index for Faster Pattern Matching.

IEEE BigData 2013

1. A reconfigurable stream compression hardware based on static symbol-lookup table.

ISAAC 2013

1. Beating $\mathcal{O}(nm)$ in Approximate LZW-Compressed Pattern Matching.
2. Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers.
3. Less Space: Indexing for Queries with Wildcards.
4. Pattern Matching with Non Overlapping Reversals - Approximation and On-line Algorithms.
5. RAM-Efficient External Memory Sorting.
6. Single and Multiple Consecutive Permutation Motif Search.
7. Sliding Bloom Filters.
8. Succinct Data Structures for Representing Equivalence Classes.
9. Top-k Document Retrieval in Compact Space and Near-Optimal Time.

IWOCA 2013

1. An Optimal Algorithm for Computing All Subtree Repeats in Trees.
2. Deciding Representability of Sets of Words of Equal Length in Polynomial Time.
3. Motif Matching Using Gapped Patterns.
4. Prefix Table Construction and Conversion.
5. Suffix Tree of Alignment: An Efficient Index for Similar Data.

Information Theory, Combinatorics, and Search Theory 2013

1. On the Value of Multiple Read/Write Streams for Data Compression.

LATA 2013

1. Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing.
2. On the Number of Unbordered Factors.

MFCS 2013

1. Detecting Regularities on Grammar-Compressed Strings.

MICRO 2013

1. Decoupled compressed cache: exploiting spatial locality for energy-optimized compressed caching.
2. Linearly compressed pages: a low-complexity, low-latency main memory compression framework.

PPAM (2) 2013

1. Accelerating String Matching on MIC Architecture for Motif Extraction.

SEA 2013

1. Lightweight Lempel-Ziv Parsing.
2. Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Bit Sequences.

SIGIR 2013

1. Faster and smaller inverted indices with treaps.

SODA 2013

1. Adaptive and Approximate Orthogonal Range Counting.
2. Compressed static functions with applications.
3. Lyndon Words and Short Superstrings.
4. Near-Optimal Range Reporting Structures for Categorical Data.
5. Optimal Dynamic Sequence Representations.
6. The Space Complexity of 2-Dimensional Approximate Range Counting.
7. Twisted Tabulation Hashing.

SOFSEM 2013

1. Permuted Pattern Matching on Multi-track Strings.

SPIRE 2013

1. A Lempel-Ziv Compressed Structure for Document Listing.
2. Accurate Profiling of Microbial Communities from Massively Parallel Sequencing Using Convex Optimization.
3. Adaptive Data Structures for Permutations and Binary Relations.
4. Adding Compression and Blended Search to a Compact Two-Level Suffix Array.
5. Compact Querieable Representations of Raster Data.
6. Consolidating and Exploring Information via Textual Inference.
7. Discovering Dense Subgraphs in Parallel for Compressing Web and Social Networks.
8. Distributed Query Processing on Compressed Graphs Using K2-Trees.
9. Document Listing on Versioned Documents.
10. Efficient Approximation of Edit Distance.
11. Faster Lyndon Factorization Algorithms for SLP and LZ78 Compressed Text.
12. Faster Range LCP Queries.
13. Faster Top-k Document Retrieval in Optimal Space.
14. Fully-Online Grammar Compression.
15. Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs.
16. Learning URL Normalization Rules Using Multiple Alignment of Sequences.
17. Learning to Schedule Webpage Updates Using Genetic Programming.
18. Lossless Compression of Rotated Maskless Lithography Images.
19. Minimal Discriminating Words Problem Revisited.
20. Nowcasting with Google Trends.
21. On Two-Dimensional Lyndon Words.
22. Order-Preserving Incomplete Suffix Trees and Order-Preserving Indexes.
23. Pattern Discovery and Listing in Graphs.
24. Position-Restricted Substring Searching over Small Alphabets.
25. Query Processing in Highly-Loaded Search Engines.
26. Simulation Study of Multi-threading in Web Search Engine Processors.
27. Solving Graph Isomorphism Using Parameterized Matching.
28. Space-Efficient Construction of the Burrows-Wheeler Transform.
29. Suffix Array of Alignment: A Practical Index for Similar Data.
30. Top-k Color Queries on Tree Paths.
31. Using Mutual Influence to Improve Recommendations.
32. You Are What You Eat: Learning User Tastes for Rating Prediction.

STACS 2013

1. Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries.
2. Finding Pseudo-repetitions.
3. Parameterized Matching in the Streaming Model.
4. Recompression: a simple and powerful technique for word equations.

Stringology 2013

1. Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagrams .
2. Computing Reversed Lempel-Ziv Factorization Online.
3. Crochemore’s String Matching Algorithm: Simplification, Extensions, Applications.
4. Deciding the Density Type of a Given Regular Language.
5. Degenerate String Reconstruction from Cover Arrays.
6. Finding Distinct Subpalindromes Online.
7. Graphs and Automata.
8. Improved and Self-Tuned Occurrence Heuristics.
9. Maximal Palindromic Factorization.
10. On Morphisms Generating Run-Rich Strings.
11. Optimal Partitioning of Data Chunks in Deduplication Systems.
12. Parallel Suffix Array Construction by Accelerated Sampling.
13. Sorting Suffixes of a Text via its Lyndon Factorization.
14. Swap Matching in Strings by Simulating Reactive Automata.
15. The Sum of Exponents of Maximal Repetitions in Standard Sturmian Words.
16. Towards a Very Fast Multiple String Matching Algorithm for Short Patterns.
17. Weak Factor Automata: Comparing (Failure) Oracles and Storacles.

WABI 2013

1. A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications.
2. Probabilistic Approaches to Alignment with Tandem Repeats.
3. Using Cascading Bloom Filters to Improve the Memory Usage for de Brujin Graphs.

WADS 2013

1. Better Space Bounds for Parameterized Range Majority and Minority.
2. Compressed Persistent Index for Efficient Rank/Select Queries.
3. Fingerprints in Compressed Strings.
4. On (Dynamic) Range Minimum Queries in External Memory.

ACM Comput. Surv. 2013

1. Spaces, Trees, and Colors: The algorithmic landscape of document retrieval on sequences.

ACM J. Exp. Algorithmics 2013

1. Compressed suffix trees: Efficient computation and storage of LCP-values.

ACM Trans. Algorithms 2013

1. Optimal Pattern Matching in LZW Compressed Strings.

Algorithmica 2013

1. Distribution-Aware Compressed Full-Text Indexes.
2. Sublinear Algorithms for Approximating String Compressibility.

Algorithms 2013

1. Practical Compressed Suffix Trees.

Algorithms Mol. Biol. 2013

1. Data compression for sequencing data.

BMC Bioinform. 2013

1. libgapmis: extending short-read alignments.

CoRR 2013

1. 2D Lyndon Words and Applications
2. A Dynamic Programming Solution to a Generalized LCS Problem
3. A Fixed-Parameter Algorithm for Minimum Common String Partition with Few Duplications.
4. A Functional Approach to Standard Binary Heaps.
5. A Note on the Longest Common Compatible Prefix Problem for Partial Words.
6. A Succinct Grammar Compression
7. A general definition of the big-oh notation for algorithm analysis.
8. A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support
9. AliBI: An Alignment-Based Index for Genomic Datasets.
10. Alphabet-Dependent String Searching with Wexponential Search Trees
11. An Efficient Dynamic Programming Algorithm for the Generalized LCS Problem with Multiple Substring Exclusion Constrains
12. An Elegant Algorithm for the Construction of Suffix Arrays.
13. Approximate String Matching using a Bidirectional Index.
14. Approximation of grammar-based compression via recompression
15. Approximation of smallest linear tree grammar.
16. Average Case and Distributional Analysis of Java 7’s Dual Pivot Quicksort
17. Beating O(nm) in approximate LZW-compressed pattern matching.
18. Bicriteria data compression.
19. Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression.
20. Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
21. Compact q-gram Profiling of Compressed Strings
22. Complexity of the FIFO Stack-Up Problem.
23. Compressed Pattern-Matching with Ranked Variables in Zimin Words.
24. Compressed Spaced Suffix Arrays.
25. Computing convolution on grammar-compressed text
26. Computing the Longest Increasing Subsequence of a Sequence Subject to Dynamic Insertion.
27. Data Structures in Classical and Quantum Computing.
28. Detecting regularities on grammar-compressed strings
29. Domain Specific Hierarchical Huffman Encoding.
30. Dynamic 2D Dictionary Matching in Small Space
31. Dynamic Gomory-Hu Tree Construction - fast and simple.
32. ELB-Trees, An Efficient and Lock-free B-tree Derivative.
33. Efficient Lyndon factorization of grammar compressed text
34. Efficient algorithms for the longest common subsequence in $k$-length substrings.
35. Efficient repeat finding via suffix arrays
36. Efficiently Computing Edit Distance to Dyck Language.
37. Encoding Range Minimum Queries.
38. Engineering Small Space Dictionary Matching
39. Estimating the longest increasing sequence in polylogarithmic time.
40. Faster Compact On-Line Lempel-Ziv Factorization
41. Finding Distinct Subpalindromes Online
42. Finding small patterns in permutations in linear time.
43. Fingerprints in Compressed Strings
44. First-Come-First-Served for Online Slot Allocation and Huffman Coding.
45. From Theory to Practice: Plug and Play with Succinct Data Structures.
46. Full-fledged Real-Time Indexing for Constant Size Alphabets
47. GPU Accelerated Multiple Deoxyribose Nucleic Acid Sequence Parallel Matching
48. Heaviest Induced Ancestors and Longest Common Substrings
49. Hybrid Indexes for Repetitive Datasets.
50. Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs
51. LZ-Compressed String Dictionaries
52. Large-Scale Pattern Search Using Reduced-Space On-Disk Suffix Arrays
53. Lempel-Ziv Parsing in External Memory.
54. Lightweight LCP Construction for Next-Generation Sequencing Datasets
55. Lightweight Lempel-Ziv Parsing
56. Minimal Indices for Successor Search.
57. Modulated String Searching
58. Motif matching using gapped patterns.
59. Near-optimal labeling schemes for nearest common ancestors.
60. On Updating and Querying Sub-arrays of Multidimensional Arrays.
61. On a compact encoding of the swap automaton.
62. On string matching with k mismatches.
63. One-variable word equations in linear time
64. Optimal Color Range Reporting in One Dimension.
65. Optimal Partitioning for Dual Pivot Quicksort
66. Optimal Top-k Document Retrieval.
67. Order Preserving Matching
68. Order-Preserving Suffix Trees and Their Algorithmic Applications
69. Order-preserving pattern matching with k mismatches.
70. Orthogonal Range Searching for Text Indexing.
71. Parallel Algorithm for Longest Common Subsequence in a String.
72. Parallel String Sample Sort
73. Parallel Suffix Array Construction by Accelerated Sampling
74. QuickXsort: Efficient Sorting with n log n - 1.399n +o(n) Comparisons on Average.
75. RAM-Efficient External Memory Sorting.
76. Regular Expression Searching in Sublinear Time.
77. Repetition-free longest common subsequence of random sequences
78. Set-Difference Range Queries.
79. Shortest Unique Substring Query Revisited.
80. Simple, compact and robust approximate string dictionary.
81. Single and multiple consecutive permutation motif search
82. Sorted Range Reporting Revisited.
83. Sorting suffixes of a text via its Lyndon Factorization.
84. Space Efficient Linear Time Lempel-Ziv Factorization on Constant~Size~Alphabets.
85. Statistically-secure ORAM with $\tilde{O}(\log^2 n)$ Overhead.
86. Substring Suffix Selection.
87. Succinct data structures for representing equivalence classes.
88. Succinct representation of labeled trees.
89. Suffix Trays and Suffix Trists: Structures for Faster Text Indexing.
90. Suffix Tree of Alignment: An Efficient Index for Similar Data
91. TRANS outperforms MTF for two special types of request sequences without locality of reference.
92. The Swap Matching Problem Revisited.
93. The technique of in-place associative sorting.
94. Tree Compression with Top Trees
95. Tree-based Arithmetic and Compressed Representations of Giant Numbers
96. Using cascading Bloom filters to improve the memory usage for de Brujin graphs
97. Various improvements to text fingerprinting
98. Web graph compression with fast access
99. XML Compression via DAGs.

Eur. J. Comb. 2013

1. Computing the Longest Previous Factor.
2. Minimax trees in linear time with applications.

IEICE Trans. Inf. Syst. 2013

1. Scalable Detection of Frequent Substrings by Grammar-Based Compression.

Inf. Comput. 2013

1. Compact binary relation representations with rich functionality.
2. Range majority in constant time and linear space.

Inf. Process. Manag. 2013

1. DACs: Bringing direct access to variable-length codes.

Inf. Syst. 2013

1. Space-efficient representations of rectangle datasets supporting orthogonal range querying.
2. Succinct nearest neighbor search.

Int. J. Comput. Biol. Drug Des. 2013

1. Querying highly similar sequences.

Int. J. Comput. Geom. Appl. 2013

1. External Memory orthogonal Range Reporting with Fast Updates.

J. Discrete Algorithms 2013

1. Computing the longest common prefix array based on the Burrows-Wheeler transform.
2. ESP-index: A compressed index based on edit-sensitive parsing.
3. Fast q-gram mining on SLP compressed strings.
4. Improved compressed indexes for full-text document retrieval.
5. Various improvements to text fingerprinting.

SIAM J. Comput. 2013

1. On the Bit-Complexity of Lempel-Ziv Compression.

Theor. Comput. Sci. 2013

1. Colored range queries and document retrieval.
2. Enhanced string covering.
3. On compressing and indexing repetitive sequences.
4. On compressing permutations and adaptive sorting.
5. On the weak prefix-search problem.
6. Palindrome pattern matching.
7. Space-efficient data-analysis queries on grids.
8. Succinct encoding of arbitrary graphs.

This site is open source. Improve this page.