String Processing and Information Retrieval: 16th International Symposium, SPIRE 2009 Saariselkä, Finland, August 25-27, 2009 Proceedings

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 -