String Processing and Information Retrieval

1. Front Matter

   PDF

2. Compression

   1. Strategic Pattern Search in Factor-Compressed Text

      • Simon Gog, Alistair Moffat, Matthias Petri

      Pages 1-12

   2. Relative Lempel-Ziv with Constant-Time Random Access

      • Héctor Ferrada, Travis Gagie, Simon Gog, Simon J. Puglisi

      Pages 13-17

   3. Efficient Compressed Indexing for Approximate Top-k String Retrieval

      • Héctor Ferrada, Gonzalo Navarro

      Pages 18-30

   4. Grammar Compressed Sequences with Rank/Select Support

      • Gonzalo Navarro, Alberto Ordóñez

      Pages 31-44

3. Indexing

   1. Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on Run-Length Encoded Strings

      • Amihood Amir, Alberto Apostolico, Tirza Hirst, Gad M. Landau, Noa Lewenstein, Liat Rozenberg

      Pages 45-51

   2. Relative FM-Indexes

      • Djamal Belazzougui, Travis Gagie, Simon Gog, Giovanni Manzini, Jouni Sirén

      Pages 52-64

   3. Efficient Indexing and Representation of Web Access Logs

      • Francisco Claude, Roberto Konow, Gonzalo Navarro

      Pages 65-76

   4. A Compressed Suffix-Array Strategy for Temporal-Graph Indexing

      • Nieves R. Brisaboa, Diego Caro, Antonio Fariña, M. Andrea Rodríguez

      Pages 77-88

   5. Succinct Indexes for Reporting Discriminating and Generic Words

      • Sudip Biswas, Manish Patil, Rahul Shah, Sharma V. Thankachan

      Pages 89-100

   6. Fast Construction of Wavelet Trees

      • J. Ian Munro, Yakov Nekrich, Jeffrey S. Vitter

      Pages 101-110

   7. Order Preserving Prefix Tables

      • Md. Mahbubul Hasan, A. S. M. Sohidull Islam, Mohammad Saifur Rahman, M. Sohel Rahman

      Pages 111-116

4. Genome and Related Topics

   1. Alphabet-Independent Algorithms for Finding Context-Sensitive Repeats in Linear Time

      • Enno Ohlebusch, Timo Beller

      Pages 117-128

   2. A 3-Approximation Algorithm for the Multiple Spliced Alignment Problem and Its Application to the Gene Prediction Task

      • Regina Beretta Mazaro, Leandro Ishi Soares de Lima, Said Sadique Adi

      Pages 129-138

   3. Improved Filters for the Approximate Suffix-Prefix Overlap Problem

      • Gregory Kucherov, Dekel Tsur

      Pages 139-148

5. Sequences and Strings

   1. Sequence Decision Diagrams

      • Hind Alhakami, Gianfranco Ciardo, Marek Chrobak

      Pages 149-160

   2. Shortest Unique Queries on Strings

      • Xiaocheng Hu, Jian Pei, Yufei Tao

      Pages 161-172

   3. Online Multiple Palindrome Pattern Matching

      • Hwee Kim, Yo-Sub Han

      Pages 173-178

   4. Indexed Matching Statistics and Shortest Unique Substrings

      • Djamal Belazzougui, Fabio Cunial

      Pages 179-190

6. Search

   1. I/O-Efficient Dictionary Search with One Edit Error

      • Chin-Wan Chung, Yufei Tao, Wei Wang

      Pages 191-202

This book constitutes the proceedings of the 21st International Symposium on String Processing and Information Retrieval, SPIRE 2014, held in Ouro Preto, Brazil, in October 2014. The 20 full and 6 short papers included in this volume were carefully reviewed and selected from 45 submissions. The papers focus not only on fundamental algorithms in string processing and information retrieval, but address also application areas such as computational biology, Web mining and recommender systems. They are organized in topical sections on compression, indexing, genome and related topics, sequences and strings, search, as well as on mining and recommending.

• algorithm
• approximation algorithm
• bioinformatics
• compression
• experimental evaluation
• gene prediction
• graphs
• index
• information retrieval
• pattern matching
• query processing
• recommender systems
• search
• search engines
• sequence processing
• string processing
• string search
• algorithm analysis and problem complexity

• Instituto de Computação, Universidade Federal do Amazonas, Manaus, Brazil

  Edleno Moura

• King’s College London, UK

  Maxime Crochemore

Policies and ethics