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. A Compact Representation of Nondeterministic (Suffix) Automata for the Bit-Parallel Approach.
  2. A Minimal Periods Algorithm with Applications.
  3. Affine Image Matching Is Uniform TC0-Complete.
  4. Algorithms for Forest Pattern Matching.
  5. Algorithms for Three Versions of the Shortest Common Superstring Problem.
  6. Approximate All-Pairs Suffix/Prefix Overlaps.
  7. Bidirectional Search in a String with Wavelet Trees.
  8. Bounds on the Minimum Mosaic of Population Sequences under Recombination.
  9. Breakpoint Distance and PQ-Trees.
  10. Building the Minimal Automaton of A*X in Linear Time, When X Is of Bounded Cardinality.
  11. Compression, Indexing, and Retrieval for Massive String Data.
  12. Cover Array String Reconstruction.
  13. Extended Islands of Tractability for Parsimony Haplotyping.
  14. Extension and Faster Implementation of the GRP Transform for Lossless Compression.
  15. Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks.
  16. Finding Optimal Alignment and Consensus of Circular Strings.
  17. Implicit Hitting Set Problems and Multi-genome Alignment.
  18. Mod/Resc Parsimony Inference.
  19. Old and New in Stringology.
  20. On the Parameterized Complexity of Some Optimization Problems Related to Multiple-Interval Graphs.
  21. Optimizing Restriction Site Placement for Synthetic Genomes.
  22. Parallel and Distributed Compressed Indexes.
  23. Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
  24. Pseudo-realtime Pattern Matching: Closing the Gap.
  25. Sampled Longest Common Prefix Array.
  26. Small-Space 2D Compressed Dictionary Matching.
  27. Succinct Dictionary Matching with No Slowdown.
  28. Succinct Representations of Separable Graphs.
  29. The Highest Expected Reward Decoding for HMMs with Application to Recombination Detection.
  30. The Property Suffix Tree with Dynamic Properties.
  31. 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. A PTAS for the Square Tiling Problem.
  2. A Self-Supervised Approach for Extraction of Attribute-Value Pairs from Wikipedia Articles.
  3. Algorithms for Finding a Minimum Repetition Representation of a String.
  4. Approximate String Matching with Stuck Address Bits.
  5. CST++.
  6. Colored Range Queries and Document Retrieval.
  7. Compressed Self-indices Supporting Conjunctive Queries on Document Collections.
  8. Computing Matching Statistics and Maximal Exact Matches on Compressed Full-Text Indexes.
  9. Counting and Verifying Maximal Palindromes.
  10. Dual-Sorted Inverted Lists.
  11. Dynamic Z-Fast Tries.
  12. Evaluation of Query Performance Prediction Methods by Range.
  13. Extracting Powers and Periods in a String from Its Runs Structure.
  14. Fast Bit-Parallel Matching for Network and Regular Expressions.
  15. Faster Compressed Dictionary Matching.
  16. Fingerprinting Ratings for Collaborative Filtering - Theoretical and Empirical Analysis.
  17. Finite Automata Based Algorithms for the Generalized Constrained Longest Common Subsequence Problems.
  18. Hypergeometric Language Model and Zipf-Like Scoring Function for Web Document Similarity Retrieval.
  19. Identifying SNPs without a Reference Genome by Comparing Raw Reads.
  20. Improved Fast Similarity Search in Dictionaries.
  21. Incremental Algorithms for Effective and Efficient Query Recommendation.
  22. Mining Large Query Induced Graphs towards a Hierarchical Query Folksonomy.
  23. Multiplication Algorithms for Monge Matrices.
  24. On Shortest Common Superstring and Swap Permutations.
  25. On Tag Spell Checking.
  26. On the Hardness of Counting and Sampling Center Strings.
  27. Parameterized Searching with Mismatches for Run-Length Encoded Strings - (Extended Abstract).
  28. Querying the Web Graph - (Invited Talk).
  29. Range Queries over Untangled Chains.
  30. Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval.
  31. Restricted LCS.
  32. Standard Deviation as a Query Hardness Estimator.
  33. String Matching with Variable Length Gaps.
  34. String Retrieval for Multi-pattern Queries.
  35. Succinct Representations of Dynamic Strings.
  36. Temporal Analysis of Document Collections: Framework and Applications.
  37. Text Comparison Using Soft Cardinality.
  38. The Gapped Suffix Array: A New Index Structure for Fast Approximate Matching.
  39. Training Parse Trees for Efficient VF Coding.
  40. Using Related Queries to Improve Web Search Results Ranking.
  41. Why Large Closest String Instances Are Easy to Solve in Practice.

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.

Stringology 2010

  1. (In)approximability Results for Pattern Matching Problems.
  2. A Space-Efficient Implementation of the Good-Suffix Heuristic.
  3. Approximate String Matching Allowing for Inversions and Translocations.
  4. Average Number of Runs and Squares in Necklace.
  5. Binary Image Compression via Monochromatic Pattern Substitution: Effectiveness and Scalability.
  6. Bounded Number of Squares in Infinite Repetition-Constrained Binary Words.
  7. Formal Characterizations of FA-based String Processors.
  8. Improving Automata Efficiency by Stretching and Jamming.
  9. Inferring Strings from Runs.
  10. New Simple Efficient Algorithms Computing Powers and Runs in Strings.
  11. On the Complexity of Variants of the k Best Strings Problem.
  12. Practical Fixed Length Lempel Ziv Coding.
  13. Reactive Links to Save Automata States.
  14. Simple Tree Pattern Matching for Trees in the Prefix Bar Notation.
  15. The Number of Runs in a Ternary Word.
  16. Tight and Simple Web Graph Compression.
  17. Tiling Binary Matrices in Haplotyping: Complexity, Models and Algorithms.

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.

CoRR 2010

  1. An Efficient Algorithm For Chinese Postman Walk on Bi-directed de Bruijn Graphs
  2. Compressed random access memory
  3. Counting Colours in Compressed Strings
  4. Document Clustering with K-tree
  5. Dynamic Range Reporting in External Memory
  6. Efficient Parallel and Out of Core Algorithms for Constructing Large Bi-directed de Bruijn Graphs
  7. Exact Analysis of Pattern Matching Algorithms with Probabilistic Arithmetic Automata
  8. Fully Dynamic Data Structure for Top-k Queries on Uncertain Data
  9. K-tree: Large Scale Document Clustering
  10. LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations
  11. Lightweight LCP-Array Construction in Linear Time
  12. Mergeable Dictionaries
  13. New Algorithms on Wavelet Trees and Applications to Information Retrieval
  14. On Finding Frequent Patterns in Directed Acyclic Graphs
  15. On the Border Length Minimization Problem (BLMP) on a Square Array
  16. Optimal Trade-Off for Succinct String Indexes
  17. Parallelization of Weighted Sequence Comparison by using EBWT
  18. Pattern Kits
  19. Permuted Common Supersequence
  20. Random Access to Grammar Compressed Strings
  21. Random Indexing K-tree
  22. Range Reporting for Moving Points on a Grid
  23. Sampled Longest Common Prefix Array
  24. Should Static Search Trees Ever Be Unbalanced?
  25. Some long-period random number generators using shifts and xors
  26. Succinct Data Structures for Assembling Large Genomes
  27. Succinct Dictionary Matching With No Slowdown
  28. Succinct Representations of Dynamic Strings
  29. The B-Skip-List: A Simpler Uniquely Represented Alternative to B-Trees
  30. The universality of iterated hashing over variable-length strings
  31. Tight and simple Web graph compression
  32. Top-K Color Queries for Document Retrieval
  33. Tree structure compression with RePair
  34. Unified Compression-Based Acceleration of Edit-Distance Computation
  35. Uses of randomness in computation
  36. Worst case efficient single and multiple string matching in the Word-RAM model

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.