StringologyTimes

Papers for stringologist (2014)

• ALENEX(2014) [dblp]
• CPM(2014) [dblp]
• DCC(2014) [dblp]
• Developments in Language Theory(2014) [dblp]
• ESA(2014) [dblp]
• FOCS(2014) [dblp]
• FSTTCS(2014) [dblp]
• HPCA(2014) [dblp]
• ICALP (1)(2014) [dblp]
• ISAAC(2014) [dblp]
• IWOCA(2014) [dblp]
• JSAI-isAI Workshops(2014) [dblp]
• LATIN(2014) [dblp]
• Language, Culture, Computation (1)(2014) [dblp]
• MFCS (1)(2014) [dblp]
• MFCS (2)(2014) [dblp]
• SEA(2014) [dblp]
• SISAP(2014) [dblp]
• SODA(2014) [dblp]
• SOFSEM(2014) [dblp]
• SPIRE(2014) [dblp]
• STACS(2014) [dblp]
• STOC(2014) [dblp]
• SWAT(2014) [dblp]
• Stringology(2014) [dblp]
• TFPIE(2014) [dblp]
• WABI(2014) [dblp]

• WALCOM(2014) [dblp]

• ACM J. Exp. Algorithmics(2014) [dblp]
• ACM Trans. Algorithms(2014) [dblp]
• ACM Trans. Inf. Syst.(2014) [dblp]
• Algorithmica(2014) [dblp]
• Algorithms(2014) [dblp]
• Algorithms Mol. Biol.(2014) [dblp]
• BMC Bioinform.(2014) [dblp]
• CoRR(2014) [dblp]
• Comput. Geom.(2014) [dblp]
• Discret. Appl. Math.(2014) [dblp]
• IEEE Trans. Knowl. Data Eng.(2014) [dblp]
• J. Comput. Syst. Sci.(2014) [dblp]
• J. Discrete Algorithms(2014) [dblp]
• Knowl. Inf. Syst.(2014) [dblp]
• Parallel Comput.(2014) [dblp]
• SIAM J. Comput.(2014) [dblp]
• Softw. Pract. Exp.(2014) [dblp]
• Theor. Comput. Sci.(2014) [dblp]
• Theory Comput. Syst.(2014) [dblp]

Contents

ALENEX 2014

1. Multi-Pivot Quicksort: Theory and Experiments.
2. Top-k Substring Matching for Auto-Completion.

CPM 2014

1. A really Simple Approximation of Smallest Grammar.
2. An Improved Query Time for Succinct Dynamic Dictionary Matching.
3. Approximate On-line Palindrome Recognition, and Applications.
4. Approximate String Matching Using a Bidirectional Index.
5. Compactness-Preserving Mapping on Trees.
6. Compressed Subsequence Matching and Packed Tree Coloring.
7. Computing Minimal and Maximal Suffixes of a Substring Revisited.
8. Computing Palindromic Factorizations and Palindromic Covers On-line.
9. Computing k-th Lyndon Word and Decoding Lexicographically Minimal de Bruijn Sequence.
10. Dictionary Matching with One Gap.
11. Efficient Algorithms for Shortest Partial Seeds in Words.
12. Encodings for Range Majority Queries.
13. From Indexing Data Structures to de Bruijn Graphs.
14. Indexed Geometric Jumbled Pattern Matching.
15. Most Recent Match Queries in On-Line Suffix Trees.
16. On Combinatorial Generation of Prefix Normal Words.
17. On Hardness of Several String Indexing Problems.
18. On the DCJ Median Problem.
19. On the Efficiency of the Hamming C-Centerstring Problems.
20. Order-Preserving Pattern Matching with k Mismatches.
21. Parameterized Complexity Analysis for the Closest String with Wildcards Problem.
22. Permuted Scaled Matching.
23. Randomized and Parameterized Algorithms for the Closest String Problem.
24. Reversal Distances for Strings with Few Blocks or Small Alphabets.
25. Searching of Gapped Repeats and Subrepetitions in a Word.
26. Shortest Unique Substring Query Revisited.
27. String Range Matching.
28. The Worst Case Complexity of Maximum Parsimony.

DCC 2014

1. A Practical Implementation of Compressed Suffix Arrays with Applications to Self-Indexing.
2. Adaptive Dictionary Sharing Method for Re-Pair Algorithm.
3. Alignment Free Sequence Similarity with Bounded Hamming Distance.
4. Better Compression through Better List Update Algorithms.
5. Boosting the Compression of Rewriting on Flash Memory.
6. Combining Deduplication and Delta Compression to Achieve Low-Overhead Data Reduction on Backup Datasets.
7. Compressing Sets and Multisets of Sequences.
8. Compressing Similar Biological Sequences Using FM-Index.
9. Compression Schemes for Similarity Queries.
10. Direct Access to Variable-to-Fixed Length Codes with a Succinct Index.
11. Entropy Reduction Using Context Transformations.
12. Fast Fully-Compressed Suffix Trees.
13. Fully Online Grammar Compression in Constant Space.
14. Hybrid Compression of Bitvectors for the FM-Index.
15. Information Profiles for DNA Pattern Discovery.
16. Interleaved K2-Tree: Indexing and Navigating Ternary Relations.
17. LZ-Compressed String Dictionaries.
18. Lempel-Ziv Parsing in External Memory.
19. Relative Lempel-Ziv with Constant-Time Random Access.
20. Space Efficient Linear Time Lempel-Ziv Factorization for Small Alphabets.
21. Towards Markup-Aware Text Compression.
22. Universal Text Preprocessing and Postprocessing for PPM Using Alphabet Adjustment.

Developments in Language Theory 2014

1. On k-Abelian Palindromic Rich and Poor Words.
2. k-Abelian Pattern Matching.

ESA 2014

1. Amortized Bounds for Dynamic Orthogonal Range Reporting.
2. Bicriteria Data Compression: Efficient and Usable.
3. Document Retrieval on Repetitive Collections.
4. Equivalence between Priority Queues and Sorting in External Memory.
5. Sublinear Space Algorithms for the Longest Common Substring Problem.
6. The Batched Predecessor Problem in External Memory.
7. Weighted Ancestors in Suffix Trees.

FOCS 2014

1. Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search.
2. The Dyck Language Edit Distance Problem in Near-Linear Time.

FSTTCS 2014

1. Asymptotically Optimal Encodings for Range Selection.

HPCA 2014

1. MemZip: Exploring unconventional benefits from memory compression.

ICALP (1) 2014

1. Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM.
2. On Hardness of Jumbled Indexing.

ISAAC 2014

1. Depth-First Search Using O(n) Bits.
2. Hashing and Indexing: Succinct DataStructures and Smoothed Analysis.
3. The Power and Limitations of Static Binary Search Trees with Lazy Finger.
4. Top- k Term-Proximity in Succinct Space.

IWOCA 2014

1. A Suffix Tree Or Not a Suffix Tree?
2. Computing Primitively-Rooted Squares and Runs in Partial Words.
3. Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance.

JSAI-isAI Workshops 2014

1. Finding Ambiguous Patterns on Grammar Compressed String.

LATIN 2014

1. Biased Predecessor Search.
2. LZ77-Based Self-indexing with Faster Pattern Matching.
3. Multiply Balanced k -Partitioning.
4. Quad-K-d Trees.

Language, Culture, Computation (1) 2014

1. Hypertext Searching - A Survey.

MFCS (1) 2014

1. Universal Lyndon Words.

MFCS (2) 2014

1. Document Retrieval with One Wildcard.
2. Inferring Strings from Lyndon Factorization.

SEA 2014

1. Approximate Online Matching of Circular Strings.
2. DenseZDD: A Compact and Fast Index for Families of Sets.
3. Efficient Representation for Online Suffix Tree Construction.
4. Efficient Wavelet Tree Construction and Querying for Multicore Architectures.
5. Faster Compressed Suffix Trees for Repetitive Text Collections.
6. From Theory to Practice: Plug and Play with Succinct Data Structures.
7. Improved ESP-index: A Practical Self-index for Highly Repetitive Texts.
8. Improved and Extended Locating Functionality on Compressed Suffix Arrays.
9. LCP Array Construction in External Memory.
10. Order-Preserving Matching with Filtration.
11. Retrieval and Perfect Hashing Using Fingerprinting.

SISAP 2014

1. Dynamic List of Clusters in Secondary Memory.

SODA 2014

1. Bicriteria data compression.
2. Concurrent Range Reporting in Two-Dimensional Space.
3. Finding small patterns in permutations in linear time.
4. Near-optimal labeling schemes for nearest common ancestors.
5. Selection and Sorting in the “Restore” Model.

SOFSEM 2014

1. Shortest Unique Substrings Queries in Optimal Time.

SPIRE 2014

1. A 3-Approximation Algorithm for the Multiple Spliced Alignment Problem and Its Application to the Gene Prediction Task.
2. A Compressed Suffix-Array Strategy for Temporal-Graph Indexing.
3. Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on Run-Length Encoded Strings.
4. Alphabet-Independent Algorithms for Finding Context-Sensitive Repeats in Linear Time.
5. Context-Aware Deal Size Prediction.
6. Efficient Compressed Indexing for Approximate Top-k String Retrieval.
7. Efficient Indexing and Representation of Web Access Logs.
8. Fast Construction of Wavelet Trees.
9. Grammar Compressed Sequences with Rank/Select Support.
10. I/O-Efficient Dictionary Search with One Edit Error.
11. Improved Filters for the Approximate Suffix-Prefix Overlap Problem.
12. Indexed Matching Statistics and Shortest Unique Substrings.
13. Information-Theoretic Term Selection for New Item Recommendation.
14. K 2-Treaps: Range Top-k Queries in Compact Space.
15. On the String Consensus Problem and the Manhattan Sequence Consensus Problem.
16. Online Multiple Palindrome Pattern Matching.
17. Online Pattern Matching for String Edit Distance with Moves.
18. Order Preserving Prefix Tables.
19. Performance Improvements for Search Systems Using an Integrated Cache of Lists+Intersections.
20. Relative FM-Indexes.
21. Relative Lempel-Ziv with Constant-Time Random Access.
22. Sequence Decision Diagrams.
23. Shortest Unique Queries on Strings.
24. Simple and Efficient String Algorithms for Query Suggestion Metrics Computation.
25. Strategic Pattern Search in Factor-Compressed Text.
26. Succinct Indexes for Reporting Discriminating and Generic Words.

STACS 2014

1. Data-Oblivious Data Structures.
2. Faster Compact On-Line Lempel-Ziv Factorization.
3. Faster Sparse Suffix Sorting.
4. Space-Efficient String Indexing for Wildcard Pattern Matching.
5. Testing Generalised Freeness of Words.
6. Weighted Coloring in Trees.

STOC 2014

1. Linear time construction of compressed text indices in compact space.
2. Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time.

SWAT 2014

1. B-slack Trees: Space Efficient B-Trees.
2. Colored Range Searching in Linear Space.
3. Expected Linear Time Sorting for Word Size Ω(log2 n loglogn).
4. Ranked Document Selection.

Stringology 2014

1. A Process-Oriented Implementation of Brzozowski’s DFA Construction Algorithm.
2. Alternative Algorithms for Lyndon Factorization.
3. Approximation of Greedy Algorithms for Max-ATSP, Maximal Compression, Maximal Cycle Cover, and Shortest Cyclic Cover of Strings.
4. Closed Factorization.
5. Computing Abelian Covers and Abelian Runs.
6. Efficient Online Abelian Pattern Matching in Strings by Simulating Reactive Multi-Automata.
7. Fast Regular Expression Matching Based On Dual Glushkov NFA.
8. Improved Two-Way Bit-parallel Search.
9. Metric Preserving Dense SIFT Compression.
10. Multiple Pattern Matching Revisited.
11. New Tabulation and Sparse Dynamic Programming Based Techniques for Sequence Similarity Problems.
12. On the Number of Distinct Squares.
13. Random Access to Fibonacci Codes.
14. Reducing Squares in Suffix Arrays.
15. Speeding up Compressed Matching with SBNDM2.
16. Threshold Approximate Matching in Grammar-Compressed Strings.
17. Two Simple Full-Text Indexes Based on the Suffix Array.
18. Two Squares Canonical Factorization.
19. Using Correctness-by-Construction to Derive Dead-zone Algorithms.

TFPIE 2014

1. Simple Balanced Binary Search Trees.

WABI 2014

1. Constructing String Graphs in External Memory.
2. Manifold de Bruijn Graphs.

WALCOM 2014

1. Alignment with Non-overlapping Inversions on Two Strings.

ACM J. Exp. Algorithmics 2014

1. General Document Retrieval in Compact Space.
2. Locally Compressed Suffix Arrays.

ACM Trans. Algorithms 2014

1. Alphabet-Independent Compressed Text Indexing.
2. Fully Functional Static and Dynamic Succinct Trees.

ACM Trans. Inf. Syst. 2014

1. XXS: Efficient XPath Evaluation on Compressed XML Documents.

Algorithmica 2014

1. A Framework for Succinct Labeled Ordinal Trees over Large Alphabets.
2. Efficient Fully-Compressed Sequence Representations.
3. Substring Range Reporting.

Algorithms 2014

1. High-Order Entropy Compressed Bit Vectors with Rank/Select.

Algorithms Mol. Biol. 2014

1. Fast algorithms for approximate circular string matching.
2. Optimal computation of all tandem repeats in a weighted sequence.

BMC Bioinform. 2014

1. Linear-time computation of minimal absent words using suffix array.

CoRR 2014

1. $LCSk$++: Practical similarity metric for long strings.
2. A Comparative Study on String Matching Algorithm of Biological Sequences.
3. A Fast String Matching Algorithm Based on Lowlight Characters in the Pattern.
4. A Parameterized Study of Maximum Generalized Pattern Matching Problems.
5. A Subquadratic Algorithm for Minimum Palindromic Factorization.
6. A Suffix Tree Or Not A Suffix Tree?
7. A massively parallel algorithm for constructing the BWT of large string sets.
8. A new characterization of maximal repetitions by Lyndon trees.
9. A note on multipivot Quicksort.
10. A note on the largest number of red nodes in red-black trees.
11. A really simple approximation of smallest grammar.
12. ARC Sort: Enhanced and Time Efficient Sorting Algorithm.
13. Algorithms in the Ultra-Wide Word Model.
14. Alternative Algorithms for Lyndon Factorization.
15. Analysis of Branch Misses in Quicksort.
16. Analysis of Pivot Sampling in Dual-Pivot Quicksort.
17. Analysis of String Sorting using Heapsort.
18. Approximating solution structure of the Weighted Sentence Alignment problem.
19. Average-Case Optimal Approximate Circular String Matching.
20. Binary Jumbled Pattern Matching via All-Pairs Shortest Paths.
21. Building a Balanced k-d Tree in O(kn log n) Time.
22. Combining pattern-based CRFs and weighted context-free grammars.
23. Compact Indexes for Flexible Top-k Retrieval.
24. Compact Subsequence Matching and Packed Tree Coloring.
25. Compression of high throughput sequencing data with probabilistic de Bruijn graph.
26. Compressive Mining: Fast and Optimal Data Mining in the Compressed Domain.
27. Computing Covers Using Prefix Tables.
28. Constructing String Graphs in External Memory.
29. Constructing small tree grammars and small circuits for formulas.
30. Covering Problems for Partial Words and for Indeterminate Strings.
31. Data Compaction - Compression without Decompression.
32. Dictionary Matching with One Gap.
33. Disk-based genome sequencing data compression.
34. Document Counting in Practice.
35. Document Retrieval on Repetitive Collections.
36. Dynamic Partial Sorting.
37. Efficient Compressed Wavelet Trees over Large Alphabets.
38. Efficient Representation for Online Suffix Tree Construction.
39. Efficient and Compact Representations of Prefix Codes.
40. Encodings of Range Maximum-Sum Segment Queries and Applications.
41. Engineering Parallel String Sorting.
42. Fast Algorithm for Partial Covers in Words.
43. Fast construction of FM-index for long sequence reads.
44. Faster Compressed Quadtrees.
45. Faster Language Edit Distance, Connection to All-pairs Shortest Paths and Related Problems.
46. Faster Sorting Networks for $17$, $19$ and $20$ Inputs.
47. Fewer runs than word length.
48. Fibonacci Heaps Revisited.
49. Fully Online Grammar Compression in Constant Space.
50. Fusion Tree Sorting.
51. GCD Computation of n Integers.
52. GPU-Accelerated BWT Construction for Large Collection of Short Reads.
53. How Fast Can We Multiply Large Integers on an Actual Computer?
54. How inefficient can a sort algorithm be?
55. Improved ESP-index: a practical self-index for highly repetitive texts.
56. Integer Set Compression and Statistical Modeling.
57. Introduction to Dynamic Unary Encoding.
58. Kernelization lower bound for Permutation Pattern Matching.
59. Lempel-Ziv Factorization May Be Harder Than Computing All Runs.
60. Linear time construction of compressed text indices in compact space.
61. Linear-time Computation of Minimal Absent Words Using Suffix Array.
62. Longest Common Extensions in Trees.
63. Longest Common Subsequence in k-length substrings.
64. Longest common substrings with k mismatches.
65. Mathematical Programming Strategies for Solving the Minimum Common String Partition Problem.
66. Most Recent Match Queries in On-Line Suffix Trees (with appendix).
67. Multilevel polynomial partitions and simplified range searching.
68. Multiple pattern matching revisited.
69. Normal, Abby Normal, Prefix Normal.
70. On Combinatorial Generation of Prefix Normal Words.
71. On Hardness of Jumbled Indexing.
72. On the Average-case Complexity of Pattern Matching with Wildcards.
73. On the representation of de Bruijn graphs.
74. Online Pattern Matching for String Edit Distance with Moves.
75. Online Repetition Detection With Backtracking.
76. Online Square Detection.
77. Optimal Encodings for Range Majority Queries.
78. Optimal Encodings for Range Min-Max and Top-k.
79. Optimal Time Random Access to Grammar-Compressed Strings in Small Space.
80. Parallel Wavelet Tree Construction.
81. Path algebra algorithm for finding longest increasing subsequence.
82. Pattern Matching and Local Alignment for RNA Structures.
83. PivotCompress: Compression by Sorting.
84. Practical Massively Parallel Sorting - Basic Algorithmic Ideas.
85. Quantum pattern matching fast on average.
86. Queries on LZ-Bounded Encodings.
87. Rank, select and access in grammar-compressed strings.
88. Reusing an FM-index.
89. Run-Length Encoded Nondeterministic KMP and Suffix Automata.
90. Sampling the suffix array with minimizers.
91. Searching and Indexing Genomic Databases via Kernelization.
92. Space-Efficient String Indexing for Wildcard Pattern Matching.
93. String Reconstruction from Substring Compositions.
94. Strong inapproximability of the shortest reset word.
95. Sublinear Space Algorithms for the Longest Common Substring Problem.
96. Suffix Arrays for Spaced-SNP Databases.
97. The Level Ancestor Problem in Practice.
98. The LevelArray: A Fast, Practical Long-Lived Renaming Algorithm.
99. Tight tradeoffs for approximating palindromes in streams.
100. Towards Tight Lower Bounds for Range Reporting on the RAM.
101. Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten).
102. Two simple full-text indexes based on the suffix array.
103. Variable-Order de Bruijn Graphs.
104. Wavelet Trees Meet Suffix Trees.
105. Weighted ancestors in suffix trees.
106. Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time.

Comput. Geom. 2014

1. Space efficient data structures for dynamic orthogonal range counting.

Discret. Appl. Math. 2014

1. A d-step approach to the maximum number of distinct squares and runs in strings.
2. A hybrid algorithm for the DNA sequencing problem.
3. A set-covering based heuristic algorithm for the periodic vehicle routing problem.
4. Algorithms for computing Abelian periods of words.
5. Algorithms for nesting with defects.
6. An ILP-refined tabu search for the Directed Profitable Rural Postman Problem.
7. Antichains and completely separating systems - A catalogue and applications.
8. Asymptotically optimal algorithms for geometric Max TSP and Max m-PSP.
9. Average number of occurrences of repetitions in a necklace.
10. Computing the number of cubic runs in standard Sturmian words.
11. Counting unique-sink orientations.
12. Cycle-aware minimization of acyclic deterministic finite-state automata.
13. Editorial.
14. Essential points of the n-cube subset partitioning characterisation.
15. Improving deduplication techniques by accelerating remainder calculations.
16. Improving heuristics for network modularity maximization using an exact algorithm.
17. Inferring strings from suffix trees and links on a binary alphabet.
18. Investigating the b-chromatic number of bipartite graphs by using the bicomplement.
19. Lower and upper bounds for the Bin Packing Problem with Fragile Objects.
20. Morphisms for resistive electrical networks.
21. New simple efficient algorithms computing powers and runs in strings.
22. On defensive alliances and strong global offensive alliances.
23. On the minimum size of 4-uniform hypergraphs without property B.
24. Partition into almost straight trails.
25. Polynomial-time algorithms for special cases of the maximum confluent flow problem.
26. Practical fixed length Lempel-Ziv coding.
27. Preface.
28. Rime: Repeat identification.
29. Scheduling arc maintenance jobs in a network to maximize total flow over time.
30. Simple tree pattern matching for trees in the prefix bar notation.
31. String matching with lookahead.
32. Stringology algorithms.
33. Text searching allowing for inversions and translocations of factors.
34. Tight and simple Web graph compression for forward and reverse neighbor queries.
35. Tilted Sperner families.
36. Triple arrays and related designs.
37. Unital designs with blocking sets.

IEEE Trans. Knowl. Data Eng. 2014

1. Large-Scale Pattern Search Using Reduced-Space On-Disk Suffix Arrays.

J. Comput. Syst. Sci. 2014

1. Range LCP.

J. Discrete Algorithms 2014

1. A subquadratic algorithm for minimum palindromic factorization.
2. Cross-document pattern matching.
3. Multi-pattern matching with bidirectional indexes.
4. Simple and efficient LZW-compressed multiple pattern matching.
5. Simple, compact and robust approximate string dictionary.
6. Time-space trade-offs for longest common extensions.
7. Wavelet trees for all.

Knowl. Inf. Syst. 2014

1. Compressed representations for web and social graphs.

Parallel Comput. 2014

1. Distributed text search using suffix arrays.

SIAM J. Comput. 2014

1. Optimal Dynamic Sequence Representations.

Softw. Pract. Exp. 2014

1. Optimized succinct data structures for massive data.

Theor. Comput. Sci. 2014

1. Closest periodic vectors in Lp spaces.
2. Compact q-gram profiling of compressed strings.
3. Detecting approximate periodic patterns.
4. Extending alignments with k-mismatches and ℓ-gaps.
5. Fast relative Lempel-Ziv self-index for similar sequences.
6. Less space: Indexing for queries with wildcards.
7. New space/time tradeoffs for top-k document retrieval on sequences.
8. Order-preserving matching.
9. Towards optimal packed string matching.

Theory Comput. Syst. 2014

1. String Indexing for Patterns with Wildcards.
2. Validating the Knuth-Morris-Pratt Failure Function, Fast and Online.

This site is open source. Improve this page.