StringologyTimes

SPIRE for Stringologist

SPIRE 2022

  1. KATKA: A KRAKEN-Like Tool with k Given at Query Time.
  2. Matching Patterns with Variables Under Edit Distance.
  3. Online Algorithms for Finding Distinct Substrings with Length and Multiple Prefix and Suffix Conditions.

SPIRE 2021

  1. Computing the Original eBWT Faster, Simpler, and with Less Memory.
  2. On the Approximation Ratio of LZ-End to LZ77.
  3. All Instantiations of the Greedy Algorithm for the Shortest Common Superstring Problem are Equivalent.
  4. Extracting the Sparse Longest Common Prefix Array from the Suffix Binary Search Tree.
  5. findere: Fast and Precise Approximate Membership Query.
  6. Longest Common Rollercoasters.
  7. An LMS-Based Grammar Self-index with Local Consistency Properties.
  8. Grammar Index by Induced Suffix Sorting.
  9. Improved Topic Modeling in Twitter Through Community Pooling.
  10. Exploiting Pseudo-locality of Interchange Distance.
  11. Position Heaps for Cartesian-Tree Matching on Strings and Tries.
  12. Lower Bounds for the Number of Repetitions in 2D Strings.
  13. A Separation of γ and b via Thue-Morse Words.
  14. String Covers of a Tree.
  15. On Stricter Reachable Repetitiveness Measures.
  16. r-Indexing the eBWT.
  17. Permutation-Constrained Common String Partitions with Applications.
  18. Minimal Unique Palindromic Substrings After Single-Character Substitution.
  19. Unicode at Gigabytes per Second.
  20. TSXor: A Simple Time Series Compression Algorithm.

SPIRE 2020

  1. Navigating Forest Straight-Line Programs in Constant Time.
  2. Efficient Enumeration of Distinct Factors Using Package Representations.
  3. Longest Square Subsequence Problem Revisited.
  4. Tailoring r-index for Document Listing Towards Metagenomics Applications.
  5. Computing Covers Under Substring Consistent Equivalence Relations.
  6. Approximating the Anticover of a String.
  7. Internal Quasiperiod Queries.
  8. A Comparison of Empirical Tree Entropies.
  9. On Repetitiveness Measures of Thue-Morse Words.
  10. Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction.
  11. Relative Lempel-Ziv Compression of Suffix Arrays.
  12. Efficient Construction of Hierarchical Overlap Graphs.
  13. Smaller Fully-Functional Bidirectional BWT Indexes.
  14. Lyndon Words, the Three Squares Lemma, and Primitive Squares.
  15. Multidimensional Period Recovery.
  16. An Efficient Elastic-Degenerate Text Index? Not Likely.
  17. Practical Random Access to SLP-Compressed Texts.
  18. Towards Efficient Interactive Computation of Dynamic Time Warping Distance.
  19. Pre-indexing Pruning Strategies.
  20. Contextual Pattern Matching.
  21. Measuring Controversy in Social Networks Through NLP.

SPIRE 2019

  1. Range Shortest Unique Substring Queries.
  2. Fast Identification of Heavy Hitters by Cached and Packed Group Testing.
  3. Lossless Image Compression Using List Update Algorithms.
  4. Minimal Absent Words in Rooted and Unrooted Trees.
  5. Weighted Shortest Common Supersequence Problem Revisited.
  6. Fast Cartesian Tree Matching.
  7. Fast, Small, and Simple Document Listing on Repetitive Text Collections.
  8. Online Algorithms on Antipowers and Antiperiods.
  9. Faster Dynamic Compressed d-ary Relations.
  10. BM25 Beyond Query-Document Similarity.
  11. Space-Efficient Merging of Succinct de Bruijn Graphs.
  12. Compact Data Structures for Shortest Unique Substring Queries.
  13. Adaptive Succinctness.
  14. COBS: A Compact Bit-Sliced Signature Index.
  15. Inducing the Lyndon Array.
  16. Faster Repetition-Aware Compressed Suffix Trees Based on Block Trees.
  17. On Longest Common Property Preserved Substring Queries.
  18. Polynomial-Delay Enumeration of Maximal Common Subsequences.
  19. Position Bias Estimation for Unbiased Learning-to-Rank in eCommerce Search.
  20. Searching Runs in Streams.
  21. SACABench: Benchmarking Suffix Array Construction.
  22. Space- and Time-Efficient Storage of LiDAR Point Clouds.
  23. Parallel External Memory Wavelet Tree and Wavelet Matrix Construction.
  24. Run-Length Encoding in a Finite Universe.
  25. Implementing the Topological Model Succinctly.
  26. An Index for Sequencing Reads Based on the Colored de Bruijn Graph.
  27. Bounds and Estimates on the Average Edit Distance.
  28. An Optimal Algorithm to Find Champions of Tournament Graphs.
  29. A Practical Alphabet-Partitioning Rank/Select Data Structure.
  30. Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets.
  31. Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings.
  32. Linear Time Maximum Segmentation Problems in Column Stream Model.
  33. A New Linear-Time Algorithm for Centroid Decomposition.
  34. Network-Based Pooling for Topic Modeling on Microblog Content.
  35. Rpair: Rescaling RePair with Rsync.
  36. On the Computation of Longest Previous Non-overlapping Factors.

SPIRE 2018

  1. Longest Property-Preserved Common Factor.
  2. Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays.
  3. Longest Common Prefixes with k-Errors and Applications.
  4. On Extended Special Factors of a Word.
  5. Block Palindromes: A New Generalization of Palindromes.
  6. Computing Burrows-Wheeler Similarity Distributions for String Collections.
  7. Efficient Computation of Sequence Mappability.
  8. Maximal Motif Discovery in a Sliding Window.
  9. Searching for a Modified Pattern in a Changing Text.
  10. Faster Recovery of Approximate Periods over Edit Distance.
  11. Compressed Communication Complexity of Longest Common Prefixes.

SPIRE 2017

  1. Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries.
  2. Tight Bounds for Top Tree Compression.
  3. LZ78 Compression in Low Main Memory Space.
  4. Detecting One-Variable Patterns.
  5. Optimal Skeleton Huffman Trees.
  6. Pattern Matching on Elastic-Degenerate Text with Errors.
  7. On Suffix Tree Breadth.
  8. Longest Common Factor After One Edit Operation.
  9. Fast Label Extraction in the CDAWG.
  10. Fast Construction of Compressed Web Graphs.
  11. Efficient Compression and Indexing of Trajectories.
  12. Order Preserving Pattern Matching on Trees and DAGs.
  13. A Self-index on Block Trees.
  14. On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation.
  15. Lightweight BWT and LCP Merging via the Gap Algorithm.
  16. Succinct Partial Sums and Fenwick Trees.
  17. Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression.
  18. Distinct Squares in Circular Words.

SPIRE 2016

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

SPIRE 2015

  1. Online Self-Indexed Grammar Compression.
  2. A Faster Algorithm for Computing Maximal \alpha -gapped Repeats in a String.
  3. Beyond the Runs Theorem.
  4. A Compact RDF Store Using Suffix Arrays.
  5. Relative Select.
  6. Efficient Algorithms for Longest Closed Factor Array.
  7. Range LCP Queries Revisited.
  8. Computing the Longest Unbordered Substring.
  9. Longest Common Prefix with Mismatches.
  10. Space-Efficient Detection of Unusual Words.
  11. Fast Online Lempel-Ziv Factorization in Compressed Space.
  12. Tight Bound for the Number of Distinct Palindromes in a Tree.

SPIRE 2014

  1. Relative FM-Indexes.
  2. Indexed Matching Statistics and Shortest Unique Substrings.
  3. Grammar Compressed Sequences with Rank/Select Support.
  4. Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on Run-Length Encoded Strings.
  5. Relative Lempel-Ziv with Constant-Time Random Access.
  6. Simple and Efficient String Algorithms for Query Suggestion Metrics Computation.
  7. Efficient Compressed Indexing for Approximate Top-k String Retrieval.
  8. Efficient Indexing and Representation of Web Access Logs.
  9. Fast Construction of Wavelet Trees.
  10. K 2-Treaps: Range Top-k Queries in Compact Space.
  11. Online Pattern Matching for String Edit Distance with Moves.
  12. Strategic Pattern Search in Factor-Compressed Text.

SPIRE 2013

  1. Space-Efficient Construction of the Burrows-Wheeler Transform.
  2. Faster Top-k Document Retrieval in Optimal Space.
  3. Document Listing on Versioned Documents.
  4. Adding Compression and Blended Search to a Compact Two-Level Suffix Array.
  5. A Lempel-Ziv Compressed Structure for Document Listing.
  6. Compact Querieable Representations of Raster Data.
  7. Minimal Discriminating Words Problem Revisited.
  8. Faster Lyndon Factorization Algorithms for SLP and LZ78 Compressed Text.
  9. Order-Preserving Incomplete Suffix Trees and Order-Preserving Indexes.
  10. Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs.
  11. Fully-Online Grammar Compression.

SPIRE 2012

  1. Grammar Precompression Speeds Up Burrows-Wheeler Compression.
  2. Computing Discriminating and Generic Words.
  3. Improved Grammar-Based Compressed Indexes.
  4. Smaller Self-indexes for Natural Language.
  5. Efficient LZ78 Factorization of Grammar Compressed Text.
  6. Dual-Sorted Inverted Lists in Practice.
  7. Faster Algorithm for Computing the Edit Distance between SLP-Compressed Strings.
  8. The Position Heap of a Trie.
  9. Compressed Suffix Trees for Repetitive Texts.
  10. Variable-Length Codes for Space-Efficient Grammar-Based Compression.
  11. Ranked Document Retrieval in (Almost) No Space.
  12. The Wavelet Matrix.

SPIRE 2011

  1. Fast q-gram Mining on SLP Compressed Strings.
  2. Approximate Regular Expression Matching with Multi-strings.
  3. Improved Compressed Indexes for Full-Text Document Retrieval.
  4. Computing All Subtree Repeats in Ordered Ranked Trees.
  5. Computing the Longest Common Prefix Array Based on the Burrows-Wheeler Transform.
  6. Finding Frequent Elements in Compressed 2D Arrays and Strings.
  7. Fixed Block Compression Boosting in FM-Indexes.
  8. COCA Filters: Co-occurrence Aware Bloom Filters.
  9. Reference Sequence Construction for Relative Compression of Genomes.
  10. ESP-Index: A Compressed Index Based on Edit-Sensitive Parsing.

SPIRE 2010

  1. Succinct Representations of Dynamic Strings.
  2. Counting and Verifying Maximal Palindromes.
  3. Dynamic Z-Fast Tries.
  4. Range Queries over Untangled Chains.
  5. Computing Matching Statistics and Maximal Exact Matches on Compressed Full-Text Indexes.
  6. String Matching with Variable Length Gaps.
  7. CST++.
  8. Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval.
  9. Colored Range Queries and Document Retrieval.
  10. Dual-Sorted Inverted Lists.

SPIRE 2009

  1. A Compressed Enhanced Suffix Array Supporting Fast String Matching.
  2. Directly Addressable Variable-Length Codes.
  3. Range Quantile Queries: Another Virtue of Wavelet Trees.
  4. A Linear-Time Burrows-Wheeler Transform Using Induced Sorting.
  5. Indexing Variable Length Substrings for Exact and Approximate Matching.
  6. k2-Trees for Compact Web Graph Representation.

SPIRE 2008

  1. Practical Rank/Select Queries over Arbitrary Sequences.
  2. Speeding Up Pattern Matching by Text Sampling.
  3. Context-Sensitive Grammar Transform: Compression and Pattern Matching.
  4. Self-indexing Natural Language.
  5. Improved Variable-to-Fixed Length Codes.
  6. Indexed Hierarchical Approximate String Matching.
  7. Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections.

SPIRE 2007

  1. A Fast and Compact Web Graph Representation.
  2. Implicit Compression Boosting with Applications to Self-indexing.
  3. Approximate String Matching with Lempel-Ziv Compressed Indexes.

SPIRE 2006

  1. Sparse Directed Acyclic Word Graphs.
  2. A Compressed Self-index Using a Ziv-Lempel Dictionary.
  3. Inverted Files Versus Suffix Arrays for Locating Patterns in Primary Memory.

SPIRE 2005

  1. Composite Pattern Discovery for PCR Application.

SPIRE 2004

  1. A Space-Saving Linear-Time Algorithm for Grammar-Based Compression.
  2. An Alphabet-Friendly FM-Index.
  3. First Huffman, Then Burrows-Wheeler: A Simple Alphabet-Independent FM-Index.
  4. Simple, Fast, and Efficient Natural Language Adaptive Compression..

SPIRE 2003

  1. SCM: Structural Contexts Model for Improving Compression in Semistructured Text Databases.
  2. A Practical Index for Genome Searching.
  3. Distributed Query Processing Using Suffix Arrays.
  4. A Bit-Parallel Suffix Automation Approach for (delta, gamma)-Matching in Music Retrieval.
  5. (S, C)-Dense Coding: An Optimized Compression Code for Natural Language Text Databases.
  6. Memory-Adaptive Dynamic Spatial Approximation Trees.
  7. Linear-Time Off-Line Text Compression by Longest-First Substitution.
  8. Flexible and Efficient Bit-Parallel Techniques for Transposition Invariant Approximate Matching in Music Retrieval.
  9. Large Edit Distance with Multiple Block Operations.

SPIRE 2002

  1. t-Spanners as a Data Structure for Metric Space Searching.
  2. Processing Text Files as Is: Pattern Matching over Compressed Texts, Multi-byte Character Texts, and Semi-structured Texts.
  3. Indexing Text Using the Ziv-Lempel Trie.
  4. Probabilistic Proximity Searching Algorithms Based on Compact Partitions.
  5. Compact Directed Acyclic Word Graphs for a Sliding Window.
  6. Fully Dynamic Spatial Approximation Trees.

SPIRE 2001

  1. Using Edit Distance in Point-Pattern Matching.
  2. On-Line Construction of Symmetric Compact Directed Acyclic Word Graphs.

SPIRE 2000

  1. Fast Multipattern Search Algorithms for Intrusion Detection.
  2. Fully Compressed Pattern Matching Algorithm for Balanced Straight-Line Programs.
  3. Online Construction of Subsequence Automata for Multiple Texts.
  4. Bit-Parallel Approach to Approximate String Matching in Compressed Texts.

SPIRE 1998

  1. A Model and a Visual Query Language for Structured Text.
  2. Direct Pattern Matching on Compressed Text.
  3. Fast Approximate String Matching in a Dictionary.
This site is open source. Improve this page.