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. Alphabet-Dependent String Searching with Wexponential Search Trees.
  3. Compact Indexes for Flexible Top- k k Retrieval.
  4. Composite Repetition-Aware Data Structures.
  5. LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding.
  6. Lempel Ziv Computation in Small Space (LZ-CISS).
  7. Longest Common Extensions in Sublinear Space.
  8. Longest Common Extensions in Trees.
  9. On Maximal Unbordered Factors.
  10. Online Detection of Repetitions with Backtracking.
  11. Parallel External Memory Suffix Sorting.
  12. Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints.
  13. Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree.
  14. 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. Beyond the Runs Theorem.
  4. Computing the Longest Unbordered Substring.
  5. Efficient Algorithms for Longest Closed Factor Array.
  6. Fast Online Lempel-Ziv Factorization in Compressed Space.
  7. Longest Common Prefix with Mismatches.
  8. Online Self-Indexed Grammar Compression.
  9. Range LCP Queries Revisited.
  10. Relative Select.
  11. Space-Efficient Detection of Unusual Words.
  12. Tight Bound for the Number of Distinct Palindromes in a Tree.

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).

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.

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.