String Processing and Information Retrieval: 15th International Symposium, SPIRE 2008, Melbourne, Australia, November 10-12, 2008. Proceedings

✍ Scribed by David Hawking (auth.), Amihood Amir, Andrew Turpin, Alistair Moffat (eds.)

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

✦ Synopsis

This book constitutes the refereed proceedings of the 15th International Symposium on String Processing and Information Retrieval, SPIRE 2008, held in Melbourne, Australia, in November 2008.

The 25 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 54 submissions. The papers are organized in topical sections on compression and performance, information retrieval scoring and ranking, string matching techniques, self-indexing, string matching: space and practicality, information retrieval, non-standard matching, and bioinformatics.

✦ Table of Contents

Front Matter....Pages -
“Search Is a Solved Problem” and Other Annoying Fallacies....Pages 1-1
Approximate Runs - Revisited....Pages 2-2
Engineering Radix Sort for Strings....Pages 3-14
Faster Text Fingerprinting....Pages 15-26
Context-Sensitive Grammar Transform: Compression and Pattern Matching....Pages 27-38
Improved Variable-to-Fixed Length Codes....Pages 39-50
Term Impacts as Normalized Term Frequencies for BM25 Similarity Scoring....Pages 51-62
The Effect of Weighted Term Frequencies on Probabilistic Latent Semantic Term Relationships....Pages 63-74
Comparison of s -gram Proximity Measures in Out-of-Vocabulary Word Translation....Pages 75-86
Speeding Up Pattern Matching by Text Sampling....Pages 87-98
Mismatch Sampling....Pages 99-108
Sliding CDAWG Perfection....Pages 109-120
Self-indexing Natural Language....Pages 121-132
New Perspectives on the Prefix Array....Pages 133-143
Indexed Hierarchical Approximate String Matching....Pages 144-154
An Efficient Linear Space Algorithm for Consecutive Suffix Alignment under Edit Distance ( Short Preliminary Paper )....Pages 155-163
Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections....Pages 164-175
Practical Rank/Select Queries over Arbitrary Sequences....Pages 176-187
Clique Analysis of Query Log Graphs....Pages 188-199
Out of the Box Phrase Indexing....Pages 200-211
Approximated Pattern Matching with the L 1 , L 2 and L  ∞  Metrics....Pages 212-223
Interchange Rearrangement: The Element-Cost Model....Pages 224-235
δγ – Parameterized Matching....Pages 236-248
Pattern Matching with Pair Correlation Distance....Pages 249-256
Some Approximations for Shortest Common Nonsubsequences and Supersequences....Pages 257-268
On the Structure of Small Motif Recognition Instances....Pages 269-281
Exact Distribution of a Spaced Seed Statistic for DNA Homology Detection....Pages 282-293
Back Matter....Pages -

✦ Subjects

Data Mining and Knowledge Discovery; Artificial Intelligence (incl. Robotics); Database Management; Data Structures; Coding and Information Theory; Algorithm Analysis and Problem Complexity