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

ISBN-13: 9783642037832 / Angielski / MiÄ™kka / 2009 / 372 str.

Jussi Karlgren

Opis

This volume contains the papers presented at the 16th International Sym- sium on String Processing and Information Retrieval (SPIRE 2009), held during August 25-27, 2009 in Saariselk] a, Finland. The annual SPIRE conference provides researchers within ?elds related to string processing and/or information retrieval a possibility to present their or- inal contributions and to meet and discuss with other researchers with similar interests. The Call for Papers invited submissions related to string processing (dictionary algorithms; text searching; pattern matching; text and sequence c- pression; automata-based string processing), information retrieval (information retrieval models; indexing; ranking and ?ltering; interface design; visualization; benchmarking), natural language processing (text analysis; text mining; - chine learning; information extraction; language models; knowledge represen- tion), search applications and usage (cross-lingual information access systems; multimedia information access; digital libraries; collaborative retrieval and W- related applications; semi-structured data retrieval; evaluation), and interaction of biology and computation (DNA sequencing and applications in molecular - ology; evolution and phylogenetics; recognition of genes and regulatory elements; sequence driven protein structure prediction). The papers presented at the symposium were selected from 84 submissions written by authors from 28 di?erent countries. Each submission was reviewed by at least two and on average 2. 9 reviewers. The Committee accepted 34 papers (? 40%): 22 papers for 25-minute and 12 papers for 15-minute presentations. In addition to these, SPIRE 2009 also featured invited talks by Mehryar Mohri (New York University, USA) and Kalervo Ja ]rvelin (University of Tampere, Finland).

Spis treści

Algorithms on Trees.- Range Quantile Queries: Another Virtue of Wavelet Trees.- Constant Factor Approximation of Edit Distance of Bounded Height Unordered Trees.- k2-Trees for Compact Web Graph Representation.- On-Line Construction of Parameterized Suffix Trees.- Compressed Indexes.- Succinct Text Indexing with Wildcards.- A Compressed Enhanced Suffix Array Supporting Fast String Matching.- Compressed Suffix Arrays for Massive Data.- On Entropy-Compressed Text Indexing in External Memory.- Compression.- A Linear-Time Burrows-Wheeler Transform Using Induced Sorting.- Novel and Generalized Sort-Based Transform for Lossless Data Compression.- A Two-Level Structure for Compressing Aligned Bitexts.- Directly Addressable Variable-Length Codes.- Content Analysis.- Identifying the Intent of a User Query Using Support Vector Machines.- Syntactic Query Models for Restatement Retrieval.- Use of Co-occurrences for Temporal Expressions Annotation.- On-Demand Associative Cross-Language Information Retrieval.- A Comparison of Data-Driven Automatic Syllabification Methods.- Indexing.- Efficient Index for Retrieving Top-k Most Frequent Documents.- Fast Single-Pass Construction of a Half-Inverted Index.- Two-Dimensional Distributed Inverted Files.- Indexing Variable Length Substrings for Exact and Approximate Matching.- String Algorithms and Bioinformatics.- Expectation of Strings with Mismatches under Markov Chain Distribution.- Consensus Optimizing Both Distance Sum and Radius.- Faster Algorithms for Sampling and Counting Biological Sequences.- String Algorithms and Theory I.- Towards a Theory of Patches.- The Frequent Items Problem, under Polynomial Decay, in the Streaming Model.- Improved Approximation Results on the Shortest Common Supersequence Problem.- String Algorithms and Theory II.- Set Intersection and Sequence Matching.- Generalised Matching.- Practical Algorithms for the Longest Common Extension Problem.- Using and Understanding Usage.- A Last-Resort Semantic Cache for Web Queries.- A Task-Based Evaluation of an Aggregated Search Interface.- Efficient Language-Independent Retrieval of Printed Documents without OCR.- Sketching Algorithms for Approximating Rank Correlations in Collaborative Filtering Systems.

Blurb

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.