String Processing and Information Retrieval : 21st International Symposium, SPIRE 2014, Ouro Preto, Brazil, October 20-22, 2014, Proceedings

This book constitutes the proceedings of the 21st International Symposium on String Processing and Information Retrieval, SPIRE 2014, held in Ouro Preto, Brazil, in October 2014. The 20 full and 6 short papers included in this volume were carefully reviewed and selected from 45 submissions. The papers focus not only on fundamental algorithms in string processing and information retrieval, but address also application areas such as computational biology, Web mining and recommender systems. They are organized in topical sections on compression, indexing, genome and related topics, sequences and strings, search, as well as on mining and recommending. Front Matter....Pages - Strategic Pattern Search in Factor-Compressed Text....Pages 1-12 Relative Lempel-Ziv with Constant-Time Random Access....Pages 13-17 Efficient Compressed Indexing for Approximate Top- k String Retrieval....Pages 18-30 Grammar Compressed Sequences with Rank/Select Support....Pages 31-44 Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on Run-Length Encoded Strings....Pages 45-51 Relative FM-Indexes....Pages 52-64 Efficient Indexing and Representation of Web Access Logs....Pages 65-76 A Compressed Suffix-Array Strategy for Temporal-Graph Indexing....Pages 77-88 Succinct Indexes for Reporting Discriminating and Generic Words....Pages 89-100 Fast Construction of Wavelet Trees....Pages 101-110 Order Preserving Prefix Tables....Pages 111-116 Alphabet-Independent Algorithms for Finding Context-Sensitive Repeats in Linear Time....Pages 117-128 A 3-Approximation Algorithm for the Multiple Spliced Alignment Problem and Its Application to the Gene Prediction Task....Pages 129-138 Improved Filters for the Approximate Suffix-Prefix Overlap Problem....Pages 139-148 Sequence Decision Diagrams....Pages 149-160 Shortest Unique Queries on Strings....Pages 161-172 Online Multiple Palindrome Pattern Matching....Pages 173-178 Indexed Matching Statistics and Shortest Unique Substrings....Pages 179-190 I/O-Efficient Dictionary Search with One Edit Error....Pages 191-202 Online Pattern Matching for String Edit Distance with Moves....Pages 203-214 K 2 -Treaps: Range Top- k Queries in Compact Space....Pages 215-226 Performance Improvements for Search Systems Using an Integrated Cache of Lists+Intersections....Pages 227-235 Information-Theoretic Term Selection for New Item Recommendation....Pages 236-243 On the String Consensus Problem and the Manhattan Sequence Consensus Problem....Pages 244-255 Context-Aware Deal Size Prediction....Pages 256-267 Simple and Efficient String Algorithms for Query Suggestion Metrics Computation....Pages 268-278 Back Matter....Pages -