StringologyTimes

Papers for stringologist (2010)

Contents

ALENEX 2010

  1. Succinct Trees in Practice.

Algorithms and Applications 2010

  1. A Parallel Algorithm for Fixed-Length Approximate String-Matching with k-mismatches.
  2. Extended Compact Web Graph Representations.
  3. Unified View of Backward Backtracking in Short Read Mapping.

BIBE 2010

  1. Compressed q-Gram Indexing for Highly Repetitive Biological Sequences.

BIBM 2010

  1. An algorithm for mapping short reads to a dynamically changing genomic sequence.

CPM 2010

  1. Approximate All-Pairs Suffix/Prefix Overlaps.
  2. Bidirectional Search in a String with Wavelet Trees.
  3. Parallel and Distributed Compressed Indexes.
  4. Succinct Dictionary Matching with No Slowdown.
  5. Verifying a Parameterized Border Array in O(n1.5) Time.

CSR 2010

  1. Validating the Knuth-Morris-Pratt Failure Function, Fast and Online.

DASFAA Workshops 2010

  1. An Improved Algorithm for Extracting Research Communities from Bibliographic Data.

DCC 2010

  1. A New Searchable Variable-to-Variable Compressor.
  2. A Pseudo-Random Number Generator Based on LZSS.
  3. A Similarity Measure Using Smallest Context-Free Grammars.
  4. Advantages of Shared Data Structures for Sequences of Balanced Parentheses.
  5. Bidirectional Delta Files.
  6. Efficient Algorithms for Constructing Optimal Bi-directional Context Sets.
  7. File-Size Preserving LZ Encoding for Reversible Data Embedding.
  8. I/O-Efficient Compressed Text Indexes: From Theory to Practice.
  9. LZ77-Like Compression with Fast Random Access.
  10. Local Modeling for WebGraph Compression.
  11. Lossless Compression of Maps, Charts, and Graphs via Color Separation.
  12. Lossless Data Compression via Substring Enumeration.
  13. Modelling Parallel Texts for Boosting Compression.
  14. Neural Markovian Predictive Compression: An Algorithm for Online Lossless Data Compression.
  15. On Computation of Performance Bounds of Optimal Index Assignment.
  16. Optimum String Match Choices in LZSS.
  17. Xampling: Analog Data Compression.
  18. gFPC: A Self-Tuning Compression Algorithm.

Discovery Science 2010

  1. Sparse Substring Pattern Set Discovery Using Linear Programming Boosting.

ER Workshops 2010

  1. Range Queries over a Compact Representation of Minimum Bounding Rectangles.

ESA (1) 2010

  1. A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings.
  2. Fast Prefix Search in Little Space, with Applications.
  3. Medium-Space Algorithms for Inverse BWT.
  4. On the Huffman and Alphabetic Tree Problem with General Cost Functions.

ESA (2) 2010

  1. Data Structures: Time, I/Os, Entropy, Joules!
  2. On Space Efficient Two Dimensional Range Minimum Data Structures.
  3. Top-k Ranked Document Search in General Text Databases.

FOCS 2010

  1. A Lower Bound for Dynamic Approximate Membership Data Structures.

FUN 2010

  1. A Fun Application of Compact Data Structures to Indexing Geographic Data.

ICALP (1) 2010

  1. Interval Sorting.
  2. Mergeable Dictionaries.
  3. Optimal Trade-Offs for Succinct String Indexes.

ICDE 2010

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

ISAAC (1) 2010

  1. Priority Range Trees.
  2. Should Static Search Trees Ever Be Unbalanced?

ISAAC (2) 2010

  1. Alphabet Partitioning for Compressed Rank/Select and Applications.
  2. Dynamic Range Reporting in External Memory.
  3. Efficient Indexes for the Positional Pattern Matching Problem and Two Related Problems over Small Alphabets.
  4. Entropy-Bounded Representation of Point Grids.
  5. Identifying Approximate Palindromes in Run-Length Encoded Strings.

IWOCA 2010

  1. Dictionary-Symbolwise Flexible Parsing.
  2. Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three.
  3. On the Maximal Sum of Exponents of Runsin a String.
  4. Skip Lift: A Probabilistic Alternative to Red-Black Trees.
  5. Worst Case Efficient Single and Multiple String Matching in the RAM Model.

LATA 2010

  1. A Fast Longest Common Subsequence Algorithm for Similar Strings.
  2. Abelian Square-Free Partial Words.
  3. Avoidable Binary Patterns in Partial Words.
  4. Choosing Word Occurrences for the Smallest Grammar Problem.
  5. Extending Stochastic Context-Free Grammars for an Application in Bioinformatics.
  6. Grammar-Based Compression in a Streaming Model.
  7. Hard Counting Problems for Partial Words.

LATIN 2010

  1. Compact Rich-Functional Binary Relation Representations.
  2. Fast Set Intersection and Two-Patterns Matching.
  3. Lightweight Data Indexing and Compression in External Memory.
  4. Optimal Succinctness for Range Minimum Queries.
  5. Sharp Separation and Applications to Exact and Parameterized Algorithms.

MFCS 2010

  1. Counting Dependent and Independent Strings.

SEA 2010

  1. Bit-Parallel Search Algorithms for Long Patterns.
  2. Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure.
  3. Practical Compressed Suffix Trees.

SODA 2010

  1. Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs.
  2. Cell-Probe Lower Bounds for Succinct Partial Sums.
  3. Counting Inversions, Offline Orthogonal Range Counting, and Related Problems.
  4. Data Structures for Range Minimum Queries in Multidimensional Arrays.
  5. Data-Specific Analysis of String Sorting.
  6. Deletion Without Rebalancing in Balanced Binary Trees.
  7. Fully-Functional Succinct Trees.
  8. Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities.
  9. On the Cell Probe Complexity of Dynamic Membership.
  10. Randomized Shellsort: A Simple Oblivious Sorting Algorithm.
  11. Regular Expression Matching with Multi-Strings and Intervals.

SOFSEM 2010

  1. Dynamic Edit Distance Table under a General Weighted Cost Function.
  2. Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays.
  3. Fast Arc-Annotated Subsequence Matching in Linear Space.
  4. Fast and Compact Prefix Codes.

SPIRE 2010

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

STACS 2010

  1. On Equations over Sets of Integers.

SWAT 2010

  1. An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times.

WABI 2010

  1. Swiftly Computing Center Strings.

WSDM 2010

  1. On compressing the textual web.

ACM J. Exp. Algorithmics 2010

  1. Practical approaches to reduce the space requirement of lempel-ziv-based compressed text indices.

ACM Trans. Algorithms 2010

  1. The compressed permuterm index.

ACM Trans. Embed. Comput. Syst. 2010

  1. Online memory compression for embedded systems.

ACM Trans. Inf. Syst. 2010

  1. Dynamic lightweight text compression.

ACM Trans. Web 2010

  1. Fast and Compact Web Graph Representations.

Algorithmica 2010

  1. On Sorting, Heaps, and Minimum Spanning Trees.

Algorithms Mol. Biol. 2010

  1. Linear-time protein 3-D structure searching with insertions and deletions.

Bioinform. 2010

  1. Efficient construction of an assembly string graph using the FM-index.

Discret. Appl. Math. 2010

  1. Sorting with networks of data structures.

IEICE Trans. Inf. Syst. 2010

  1. Context-Sensitive Grammar Transform: Compression and Pattern Matching.

Inf. Process. Lett. 2010

  1. Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem.

J. Comput. Biol. 2010

  1. Storage and Retrieval of Highly Repetitive Sequence Collections.

J. Discrete Algorithms 2010

  1. The longest common extension problem revisited and applications to approximate string searching.

Math. Comput. Sci. 2010

  1. Fast, Practical Algorithms for Computing All the Repeats in a String.

Theor. Comput. Sci. 2010

  1. Move-to-Front, Distance Coding, and Inversion Frequencies revisited.
  2. On compact representations of All-Pairs-Shortest-Path-Distance matrices.
This site is open source. Improve this page.