String Processing and Information Retrieval

1. Front Matter

   PDF

2. Algorithms on Trees

   1. Range Quantile Queries: Another Virtue of Wavelet Trees

      • Travis Gagie, Simon J. Puglisi, Andrew Turpin

      Pages 1-6

   2. Constant Factor Approximation of Edit Distance of Bounded Height Unordered Trees

      • Daiji Fukagawa, Tatsuya Akutsu, Atsuhiro Takasu

      Pages 7-17

   3. k2-Trees for Compact Web Graph Representation

      • Nieves R. Brisaboa, Susana Ladra, Gonzalo Navarro

      Pages 18-30

   4. On-Line Construction of Parameterized Suffix Trees

      • Taehyung Lee, Joong Chae Na, Kunsoo Park

      Pages 31-38

3. Compressed Indexes

   1. Succinct Text Indexing with Wildcards

      • Alan Tam, Edward Wu, Tak-Wah Lam, Siu-Ming Yiu

      Pages 39-50

   2. A Compressed Enhanced Suffix Array Supporting Fast String Matching

      • Enno Ohlebusch, Simon Gog

      Pages 51-62

   3. Compressed Suffix Arrays for Massive Data

      • Jouni Sirén

      Pages 63-74

   4. On Entropy-Compressed Text Indexing in External Memory

      • Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan, Jeffrey Scott Vitter

      Pages 75-89

4. Compression

   1. A Linear-Time Burrows-Wheeler Transform Using Induced Sorting

      • Daisuke Okanohara, Kunihiko Sadakane

      Pages 90-101

   2. Novel and Generalized Sort-Based Transform for Lossless Data Compression

      • Kazumasa Inagaki, Yoshihiro Tomizawa, Hidetoshi Yokoo

      Pages 102-113

   3. A Two-Level Structure for Compressing Aligned Bitexts

      • Joaquín Adiego, Nieves R. Brisaboa, Miguel A. Martínez-Prieto, Felipe Sánchez-Martínez

      Pages 114-121

   4. Directly Addressable Variable-Length Codes

      • Nieves R. Brisaboa, Susana Ladra, Gonzalo Navarro

      Pages 122-130

5. Content Analysis

   1. Identifying the Intent of a User Query Using Support Vector Machines

      • Marcelo Mendoza, Juan Zamora

      Pages 131-142

   2. Syntactic Query Models for Restatement Retrieval

      • Niranjan Balasubramanian, James Allan

      Pages 143-155

   3. Use of Co-occurrences for Temporal Expressions Annotation

      • Olga Craveiro, Joaquim Macedo, Henrique Madeira

      Pages 156-164

   4. On-Demand Associative Cross-Language Information Retrieval

      • André Pinto Geraldo, Viviane P. Moreira, Marcos A. Gonçalves

      Pages 165-173

   5. A Comparison of Data-Driven Automatic Syllabification Methods

      • Connie R. Adsett, Yannick Marchand

      Pages 174-181

6. Indexing

   1. Efficient Index for Retrieving Top-k Most Frequent Documents

      • Wing-Kai Hon, Rahul Shah, Shih-Bin Wu

      Pages 182-193

   2. Fast Single-Pass Construction of a Half-Inverted Index

      • Marjan Celikik, Hannah Bast

      Pages 194-205

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.

• algorithms
• data analysis
• data compression
• data mining
• graph theory
• hashing
• information retrieval
• knowledge discovery
• sorting
• string matching
• text mining
• data structures

• Swedish Institute of Computer Science, Kista, Sweden

  Jussi Karlgren

• Department of Computer Science and Engineering, Helsinki University of Technology, Espoo, Finland

  Jorma Tarhio

• Department of Computer Sciences, University of Tampere, Tampere, Finland

  Heikki Hyyrö

Policies and ethics