StringologyTimes

Papers for stringologist (2019)

Contents

ALENEX 2019

  1. Lightweight Distributed Suffix Array Construction.

CIAC 2019

  1. The Parameterized Position Heap of a Trie.

CIKM 2019

  1. Improved Compressed String Dictionaries.

CPM 2019

  1. A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem.
  2. A New Class of Searchable and Provably Highly Compressible String Transformations.
  3. A Rearrangement Distance for Fully-Labelled Trees.
  4. Approximating Approximate Pattern Matching.
  5. Cartesian Tree Matching and Indexing.
  6. Compressed Multiple Pattern Matching.
  7. Computing Runs on a Trie.
  8. Computing the Antiperiod(s) of a String.
  9. Conversion from RLBWT to LZ77.
  10. Dichotomic Selection on Words: A Probabilistic Analysis.
  11. Entropy Lower Bounds for Dictionary Compression.
  12. Faster Queries for Longest Substring Palindrome After Block Edit.
  13. Finding a Small Number of Colourful Components.
  14. Front Matter, Table of Contents, Preface, Conference Organization.
  15. Fully-Functional Bidirectional Burrows-Wheeler Indexes and Infinite-Order De Bruijn Graphs.
  16. Hamming Distance Completeness.
  17. How to Exploit Periodicity (Invited Talk).
  18. Indexing the Bijective BWT.
  19. Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding.
  20. On Maximal Repeats in Compressed Strings.
  21. On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations.
  22. Online Algorithms for Constructing Linear-Size Suffix Trie.
  23. Optimal Rank and Select Queries on Dictionary-Compressed Text.
  24. Quasi-Linear-Time Algorithm for Longest Common Circular Factor.
  25. Quasi-Periodicity in Streams.
  26. Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to RNA Folding.
  27. Searching Long Repeats in Streams.
  28. Simulating the DNA Overlap Graph in Succinct Space.
  29. Some Variations on Lyndon Words (Invited Talk).
  30. Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform.
  31. Streaming Dictionary Matching with Mismatches.
  32. Stringology Combats Microbiological Threats (Invited Talk).
  33. Sufficient Conditions for Efficient Indexing Under Different Matchings.

DCC 2019

  1. A Compact Representation of Raster Time Series.
  2. A New Technique for Lossless Compression of Color Images Based on Hierarchical Prediction, Inversion and Context Adaptive Coding.
  3. BWT Tunnel Planning is Hard But Manageable.
  4. Better Than Optimal Huffman Coding?
  5. Constructing Antidictionaries in Output-Sensitive Space.
  6. Dv2v: A Dynamic Variable-to-Variable Compressor.
  7. Generalized Word Equations: A New Approach to Data Compresion.
  8. LZRR: LZ77 Parsing with Right Reference.
  9. Light Field Image Compression with Random Access.
  10. MR-RePair: Grammar Compression Based on Maximal Repeats.
  11. Multidimensional Compression with Pattern Matching.
  12. Numerical Pattern Mining Through Compression.
  13. On Lempel-Ziv Decompression in Small Space.
  14. On the Randomness of Compressed Data.
  15. Parameterized Text Indexing with One Wildcard.
  16. Practical Indexing of Repetitive Collections Using Relative Lempel-Ziv.
  17. RePair in Compressed Space and Time.
  18. Regular Expression Search on Compressed Text.
  19. Selective Dynamic Compression.
  20. Space-Efficient Computation of the Burrows-Wheeler Transform.
  21. Tunneling on Wheeler Graphs.
  22. Vectorizing Fast Compression.

DEXA (2) 2019

  1. Succinct BWT-Based Sequence Prediction.

DLT 2019

  1. Computing the k-binomial Complexity of the Thue-Morse Word.
  2. First Lower Bounds for Palindromic Length.
  3. On Palindromic Length of Sturmian Sequences.
  4. On the Length of Shortest Strings Accepted by Two-Way Finite Automata.
  5. Separating Many Words by Counting Occurrences of Factors.
  6. The Relative Edit-Distance Between Two Input-Driven Languages.
  7. k-Spectra of Weakly-c-Balanced Words.

ECML/PKDD (1) 2019

  1. String Sanitization: A Combinatorial Approach.

ESA 2019

  1. Bidirectional Text Compression in External Memory.
  2. Longest Common Substring Made Fully Dynamic.
  3. On the Hardness and Inapproximability of Recognizing Wheeler Graphs.
  4. Repetition Detection in a Dynamic String.

FCT 2019

  1. Circular Pattern Matching with k Mismatches.

FOCS 2019

  1. Approximation Algorithms for LCS and LIS with Truly Improved Running Times.
  2. Balancing Straight-Line Programs.
  3. Optimal Document Exchange and New Codes for Insertions and Deletions.
  4. Sublinear Algorithms for Gap Edit Distance.
  5. Why are Proof Complexity Lower Bounds Hard?

ICALP 2019

  1. Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps.
  2. Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication.

INNSBDDL (Tutorials) 2019

  1. Learned Data Structures.

ISAAC 2019

  1. An Improved Data Structure for Left-Right Maximal Generic Words Problem.
  2. Internal Dictionary Matching.
  3. On Approximate Range Mode and Range Selection.
  4. Top Tree Compression of Tries.

ITCS 2019

  1. Testing Local Properties of Arrays.

IWOCA 2019

  1. Burrows-Wheeler Transform of Words Defined by Morphisms.
  2. Finding Periods in Cartesian Tree Matching.
  3. Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings.

LATA 2019

  1. Automata over Infinite Sequences of Reals.
  2. Efficient Representation and Counting of Antipower Factors in Words.
  3. Generalized Register Context-Free Grammars.
  4. On the Maximum Number of Distinct Palindromic Sub-arrays.
  5. Palindromic Subsequences in Finite Words.
  6. Recurrence in Multidimensional Words.
  7. Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables.

MFCS 2019

  1. A Constant-Time Colored Choice Dictionary with Almost Robust Iteration.
  2. From Regular Expression Matching to Parsing.
  3. Indexing Graph Search Trees and Applications.
  4. RLE Edit Distance in Near Optimal Time.
  5. The Power Word Problem.
  6. Uniform Random Expressions Lack Expressivity.
  7. Upper Bounds on the Length of Minimal Solutions to Certain Quadratic Word Equations.

RECOMB 2019

  1. Efficient Construction of a Complete Index for Pan-Genomics Read Alignment.

SEA² 2019

  1. Searching for Best Karatsuba Recurrences.

SODA 2019

  1. Efficiently Approximating Edit Distance Between Pseudorandom Strings.
  2. Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts.
  3. List Decoding with Double Samplers.
  4. Lower Bounds for Oblivious Data Structures.
  5. Lower bounds for text indexing with mismatches and differences.
  6. Optimal Construction of Compressed Indexes for Highly Repetitive Texts.
  7. Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets.
  8. The streaming k-mismatch problem.

SOFSEM 2019

  1. On Infinite Prefix Normal Words.

SPIRE 2019

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

STACS 2019

  1. Constant-Time Retrieval with O(log m) Extra Bits.
  2. Depth First Search in the Semi-streaming Model.
  3. Fast and Longest Rollercoasters.

STOC 2019

  1. Local decodability of the Burrows-Wheeler transform.
  2. Optimal succinct rank data structure via approximate nonnegative tensor decomposition.
  3. String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure.

Stringology 2019

  1. k-Abelian Pattern Matching: Revisited, Corrected, and Extended.
  2. A Fast SIMD-Based Chunking Algorithm.
  3. Algorithms to Compute the Lyndon Array Revisited.
  4. An Improvement of the Franek-Jennings-Smyth Pattern Matching Algorithm.
  5. Bidirectional Adaptive Compression.
  6. Computing Maximal Palindromes and Distinct Palindromes in a Trie.
  7. Lexicalized Syntactic Analysis by Restarting Automata.
  8. Online Parameterized Dictionary Matching with One Gap.
  9. Optimal Time and Space Construction of Suffix Arrays and LCP Arrays for Integer Alphabets.
  10. Pattern Matching on Weighted Strings.
  11. Selective Dynamic Compression.
  12. Translating Between Wavelet Tree and Wavelet Matrix Construction.

WABI 2019

  1. Finding All Maximal Perfect Haplotype Blocks in Linear Time.

WADS 2019

  1. Dynamic Dictionary Matching in the Online Model.
  2. Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles.

WALCOM 2019

  1. Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index.

WORDS 2019

  1. Generalized Lyndon Factorizations of Infinite Words.
  2. Matching Patterns with Variables.
  3. Repetitions in Infinite Palindrome-Rich Words.

ACM J. Exp. Algorithmics 2019

  1. Better External Memory LCP Array Construction.

ACM Trans. Algorithms 2019

  1. Sparse Dynamic Programming on DAGs with Small Width.

ACM Trans. Inf. Syst. 2019

  1. Brotli: A General-Purpose Data Compressor.

Algorithmica 2019

  1. Can We Recover the Cover?
  2. Correction to: Longest Common Substring with Approximately k Mismatches.
  3. Fixed Block Compression Boosting in FM-Indexes: Theory and Practice.
  4. Longest Common Substring with Approximately k Mismatches.
  5. Mind the Gap! - Online Dictionary Matching with One Gap.
  6. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.

Algorithms 2019

  1. Compaction of Church Numerals.
  2. Space-Efficient Fully Dynamic DFS in Undirected Graphs.

Algorithms Mol. Biol. 2019

  1. External memory BWT and LCP computation for sequence collections with applications.
  2. Linear time minimum segmentation enables scalable founder reconstruction.
  3. Prefix-free parsing for building big BWTs.
  4. SNPs detection by eBWT positional clustering.

Bioinform. 2019

  1. A framework for space-efficient variable-order Markov models.
  2. Compressed filesystem for managing large genome collections.
  3. Fully-sensitive seed finding in sequence graphs using a hybrid index.

CoRR 2019

  1. 3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications.
  2. A Compact Representation of Raster Time Series.
  3. A Detailed Analysis of Quicksort Algorithms with Experimental Mathematics.
  4. A Memory-Efficient Sketch Method for Estimating High Similarities in Streaming Sets.
  5. A New Class of Searchable and Provably Highly Compressible String Transformations.
  6. A New Deterministic Algorithm for Dynamic Set Cover.
  7. A New Lower Bound for Semigroup Orthogonal Range Searching.
  8. A Simple Reduction for Full-Permuted Pattern Matching Problems on Multi-Track Strings.
  9. A Simple Solution to the Level-Ancestor Problem.
  10. A fast algorithm for constructing balanced binary search trees.
  11. A multidimensional analog to the Burrows-Wheeler transform.
  12. A randomized strategy in the mirror game.
  13. A study for Image compression using Re-Pair algorithm.
  14. A sub-quadratic algorithm for the longest common increasing subsequence problem.
  15. ALLSAT compressed with wildcards: Frequent Set Mining.
  16. Abelian periods of factors of Sturmian words.
  17. Abelian-square factors and binary words.
  18. About Fibonacci trees. I.
  19. Algorithms to compute the Burrows-Wheeler Similarity Distribution.
  20. An Average-Compress Algorithm for the Sample Mean Problem under Dynamic Time Warping.
  21. An Efficient Word Lookup System by using Improved Trie Algorithm.
  22. An Incompressibility Theorem for Automatic Complexity.
  23. An Index for Sequencing Reads Based on The Colored de Bruijn Graph.
  24. An efficient sorting algorithm - Ultimate Heapsort(UHS).
  25. An in-place, subquadratic algorithm for permutation inversion.
  26. Analyzing Trade-offs in Reversible Linear and Binary Search Algorithms.
  27. Apply Sorting Algorithms to FAST Problem.
  28. Approximate Similarity Search Under Edit Distance Using Locality-Sensitive Hashing.
  29. Approximating the Geometric Edit Distance.
  30. Balancing Straight-Line Programs.
  31. Belga B-trees.
  32. Beyond the Inverted Index.
  33. Bidirectional Text Compression in External Memory.
  34. Bloom filter variants for multiple sets: a comparative assessment.
  35. Borders, Palindrome Prefixes, and Square Prefixes.
  36. Cache-Friendly Search Trees; or, In Which Everything Beats std: : set.
  37. Cartesian Tree Matching and Indexing.
  38. Characteristic Parameters and Special Trapezoidal Words.
  39. Circ-Tree: A B+-Tree Variant with Circular Design for Persistent Memory.
  40. Circular Pattern Matching with k Mismatches.
  41. Communication cost of consensus for nodes with limited memory.
  42. Compact Data Structures for Shortest Unique Substring Queries.
  43. Compact Fenwick trees for dynamic ranking and selection.
  44. Compacted binary trees admit a stretched exponential.
  45. Competitive Online Search Trees on Trees.
  46. Compressed Indexes for Fast Search of Semantic Data.
  47. Compressed Range Minimum Queries.
  48. Computing runs on a trie.
  49. Constant Delay Traversal of Grammar-Compressed Graphs with Bounded Rank.
  50. Constant factor approximations to edit distance on far input pairs in nearly linear time.
  51. Constant-factor approximation of near-linear edit distance in near-linear time.
  52. Constrained Orthogonal Segment Stabbing.
  53. Constructing Antidictionaries in Output-Sensitive Space.
  54. Constructing the Bijective BWT.
  55. Conversion from RLBWT to LZ77.
  56. Convex Graph Invariant Relaxations For Graph Edit Distance.
  57. Counting Small Permutation Patterns.
  58. Data structures to represent sets of k-long DNA sequences.
  59. DeepCABAC: A Universal Compression Algorithm for Deep Neural Networks.
  60. Depth First Search in the Semi-streaming Model.
  61. Determining satisfiability of 3-SAT in polynomial time.
  62. Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets.
  63. Don’t Persist All : Efficient Persistent Data Structures.
  64. Dv2v: A Dynamic Variable-to-Variable Compressor.
  65. Dynamic Optimality Refuted - For Tournament Heaps.
  66. Dynamic Packed Compact Tries Revisited.
  67. Dynamic Palindrome Detection.
  68. Dynamic Partition Bloom Filters: A Bounded False Positive Solution For Dynamic Set Membership (Extended Abstract).
  69. Dynamic Path-Decomposed Tries.
  70. E2FM: an encrypted and compressed full-text index for collections of genomic sequences.
  71. ER-index: a referential index for encrypted genomic databases.
  72. Edge minimization in de Bruijn graphs.
  73. Efficient Online String Matching Based on Characters Distance Text Sampling.
  74. Efficient computation of the Jacobi symbol.
  75. Efficient processing of raster and vector data.
  76. Encoding 3SUM.
  77. Energy consumption in compact integer vectors: A study case.
  78. Engineering Faster Sorters for Small Sets of Items.
  79. Engineering Top-Down Weight-Balanced Trees.
  80. Entropy Bounds for Grammar-Based Tree Compressors.
  81. Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space.
  82. Enumerating Range Modes.
  83. Enumerative Data Compression with Non-Uniquely Decodable Codes.
  84. Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication.
  85. Every nonnegative real number is an abelian critical exponent.
  86. EvoZip: Efficient Compression of Large Collections of Evolutionary Trees.
  87. Exhaustive Exact String Matching: The Analysis of the Full Human Genome.
  88. Extending General Compact Querieable Representations to GIS Applications.
  89. Fast Cartesian Tree Matching.
  90. Fast Concurrent Data Sketches.
  91. Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series.
  92. Fast Fibonacci heaps with worst case extensions.
  93. Fast Multiple Pattern Cartesian Tree Matching.
  94. Fast Sequence Segmentation using Log-Linear Models.
  95. Fast hashing with Strong Concentration Bounds.
  96. Fast, Small, and Simple Document Listing on Repetitive Text Collections.
  97. Faster Dynamic Compressed d-ary Relations.
  98. Faster Integer Multiplication Using Preprocessing.
  99. Faster Privacy-Preserving Computation of Edit Distance with Moves.
  100. Faster Repetition-Aware Compressed Suffix Trees based on Block Trees.
  101. Faster and simpler algorithms for finding large patterns in permutations.
  102. Faster queries for longest substring palindrome after block edit.
  103. Finding First and Most-Beautiful Queens by Integer Programming.
  104. Finding monotone patterns in sublinear time.
  105. Finite test sets for morphisms which are square-free on some of Thue’s square-free ternary words.
  106. Flat combined Red Black Trees.
  107. Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses.
  108. Fully-functional bidirectional Burrows-Wheeler indexes.
  109. Gardens of Eden in the Game of Life.
  110. Generalized Dictionary Matching under Substring Consistent Equivalence Relations.
  111. Generalized de Bruijn words and the state complexity of conjugate sets.
  112. GraCT: A Grammar-based Compressed Index for Trajectory Data.
  113. Grammar Compressed Sequences with Rank/Select Support.
  114. Heuristic algorithms for the Longest Filled Common Subsequence Problem.
  115. How far away must forced letters be so that squares are still avoidable?
  116. How to Store a Random Walk.
  117. Implementing the Topological Model Succinctly.
  118. Improved Compressed String Dictionaries.
  119. Improved local search for graph edit distance.
  120. In Search of the Fastest Concurrent Union-Find Algorithm.
  121. In oder Aus.
  122. Indexing Graph Search Trees and Applications.
  123. Inducing the Lyndon Array.
  124. Internal Dictionary Matching.
  125. It is high time we let go of the Mersenne Twister.
  126. LISA: Towards Learned DNA Sequence Search.
  127. Learning Multi-dimensional Indexes.
  128. Learning Sublinear-Time Indexing for Nearest Neighbor Search.
  129. Lempel-Ziv-like Parsing in Small Space.
  130. Leyenda: An Adaptive, Hybrid Sorting Algorithm for Large Scale Data with Limited Memory.
  131. Lightweight merging of compressed indices based on BWT variants.
  132. Linear-size Suffix Tries for Parameterized Strings.
  133. Listing Conflicting Triples in Optimal Time.
  134. Local Decode and Update for Big Data Compression.
  135. Lock-Free Hopscotch Hashing.
  136. Longest Common Subsequence on Weighted Sequences.
  137. Loop Programming Practices that Simplify Quicksort Implementations.
  138. Lp Pattern Matching in a Stream.
  139. Lyndon words versus inverse Lyndon words: queries on suffixes and bordered words.
  140. Matching Patterns with Variables.
  141. Matching reads to many genomes with the r-index.
  142. Matching strings in encoded sequences.
  143. Memory Lower Bounds for Self-Stabilization.
  144. Mergeable Dictionaries With Shifts.
  145. Minimal Absent Words in Rooted and Unrooted Trees.
  146. Minimal Unique Substrings and Minimal Absent Words in a Sliding Window.
  147. Multiple Set Matching and Pre-Filtering with Bloom Multifilters.
  148. Multiplication method for factoring natural numbers.
  149. Nearly Optimal Static Las Vegas Succinct Dictionary.
  150. New Bounds on Antipowers in Binary Words.
  151. New Paths from Splay to Dynamic Optimality.
  152. New results on pseudosquare avoidance.
  153. Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements.
  154. On Approximate Range Mode and Range Selection.
  155. On Greedy Algorithms for Binary de Bruijn Sequences.
  156. On Huang and Wong’s Algorithm for Generalized Binary Split Trees.
  157. On Longest Common Property Preserved Substring Queries.
  158. On Occupancy Moments and Bloom Filter Efficiency.
  159. On Prefix-Sorting Finite Automata.
  160. On Slicing Sorted Integer Sequences.
  161. On dynamic succinct graph representations.
  162. On long words avoiding Zimin patterns.
  163. On the Average Case of MergeInsertion.
  164. On the Complexity of BWT-runs Minimization via Alphabet Reordering.
  165. On the Complexity of Exact Pattern Matching in Graphs: Binary Strings and Bounded Degree.
  166. On the Complexity of Exact Pattern Matching in Graphs: Determinism and Zig-Zag Matching.
  167. On the Hardness and Inapproximability of Recognizing Wheeler Graphs.
  168. On the Reproducibility of Experiments of Indexing Repetitive Document Collections.
  169. On the cyclic regularities of strings.
  170. Online Algorithms for Constructing Linear-size Suffix Trie.
  171. Optimal Adaptive Detection of Monotone Patterns.
  172. Optimal In-place Algorithms for Basic Graph Problems.
  173. Optimal Joins using Compact Data Structures.
  174. Order-Preserving Pattern Matching Indeterminate Strings.
  175. Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles.
  176. Padovan heaps.
  177. Palindromic Subsequences in Finite Words.
  178. Palindromic Ziv-Lempel and Crochemore Factorizations of m-Bonacci Infinite Words.
  179. Parallel Finger Search Structures.
  180. Parallel decompression of gzip-compressed files and random access to DNA sequences.
  181. Partial Sums on the Ultra-Wide Word RAM.
  182. Pinning Down the Strong Wilber 1 Bound for Binary Search Trees.
  183. Practical Repetition-Aware Grammar Compression.
  184. Prefix Block-Interchanges on Binary and Ternary Strings.
  185. Proving tree algorithms for succinct data structures.
  186. Pseudo-solutions of word equations.
  187. Quantum Computing: Lecture Notes.
  188. Quasi-Linear-Time Algorithm for Longest Common Circular Factor.
  189. QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations.
  190. Quotient Hash Tables - Efficiently Detecting Duplicates in Streaming Data.
  191. RAMBO: Repeated And Merged Bloom Filter for Multiple Set Membership Testing (MSMT) in Sub-linear time.
  192. RECIPE : Converting Concurrent DRAM Indexes to Persistent-Memory Indexes.
  193. RLE edit distance in near optimal time.
  194. Re-Pair In-Place.
  195. RecSplit: Minimal Perfect Hashing via Recursive Splitting.
  196. Reducing approximate Longest Common Subsequence to approximate Edit Distance.
  197. Repetitions in infinite palindrome-rich words.
  198. Resolution of the Burrows-Wheeler Transform Conjecture.
  199. Revisiting Consistent Hashing with Bounded Loads.
  200. Rpair: Rescaling RePair with Rsync.
  201. Run-Length Encoding in a Finite Universe.
  202. SOSD: A Benchmark for Learned Indexes.
  203. Selection on X1+X2+⋅⋅⋅ + Xm with layer-ordered heaps.
  204. Separate Chaining Meets Compact Hashing.
  205. Separating many words by counting occurrences of factors.
  206. Set Cover in Sub-linear Time.
  207. Shed More Light on Bloom Filter’s Variants.
  208. Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings.
  209. Simulating the DNA String Graph in Succinct Space.
  210. Sorted Top-k in Rounds.
  211. Space Efficient Algorithms for Breadth-Depth Search.
  212. Space Efficient Construction of Lyndon Arrays in Linear Time.
  213. Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform.
  214. Space-Efficient Construction of Compressed Suffix Trees.
  215. Space-Efficient Data Structures for Lattices.
  216. Space-efficient merging of succinct de Bruijn graphs.
  217. Sparse Regular Expression Matching.
  218. Speeding up the Karatsuba algorithm.
  219. Splaying Preorders and Postorders.
  220. Stack Sorting with Increasing and Decreasing Stacks.
  221. Stack sorting with restricted stacks.
  222. String Attractors and Combinatorics on Words.
  223. String Indexing with Compressed Patterns.
  224. String Sanitization: A Combinatorial Approach.
  225. String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure.
  226. String factorisations with maximum or minimum dimension.
  227. Sublinear Algorithms for Gap Edit Distance.
  228. Succinct Data Structures for Families of Interval Graphs.
  229. Succinct Representation for (Non)Deterministic Finite Automata.
  230. Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries.
  231. Superset Technique for Approximate Recovery in One-Bit Compressed Sensing.
  232. Survey of Information Encoding Techniques for DNA.
  233. Techniques for Inverted Index Compression.
  234. The Alternating BWT: an algorithmic perspective.
  235. The Bloom Clock.
  236. The One-Way Communication Complexity of Dynamic Time Warping Distance.
  237. The PGM-index: a multicriteria, compressed and learned approach to data indexing.
  238. The Parameterized Position Heap of a Trie.
  239. The Strong 3SUM-INDEXING Conjecture is False.
  240. The Tandem Duplication Distance is NP-hard.
  241. The Weak Circular Repetition Threshold Over Large Alphabets.
  242. The k-d tree data structure and a proof for neighborhood computation in expected logarithmic time.
  243. The power word problem.
  244. The repetition threshold for binary rich words.
  245. The smallest grammar problem revisited.
  246. Top Tree Compression of Tries.
  247. Towards Better Compressed Representations.
  248. Towards a Definitive Measure of Repetitiveness.
  249. Tree-Shape Grammars for Random Access.
  250. Unconstrained Church-Turing thesis cannot possibly be true.
  251. Weighted Shortest Common Supersequence Problem Revisited.
  252. What Storage Access Privacy is Achievable with Small Overhead?
  253. When a Dollar Makes a BWT.
  254. Words Avoiding Reversed Factors, Revisited.
  255. Words With Few Palindromes, Revisited.
  256. Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters.
  257. k-Spectra of c-Balanced Words.
  258. scaleBF: A High Scalable Membership Filter using 3D Bloom Filter.

Comput. J. 2019

  1. Context Sensitive Rewriting Codes for Flash Memory†.
  2. Edit Distance with Multiple Block Operations†.

Dagstuhl Reports 2019

  1. 25 Years of the Burrows-Wheeler Transform (Dagstuhl Seminar 19241).

IEEE Trans. Inf. Theory 2019

  1. RePair and All Irreducible Grammars are Upper Bounded by High-Order Empirical Entropy.

Inf. Comput. 2019

  1. Lempel-Ziv compressed structures for document retrieval.
  2. On-line weighted pattern matching.

Inf. Process. Lett. 2019

  1. Applying the Positional Burrows-Wheeler Transform to all-pairs Hamming distance.
  2. Comparison of LZ77-type parsings.

Inf. Sci. 2019

  1. GraCT: A Grammar-based Compressed Index for Trajectory Data.

Inf. Syst. 2019

  1. On the reproducibility of experiments of indexing repetitive document collections.

J. Comb. Optim. 2019

  1. Efficient enumeration of non-equivalent squares in partial words with few holes.

J. Comput. Syst. Sci. 2019

  1. Hide and seek with repetitions.

Rev. Socionetwork Strateg. 2019

  1. Storing Partitions of Integers in Sublinear Space.

SIAM J. Comput. 2019

  1. Bicriteria Data Compression.
  2. Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product.

SIAM J. Discret. Math. 2019

  1. Rollercoasters: Long Sequences without Short Runs.

Softw. Pract. Exp. 2019

  1. A compact index for order-preserving pattern matching.

Theor. Comput. Sci. 2019

  1. A substring-substring LCS data structure.
  2. Algorithms to compute the Burrows-Wheeler Similarity Distribution.
  3. Approximate cover of strings.
  4. Document listing on repetitive collections with guaranteed performance.
  5. Efficient dynamic dictionary matching with DAWGs and AC-automata.
  6. Improved upper bounds on all maximal α-gapped repeats and palindromes.
  7. Maximal common subsequence algorithms.
  8. On overabundant words and their application to biological sequence analysis.
  9. On the size of the smallest alphabet for Lyndon trees.
  10. Path queries on functions.
  11. Universal compressed text indexing.

Theory Comput. Syst. 2019

  1. Pattern Matching and Consensus Problems on Weighted Sequences and Profiles.
This site is open source. Improve this page.