String Processing and Information Retrieval

1. Front Matter

   PDF

2. “Search Is a Solved Problem” and Other Annoying Fallacies

   • David Hawking

   Pages 1-1

3. Approximate Runs - Revisited

   • Gad M. Landau

   Pages 2-2

4. Engineering Radix Sort for Strings

   • Juha Kärkkäinen, Tommi Rantala

   Pages 3-14

5. Faster Text Fingerprinting

   • Roman Kolpakov, Mathieu Raffinot

   Pages 15-26

6. Context-Sensitive Grammar Transform: Compression and Pattern Matching

   • Shirou Maruyama, Yohei Tanaka, Hiroshi Sakamoto, Masayuki Takeda

   Pages 27-38

7. Improved Variable-to-Fixed Length Codes

   • Shmuel T. Klein, Dana Shapira

   Pages 39-50

8. Term Impacts as Normalized Term Frequencies for BM25 Similarity Scoring

   • Vo Ngoc Anh, Raymond Wan, Alistair Moffat

   Pages 51-62

9. The Effect of Weighted Term Frequencies on Probabilistic Latent Semantic Term Relationships

   • Laurence A. F. Park, Kotagiri Ramamohanarao

   Pages 63-74

10. Comparison of s-gram Proximity Measures in Out-of-Vocabulary Word Translation

    • Anni Järvelin, Antti Järvelin

    Pages 75-86

11. Speeding Up Pattern Matching by Text Sampling

    • Francisco Claude, Gonzalo Navarro, Hannu Peltola, Leena Salmela, Jorma Tarhio

    Pages 87-98

12. Mismatch Sampling

    • Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat, Amir Rothschild

    Pages 99-108

13. Sliding CDAWG Perfection

    • Martin Senft, Tomáš Dvořák

    Pages 109-120

14. Self-indexing Natural Language

    • Nieves R. Brisaboa, Antonio Fariña, Gonzalo Navarro, Angeles S. Places, Eduardo Rodríguez

    Pages 121-132

15. New Perspectives on the Prefix Array

    • W. F. Smyth, Shu Wang

    Pages 133-143

16. Indexed Hierarchical Approximate String Matching

    • Luís M. S. Russo, Gonzalo Navarro, Arlindo L. Oliveira

    Pages 144-154

17. An Efficient Linear Space Algorithm for Consecutive Suffix Alignment under Edit Distance (Short Preliminary Paper)

    • Heikki Hyyrö

    Pages 155-163

18. Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections

    • Jouni Sirén, Niko Välimäki, Veli Mäkinen, Gonzalo Navarro

    Pages 164-175

19. Practical Rank/Select Queries over Arbitrary Sequences

    • Francisco Claude, Gonzalo Navarro

    Pages 176-187

20. Clique Analysis of Query Log Graphs

    • Alexandre P. Francisco, Ricardo Baeza-Yates, Arlindo L. Oliveira

    Pages 188-199

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.

• DNA analysis
• Pattern Matching
• algorithms
• bioinformatics
• bipartite matching
• cognition
• combinatorial algorithms
• computational biology
• data analysis
• digital libraries
• grammar
• huffman codes
• information retrieval
• interchange rearrangement
• natural language
• data structures

• Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel

  Amihood Amir

• School of Computer Science and Information Technology, RMIT University, Melbourne, Australia

  Andrew Turpin

• NICTA Victoria Laboratory, Department of Computer Science and Software Engineering, The University of Melbourne, Victoria, Australia

  Alistair Moffat

Policies and ethics