String Processing and Information Retrieval: 17th International Symposium, SPIRE 2010, Los Cabos, Mexico, October 11-13, 2010. Proceedings

✍ Scribed by Marc Najork (auth.), Edgar Chavez, Stefano Lonardi (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2010
• Tongue: English
• Leaves: 419
• Series: Lecture Notes in Computer Science 6393 : Theoretical Computer Science and General Issues
• Edition: 1
• Category: Library

✦ Synopsis

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

Front Matter....Pages -
Querying the Web Graph....Pages 1-12
Incremental Algorithms for Effective and Efficient Query Recommendation....Pages 13-24
Fingerprinting Ratings for Collaborative Filtering — Theoretical and Empirical Analysis....Pages 25-36
On Tag Spell Checking....Pages 37-42
Compressed Self-indices Supporting Conjunctive Queries on Document Collections....Pages 43-54
String Retrieval for Multi-pattern Queries....Pages 55-66
Colored Range Queries and Document Retrieval....Pages 67-81
Range Queries over Untangled Chains....Pages 82-93
Multiplication Algorithms for Monge Matrices....Pages 94-105
Why Large Closest String Instances Are Easy to Solve in Practice....Pages 106-117
A PTAS for the Square Tiling Problem....Pages 118-126
On the Hardness of Counting and Sampling Center Strings....Pages 127-134
Counting and Verifying Maximal Palindromes....Pages 135-146
Identifying SNPs without a Reference Genome by Comparing Raw Reads....Pages 147-158
Dynamic Z-Fast Tries....Pages 159-172
Improved Fast Similarity Search in Dictionaries....Pages 173-178
Training Parse Trees for Efficient VF Coding....Pages 179-184
Algorithms for Finding a Minimum Repetition Representation of a String....Pages 185-190
Faster Compressed Dictionary Matching....Pages 191-200
Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval....Pages 201-206
Standard Deviation as a Query Hardness Estimator....Pages 207-212
Using Related Queries to Improve Web Search Results Ranking....Pages 213-224
Evaluation of Query Performance Prediction Methods by Range....Pages 225-236
Mining Large Query Induced Graphs towards a Hierarchical Query Folksonomy....Pages 237-242
Finite Automata Based Algorithms for the Generalized Constrained Longest Common Subsequence Problems....Pages 243-249
Restricted LCS....Pages 250-257
Extracting Powers and Periods in a String from Its Runs Structure....Pages 258-269
On Shortest Common Superstring and Swap Permutations....Pages 270-278
A Self-Supervised Approach for Extraction of Attribute-Value Pairs from Wikipedia Articles....Pages 279-289
Temporal Analysis of Document Collections: Framework and Applications....Pages 290-296
Text Comparison Using Soft Cardinality....Pages 297-302
Hypergeometric Language Model and Zipf-Like Scoring Function for Web Document Similarity Retrieval....Pages 303-308
Dual-Sorted Inverted Lists....Pages 309-321
CST++....Pages 322-333
Succinct Representations of Dynamic Strings....Pages 334-346
Computing Matching Statistics and Maximal Exact Matches on Compressed Full-Text Indexes....Pages 347-358
The Gapped Suffix Array: A New Index Structure for Fast Approximate Matching....Pages 359-364
Parameterized Searching with Mismatches for Run-Length Encoded Strings....Pages 365-371
Fast Bit-Parallel Matching for Network and Regular Expressions....Pages 372-384
String Matching with Variable Length Gaps....Pages 385-394
Approximate String Matching with Stuck Address Bits....Pages 395-405
Erratum to: Range Queries over Untangled Chains....Pages E1-E1
Back Matter....Pages -

✦ Subjects

Information Storage and Retrieval; Computational Biology/Bioinformatics; Data Mining and Knowledge Discovery; Database Management; Pattern Recognition; Multimedia Information Systems