String Processing and Information Retrieval

by Chavez, Edgar; Lonardi, Stefano

• ISBN13: 9783642163203
• ISBN10: 3642163203
• Format: Paperback
• Copyright: 2010-10-18
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the proceedings of the 17th International Symposium on String Processing and Information Retrieval, SPIRE 2010, held in Los Cabos, Mexico, in October 2010. The 26 long and 13 short papers presented were carefully reviewed and selected from 109 submissions. The volume also contains 2 invited talks. The papers are structured in topical sections on crowdsourcing and recommendation; indexes and compressed indexes; theory; string algorithms; compressions; querying and search user experience; document analysis and comparison; compressed indexes; and string matching.

Table of Contents

Crowdsourcing and Recommendation
Querying the Web Graph (Invited Talk)	p. 1
Incremental Algorithms for Effective and Efficient Query Recommendation	p. 13
Fingerprinting Ratings for Collaborative Filtering - Theoretical and Empirical Analysis	p. 25
On Tag Spell Checking	p. 37
Indexes and Compressed Indexes
Compressed Self-Indices Supporting Conjunctive Queries on Document Collections	p. 43
String Retrieval for Multi-pattern Queries	p. 55
Colored Range Queries and Document Retrieval	p. 67
Range Queries over Untangled Chains	p. 82
Theory
Multiplication Algorithms for Monge Matrices	p. 94
Why Large Closest String Instances Are Easy to Solve in Practice	p. 106
A PTAS for the Square Tiling Problem	p. 118
On the Hardness of Counting and Sampling Center Strings	p. 127
String Algorithms I
Counting and Verifying Maximal Palindromes	p. 135
Identifying SNPs without a Reference Genome by Comparing Raw Reads	p. 147
Dynamic Z-Fast Tries	p. 159
Improved Fast Similarity Search in Dictionaries	p. 173
Compression
Training Parse Trees for Efficient VF Coding	p. 179
Algorithms for Finding a Minimum Repetition Representation of a String	p. 185
Faster Compressed Dictionary Matching	p. 191
Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval	p. 201
Querying and Search User Experience
Standard Deviation as a Query Hardness Estimator	p. 207
Using Related Queries to Improve Web Search Results Ranking	p. 213
Evaluation of Query Performance Prediction Methods by Range	p. 225
Mining Large Query Induced Graphs towards a Hierarchical Query Folksonomy	p. 237
String Algorithms II
Finite Automata Based Algorithms for the Generalized Constrained Longest Common Subsequence Problems	p. 243
Restricted LCS	p. 250
Extracting Powers and Periods in a String from Its Runs Structure	p. 258
On Shortest Common Superstring and Swap Permutations	p. 270
Document Analysis and Comparison
A Self-Supervised Approach for Extraction of Attribute-Value Pairs from Wikipedia Articles	p. 279
Temporal Analysis of Document Collections: Framework and Applications	p. 290
Text Comparison Using Soft Cardinality	p. 297
Hypergeometric Language Model and Zipf-Like Scoring Function for Web Document Similarity Retrieval	p. 303
Compressed Indexes
Dual-Sorted Inverted Lists (Invited Talk)	p. 309
CST++	p. 322
Succinct Representations of Dynamic Strings	p. 334
Computing Matching Statistics and Maximal Exact Matches on Compressed Full-Text Indexes	p. 347
The Gapped Suffix Array: A New Index Structure for Fast Approximate Matching	p. 359
String Matching
Parameterized Searching with Mismatches for Run-Length Encoded Strings (Extended Abstract)	p. 365
Fast Bit-Parallel Matching for Network and Regular Expressions	p. 372
String Matching with Variable Length Gaps	p. 385
Approximate String Matching with Stuck Address Bits	p. 395
Author Index	p. 407
Table of Contents provided by Ingram. All Rights Reserved.