String Processing and Information Retrieval

1. Front Matter

   Pages i-xviii

   PDF

2. Data Compression

   1. Front Matter

      Pages 1-1

      PDF

   2. Approximation Ratios of \(\mathsf {RePair}\), \(\mathsf {LongestMatch}\) and \(\mathsf {Greedy}\) on Unary Strings

      • Danny Hucke

      Pages 3-15

   3. Lossless Image Compression Using List Update Algorithms

      • Arezoo Abdollahi, Neil Bruce, Shahin Kamali, Rezaul Karim

      Pages 16-34

   4. Rpair: Rescaling RePair with Rsync

      • Travis Gagie, Tomohiro I, Giovanni Manzini, Gonzalo Navarro, Hiroshi Sakamoto, Yoshimasa Takabatake

      Pages 35-44

3. Information Retrieval

   1. Front Matter

      Pages 45-45

      PDF

   2. Position Bias Estimation for Unbiased Learning-to-Rank in eCommerce Search

      • Grigor Aslanyan, Utkarsh Porwal

      Pages 47-64

   3. BM25 Beyond Query-Document Similarity

      • Billel Aklouche, Ibrahim Bounhas, Yahya Slimani

      Pages 65-79

   4. Network-Based Pooling for Topic Modeling on Microblog Content

      • Anaïs Ollagnier, Hywel Williams

      Pages 80-87

4. String Algorithms

   1. Front Matter

      Pages 89-89

      PDF

   2. Bounds and Estimates on the Average Edit Distance

      • Michele Schimd, Gianfranco Bilardi

      Pages 91-106

   3. Compact Data Structures for Shortest Unique Substring Queries

      • Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

      Pages 107-123

   4. Fast Cartesian Tree Matching

      • Siwoo Song, Cheol Ryu, Simone Faro, Thierry Lecroq, Kunsoo Park

      Pages 124-137

   5. Inducing the Lyndon Array

      • Felipe A. Louza, Sabrina Mantaci, Giovanni Manzini, Marinella Sciortino, Guilherme P. Telles

      Pages 138-151

   6. Minimal Absent Words in Rooted and Unrooted Trees

      • Gabriele Fici, Paweł Gawrychowski

      Pages 152-161

   7. On Longest Common Property Preserved Substring Queries

      • Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomasz Kociumaka

      Pages 162-174

   8. Online Algorithms on Antipowers and Antiperiods

      • Mai Alzamel, Alessio Conte, Daniele Greco, Veronica Guerrini, Costas Iliopoulos, Nadia Pisanti et al.

      Pages 175-188

   9. Polynomial-Delay Enumeration of Maximal Common Subsequences

      • Alessio Conte, Roberto Grossi, Giulia Punzi, Takeaki Uno

      Pages 189-202

   10. Searching Runs in Streams

       • Oleg Merkurev, Arseny M. Shur

       Pages 203-220

   11. Weighted Shortest Common Supersequence Problem Revisited

       • Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński et al.

       Pages 221-238

This volume constitutes the refereed proceedings of the 26th International Symposium on String Processing and Information Retrieval, SPIRE 2019, held in Segovia, Spain, in October 2019.
The 28 full papers and 8 short papers presented in this volume were carefully reviewed and selected from 59 submissions. They cover topics such as: data compression; information retrieval; string algorithms; algorithms; computational biology; indexing and compression; and compressed data structures.

• algorithms
• bioinformatics
• data compression
• databases
• experimental evaluation
• graphs
• information retrieval
• natural language processing
• pattern matching
• search engines
• sequences and graphs
• string processing
• data mining
• data structures
• dynamic programming
• query processing
• string search
• software engineering
• query languages
• image processing

• University of A Coruña, A Coruña, Spain

  Nieves R. Brisaboa

• University of Helsinki, Helsinki, Finland

  Simon J. Puglisi

Policies and ethics