This book constitutes the refereed proceedings of the 16th String Processing and Information Retrieval Symposium, SPIRE 2009 held in Saariselkä, Finland in August 2009.
The 34 revised full papers were carefully reviewed and selected from 84 submissions. The papers are organized in topical sections on algorithms on trees, compressed indexes, compression, indexing, content analysis, string algorithms and bioinformatics, string algorithms and theory, and using and understanding usage.
Author(s): Travis Gagie, Simon J. Puglisi, Andrew Turpin (auth.), Jussi Karlgren, Jorma Tarhio, Heikki Hyyrö (eds.)
Series: Lecture Notes in Computer Science 5721 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 354
Tags: Data Mining and Knowledge Discovery; Data Structures; Data Structures, Cryptology and Information Theory; Symbolic and Algebraic Manipulation; Algorithm Analysis and Problem Complexity; Pattern Recognition
Front Matter....Pages -
Range Quantile Queries: Another Virtue of Wavelet Trees....Pages 1-6
Constant Factor Approximation of Edit Distance of Bounded Height Unordered Trees....Pages 7-17
k 2 -Trees for Compact Web Graph Representation....Pages 18-30
On-Line Construction of Parameterized Suffix Trees....Pages 31-38
Succinct Text Indexing with Wildcards....Pages 39-50
A Compressed Enhanced Suffix Array Supporting Fast String Matching....Pages 51-62
Compressed Suffix Arrays for Massive Data....Pages 63-74
On Entropy-Compressed Text Indexing in External Memory....Pages 75-89
A Linear-Time Burrows-Wheeler Transform Using Induced Sorting....Pages 90-101
Novel and Generalized Sort-Based Transform for Lossless Data Compression....Pages 102-113
A Two-Level Structure for Compressing Aligned Bitexts....Pages 114-121
Directly Addressable Variable-Length Codes....Pages 122-130
Identifying the Intent of a User Query Using Support Vector Machines....Pages 131-142
Syntactic Query Models for Restatement Retrieval....Pages 143-155
Use of Co-occurrences for Temporal Expressions Annotation....Pages 156-164
On-Demand Associative Cross-Language Information Retrieval....Pages 165-173
A Comparison of Data-Driven Automatic Syllabification Methods....Pages 174-181
Efficient Index for Retrieving Top- k Most Frequent Documents....Pages 182-193
Fast Single-Pass Construction of a Half-Inverted Index....Pages 194-205
Two-Dimensional Distributed Inverted Files....Pages 206-213
Indexing Variable Length Substrings for Exact and Approximate Matching....Pages 214-221
Expectation of Strings with Mismatches under Markov Chain Distribution....Pages 222-233
Consensus Optimizing Both Distance Sum and Radius....Pages 234-242
Faster Algorithms for Sampling and Counting Biological Sequences....Pages 243-253
Towards a Theory of Patches....Pages 254-265
The Frequent Items Problem, under Polynomial Decay, in the Streaming Model....Pages 266-276
Improved Approximation Results on the Shortest Common Supersequence Problem....Pages 277-284
Set Intersection and Sequence Matching....Pages 285-294
Generalised Matching....Pages 295-301
Practical Algorithms for the Longest Common Extension Problem....Pages 302-309
A Last-Resort Semantic Cache for Web Queries....Pages 310-321
A Task-Based Evaluation of an Aggregated Search Interface....Pages 322-333
Efficient Language-Independent Retrieval of Printed Documents without OCR....Pages 334-343
Sketching Algorithms for Approximating Rank Correlations in Collaborative Filtering Systems....Pages 344-352
Back Matter....Pages -
