StringologyTimes

Papers for stringologist (2015)

Contents

ALENEX 2015

  1. A Data-Aware FM-index.
  2. Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions.
  3. Improved Single-Term Top-k Document Retrieval.

BCB 2015

  1. Fast and efficient compression of high-throughput sequencing reads.

BPOE 2015

  1. Stream-Based Lossless Data Compression Hardware Using Adaptive Frequency Table Management.

CIAC 2015

  1. An Opportunistic Text Indexing Structure Based on Run Length Encoding.

CPM 2015

  1. A Framework for Space-Efficient String Kernels.
  2. A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm.
  3. Alphabet-Dependent String Searching with Wexponential Search Trees.
  4. Combinatorial RNA Design: Designability and Structure-Approximating Algorithm.
  5. Compact Indexes for Flexible Top- k k Retrieval.
  6. Composite Repetition-Aware Data Structures.
  7. Dictionary Matching with Uneven Gaps.
  8. Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis.
  9. Encoding Nearest Larger Values.
  10. Encodings of Range Maximum-Sum Segment Queries and Applications.
  11. Fast String Dictionary Lookup with One Error.
  12. Greedy Conjecture for Strings of Length 4.
  13. Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem.
  14. LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding.
  15. Lempel Ziv Computation in Small Space (LZ-CISS).
  16. Longest Common Extensions in Sublinear Space.
  17. Longest Common Extensions in Trees.
  18. On Maximal Unbordered Factors.
  19. On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem.
  20. On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling.
  21. On the Readability of Overlap Digraphs.
  22. Online Detection of Repetitions with Backtracking.
  23. Parallel External Memory Suffix Sorting.
  24. Parameterized Complexity of Superstring Problems.
  25. Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process.
  26. Range Minimum Query Indexes in Higher Dimensions.
  27. Ranked Document Retrieval with Forbidden Pattern.
  28. Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints.
  29. Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree.
  30. Sorting by Cuts, Joins and Whole Chromosome Duplications.
  31. String Powers in Trees.
  32. Succinct Non-overlapping Indexing.
  33. The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets.
  34. Tighter Bounds for the Sum of Irreducible LCP Values.

DCC 2015

  1. Bi-Directional Context Modeling with Combinatorial Structuring for Genome Sequence Compression.
  2. Compressing Yahoo Mail.
  3. Compression for Similarity Identification: Computing the Error Exponent.
  4. Compression of Next Generation Sequencing Data.
  5. Compression-Aware Algorithms for Massive Datasets.
  6. Data Compression Cost Optimization.
  7. Document Counting in Compressed Space.
  8. Efficient Set Operations over k2-Trees.
  9. Enhanced Direct Access to Huffman Encoded Files.
  10. Faster Compressed Quadtrees.
  11. Geometric Compression of Orientation Signals for Fast Gesture Analysis.
  12. Improving PPM with Dynamic Parameter Updates.
  13. Incremental Locality and Clustering-Based Compression.
  14. On Probability Estimation via Relative Frequencies and Discount.
  15. OnlineRePair: A Recompressor for XML Structures.
  16. Parallel Wavelet Tree Construction.
  17. Queries on LZ-Bounded Encodings.
  18. Range Selection Queries in Data Aware Space and Time.
  19. Serializing RDF in Compressed Space.
  20. Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+.
  21. Universal Compression of Memoryless Sources over Large Alphabets via Independent Component Analysis.
  22. Variable-Order de Bruijn Graphs.

DEXA Workshops 2015

  1. Longest Previous Non-overlapping Factors Computation.

DLT 2015

  1. Diverse Palindromic Factorization Is NP-complete.
  2. Grammar-Based Tree Compression.
  3. Squareable Words.
  4. State Complexity of Neighbourhoods and Approximate Pattern Matching.
  5. Transfinite Lyndon Words.
  6. Unary Patterns with Permutations.

ESA 2015

  1. Access, Rank, and Select in Grammar-compressed Strings.
  2. Approximating LZ77 via Small-Space Multiple-Pattern Matching.
  3. Compressed Data Structures for Dynamic Sequences.
  4. Dictionary Matching in a Stream.

FCT 2015

  1. Longest α-Gapped Repeat and Palindrome.

FOCS 2015

  1. Pattern-Avoiding Access in Binary Search Trees.
  2. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.
  3. Tight Hardness Results for LCS and Other Sequence Similarity Measures.

ICALP (1) 2015

  1. Hollow Heaps.
  2. Optimal Encodings for Range Top- k k , Selection, and Min-Max.
  3. Replacing Mark Bits with Randomness in Fibonacci Heaps.

ISAAC 2015

  1. An In-place Framework for Exact and Approximate Shortest Unique Substring Queries.
  2. Inferring Strings from Full Abelian Periods.
  3. Multidimensional Range Selection.
  4. On the Succinct Representation of Unlabeled Permutations.
  5. Optimal Search Trees with 2-Way Comparisons.

IWOCA 2015

  1. Computing the BWT and the LCP Array in Constant Space.
  2. EERTREE: An Efficient Data Structure for Processing Palindromes in Strings.
  3. Longest Common Extensions in Partial Words.

LATA 2015

  1. Average Linear Time and Compressed Space Construction of the Burrows-Wheeler Transform.
  2. Average-Case Optimal Approximate Circular String Matching.
  3. Backward Linearised Tree Pattern Matching.
  4. Compressed Data Structures for Range Searching.
  5. Construction of a de Bruijn Graph for Assembly from a Truncated Suffix Tree.
  6. Coverability in Two Dimensions.
  7. Equation x^iy^jx^k=u^iv^ju^k in Words.
  8. On the Language of Primitive Partial Words.
  9. On the Number of Closed Factors in a Word.
  10. Online Computation of Abelian Runs.
  11. Square-Free Words over Partially Commutative Alphabets.

MFCS (1) 2015

  1. Longest Gapped Repeats and Palindromes.
  2. Strong Inapproximability of the Shortest Reset Word.

MFCS (2) 2015

  1. Faster Lightweight Lempel-Ziv Parsing.

PPAM (2) 2015

  1. Parallelising the Computation of Minimal Absent Words.

SEA 2015

  1. A Bulk-Parallel Priority Queue in External Memory with STXXL.
  2. Huffman Codes versus Augmented Non-Prefix-Free Codes.
  3. Parallel Construction of Succinct Trees.
  4. Tree Compression with Top Trees Revisited.

SODA 2015

  1. A new characterization of maximal repetitions by Lyndon trees.
  2. Approximate Range Emptiness in Constant Time and Optimal Space.
  3. Cell-probe bounds for online edit distance and other pattern matching problems.
  4. Internal Pattern Matching Queries in a Text and Applications.
  5. The amortized cost of finding the minimum.
  6. Wavelet Trees Meet Suffix Trees.

SPIRE 2015

  1. A Compact RDF Store Using Suffix Arrays.
  2. A Faster Algorithm for Computing Maximal \alpha -gapped Repeats in a String.
  3. Adaptive Computation of the Swap-Insert Correction Distance.
  4. Assessing the Efficiency of Suffix Stripping Approaches for Portuguese Stemming.
  5. Beyond the Runs Theorem.
  6. Chaining Fragments in Sequences: to Sweep or Not (Extended Abstract).
  7. Computing the Longest Unbordered Substring.
  8. DeShaTo: Describing the Shape of Cumulative Topic Distributions to Rank Retrieval Systems Without Relevance Judgments.
  9. Efficient Algorithms for Longest Closed Factor Array.
  10. Efficient Term Set Prediction Using the Bell-Wigner Inequality.
  11. Evaluating Geographical Knowledge Re-Ranking, Linguistic Processing and Query Expansion Techniques for Geographical Information Retrieval.
  12. Fast Online Lempel-Ziv Factorization in Compressed Space.
  13. Faster Exact Search Using Document Clustering.
  14. Feasibility of Word Difficulty Prediction.
  15. Filtration Algorithms for Approximate Order-Preserving Matching.
  16. Fishing in Read Collections: Memory Efficient Indexing for Sequence Assembly.
  17. How Big is that Genome? Estimating Genome Size and Coverage from k-mer Abundance Spectra.
  18. Improved Practical Compact Dynamic Tries.
  19. Induced Sorting Suffixes in External Memory with Better Design and Less Space.
  20. Longest Common Prefix with Mismatches.
  21. On Prefix/Suffix-Square Free Words.
  22. Online Self-Indexed Grammar Compression.
  23. Parallel Construction of Succinct Representations of Suffix Tree Topologies.
  24. Prefix and Suffix Reversals on Strings.
  25. Range LCP Queries Revisited.
  26. Relative Select.
  27. Sampling the Suffix Array with Minimizers.
  28. Selective Labeling and Incomplete Label Mitigation for Low-Cost Evaluation.
  29. ShRkC: Shard Rank Cutoff Prediction for Selective Search.
  30. Space-Efficient Detection of Unusual Words.
  31. Temporal Analysis of CHAVE Collection.
  32. Temporal Query Classification at Different Granularities.
  33. Tight Bound for the Number of Distinct Palindromes in a Tree.
  34. Transforming XML Streams with References.

STACS 2015

  1. Lempel-Ziv Factorization May Be Harder Than Computing All Runs.
  2. Pattern Matching with Variables: Fast Algorithms and New Hardness Results.
  3. Space-efficient Basic Graph Algorithms.

STOC 2015

  1. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false).

Stringology 2015

  1. A Faster Longest Common Extension Algorithm on Compressed Strings and its Applications.
  2. A Formal Framework for Stringology.
  3. Alternative Algorithms for Order-Preserving Matching.
  4. An Efficient Skip-Search Approach to the Order-Preserving Pattern Matching Problem.
  5. Combinatorics of the Interrupted Period.
  6. Computing Left-Right Maximal Generic Words.
  7. Controlling the Chunk-Size in Deduplication Systems.
  8. Efficient Algorithm for δ-Approximate Jumbled Pattern Matching.
  9. Enhanced Extraction from Huffman Encoded Files.
  10. Parameterized Matching: Solutions and Extensions.
  11. Quantum Leap Pattern Matching.
  12. Refined Tagging of Complex Verbal Phrases for the Italian Language.
  13. Tuning Algorithms for Jumbled Matching.

WABI 2015

  1. Bloom Filter Trie - A Data Structure for Pan-Genome Storage.
  2. Circular Sequence Comparison with q-grams.
  3. Optimizing Read Reversals for Sequence Compression - (Extended Abstract).

WADS 2015

  1. Universal Reconstruction of a String.

WALCOM 2015

  1. A Practical Succinct Data Structure for Tree-Like Graphs.
  2. Non-repetitive Strings over Alphabet Lists.

WORDS 2015

  1. Arithmetics on Suffix Arrays of Fibonacci Words.
  2. Linear-Time Computation of Prefix Table for Weighted Strings.

WWW 2015

  1. Compressed Indexes for String Searching in Labeled Graphs.

ACM Trans. Algorithms 2015

  1. Optimal Lower and Upper Bounds for Representing Sequences.

Algorithmica 2015

  1. Binary Jumbled Pattern Matching on Trees and Tree-Like Structures.
  2. Fast Algorithm for Partial Covers in Words.
  3. Improved Space-Time Tradeoffs for Approximate Full-Text Indexing with One Edit Error.
  4. Linked Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space.
  5. Space-Time Trade-offs for Stack-Based Algorithms.

BMC Bioinform. 2015

  1. Fast randomized approximate string matching with succinct hash data structures.

Bioinform. 2015

  1. MEGAHIT: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph.
  2. Ultrafast SNP analysis using the Burrows-Wheeler transform of short-read data.

CoRR 2015

  1. A Bloom filter based semi-index on q-grams.
  2. A Compressed-Gap Data-Aware Measure for Indexable Dictionaries.
  3. A Fast Heuristic for Exact String Matching.
  4. A Lower Bound on Supporting Predecessor Search in k sorted Arrays.
  5. A Note on Easy and Efficient Computation of Full Abelian Periods of a Word.
  6. A Practical O(Rlog log n+n) time Algorithm for Computing the Longest Common Subsequence.
  7. A Quadratic Assignment Formulation of the Graph Edit Distance.
  8. A Review on the Tree Edit Distance Problem and Related Path-Decomposition Algorithms.
  9. A Study on Splay Trees.
  10. A framework for space-efficient string kernels.
  11. A note on the longest common Abelian factor problem.
  12. A numerical analysis of Quicksort: How many cases are bad cases?
  13. Adaptive Search over Sorted Sets.
  14. Algorithms for Longest Common Abelian Factors.
  15. Amortized Rotation Cost in AVL Trees.
  16. An Efficient Dynamic Programming Algorithm for STR-IC-SEQ-EC-LCS Problem.
  17. An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring inclusive constraints.
  18. Approximating LZ77 in Small Space.
  19. Approximating LZ77 via Small-Space Multiple-Pattern Matching.
  20. Binary Coding in Stream.
  21. Burrows-Wheeler transform for terabases.
  22. Communication Complexity (for Algorithm Designers).
  23. Composite repetition-aware data structures.
  24. Compressed Data Structures for Dynamic Sequences.
  25. Compressed Tree Canonization.
  26. Computing LZ77 in Run-Compressed Space.
  27. Computing Runs on a General Alphabet.
  28. Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets.
  29. Deterministic Sparse Suffix Sorting on Rewritable Texts.
  30. Dictionary matching in a stream.
  31. Diverse Palindromic Factorization is NP-Complete.
  32. Dual pivot Quicksort.
  33. Dynamic Data Structures for Document Collections and Graphs.
  34. Dynamic Relative Compression.
  35. Dynamic concurrent van Emde Boas array.
  36. Dynamic index, LZ factorization, and LCE queries in compressed space.
  37. Efficient Algorithms for the Order Preserving Pattern Matching Problem.
  38. Efficient Deterministic Single Round Document Exchange for Edit Distance.
  39. Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence.
  40. Efficiently Finding All Maximal $α$-gapped Repeats.
  41. Enhanced Covers of Regular & Indeterminate Strings using Prefix Tables.
  42. Error Tree: A Tree Structure for Hamming & Edit Distances & Wildcards Matching.
  43. External Memory Three-Sided Range Reporting and Top-$k$ Queries with Sublogarithmic Updates.
  44. FM-index for dummies.
  45. Fast Algorithms for Exact String Matching.
  46. Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations.
  47. Fast Average-Case Pattern Matching on Weighted Sequences.
  48. Fast Computation of Abelian Runs.
  49. Fast and Powerful Hashing using Tabulation.
  50. Fast and Vectorizable Alternatives to Binary Search.
  51. Faster Lightweight Lempel-Ziv Parsing.
  52. Finding the Leftmost Critical Factorization on Unordered Alphabet.
  53. Finger Search, Random Access, and Longest Common Extensions in Grammar-Compressed Strings.
  54. Full-text and Keyword Indexes for String Searching.
  55. Fully-online construction of suffix trees and DAWGs for multiple texts.
  56. How Good is Multi-Pivot Quicksort?
  57. Implementation of BT-trees.
  58. Layered Heaps Beating Standard and Fibonacci Heaps in Practice.
  59. Lempel Ziv Computation In Compressed Space (LZ-CICS).
  60. Lempel Ziv Computation In Small Space (LZ-CISS).
  61. Linear Algorithm for Conservative Degenerate Pattern Matching.
  62. Linear Algorithms for Computing the Lyndon Border Array and the Lyndon Suffix Array.
  63. Linear-Time Sequence Comparison Using Minimal Absent Words & Applications.
  64. Linear-Time Superbubble Identification Algorithm.
  65. Longest Common Extensions in Sublinear Space.
  66. Longest Gapped Repeats and Palindromes.
  67. Lower bounds for approximation schemes for Closest String.
  68. Mespotine-RLE-basic v0.9 - An overhead-reduced and improved Run-Length-Encoding Method.
  69. Multiple sequence alignment for short sequences.
  70. On Longest Repeat Queries.
  71. On Maximal Unbordered Factors.
  72. On The Average-Case Complexity of Shellsort.
  73. On the Greedy Algorithm for the Shortest Common Superstring Problem with Reversals.
  74. Online Computation of Abelian Runs.
  75. Online Dictionary Matching with One Gap.
  76. Online Self-Indexed Grammar Compression.
  77. Optimal Dynamic Strings.
  78. Optimal search trees with equality tests.
  79. Parallel Query in the Suffix Tree.
  80. Parameterized Complexity of Superstring Problems.
  81. Pattern-avoiding access in binary search trees.
  82. Permutations sortable by two stacks in series.
  83. Practical Concurrent Priority Queues.
  84. Probabilistic Threshold Indexing for Uncertain Strings.
  85. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.
  86. Quadratic-Time Hardness of LCS and other Sequence Similarity Measures.
  87. Range Predecessor and Lempel-Ziv Parsing.
  88. Read Mapping on de Bruijn graph.
  89. Relative Compressed Suffix Trees.
  90. Relative Select.
  91. Space-efficient detection of unusual words.
  92. Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time.
  93. Subsequence Automata with Default Transitions.
  94. Testing k-binomial equivalence.
  95. The Complexity of Pattern Matching for 321-Avoiding and Skew-Merged Permutations.
  96. The complexity of computation in bit streams.
  97. The k-mismatch problem revisited.
  98. Traversing Grammar-Compressed Trees with Constant Delay.
  99. Tree Compression with Top Trees Revisited.
  100. Tree compression using string grammars.
  101. Triple State QuickSort, A replacement for the C/C++ library qsort.

IEEE Trans. Inf. Theory 2015

  1. Efficient and Compact Representations of Prefix Codes.

Inf. Comput. 2015

  1. Approximate periodicity.
  2. Detecting regularities on grammar-compressed strings.
  3. Tree compression with top trees.

Inf. Process. Lett. 2015

  1. Constructing LZ78 tries and position heaps in linear time for large alphabets.

Inf. Syst. 2015

  1. The wavelet matrix: An efficient wavelet tree for large alphabets.

J. Discrete Algorithms 2015

  1. A suffix tree or not a suffix tree?
  2. An efficient Variable-to-Fixed length encoding using multiplexed parse trees.
  3. Approximate pattern matching in LZ77-compressed texts.
  4. Bottom-k document retrieval.
  5. Computing the Burrows-Wheeler transform in place and in small space.
  6. Dynamic edit distance table under a general weighted cost function.
  7. Improved and extended locating functionality on compressed suffix arrays.

Knowl. Inf. Syst. 2015

  1. Compressed vertical partitioning for efficient RDF management.

SIAM J. Comput. 2015

  1. Random Access to Grammar-Compressed Strings and Trees.

SIAM J. Discret. Math. 2015

  1. String Reconstruction from Substring Compositions.

Softw. Pract. Exp. 2015

  1. Fast in-memory XPath search using compressed indexes.

Theor. Comput. Sci. 2015

  1. Compressed automata for dictionary matching.
  2. Dictionary matching with a few gaps.
  3. Global and local sequence alignment with a bounded number of gaps.
  4. On hardness of several string indexing problems.
This site is open source. Improve this page.