String Processing and Information Retrieval: 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7–9, 2019, Proceedings

Description

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. Front Matter ....Pages i-xviii Front Matter ....Pages 1-1 Approximation Ratios of \(\mathsf {RePair}\), \(\mathsf {LongestMatch}\) and \(\mathsf {Greedy}\) on Unary Strings (Danny Hucke)....Pages 3-15 Lossless Image Compression Using List Update Algorithms (Arezoo Abdollahi, Neil Bruce, Shahin Kamali, Rezaul Karim)....Pages 16-34 Rpair: Rescaling RePair with Rsync (Travis Gagie, Tomohiro I, Giovanni Manzini, Gonzalo Navarro, Hiroshi Sakamoto, Yoshimasa Takabatake)....Pages 35-44 Front Matter ....Pages 45-45 Position Bias Estimation for Unbiased Learning-to-Rank in eCommerce Search (Grigor Aslanyan, Utkarsh Porwal)....Pages 47-64 BM25 Beyond Query-Document Similarity (Billel Aklouche, Ibrahim Bounhas, Yahya Slimani)....Pages 65-79 Network-Based Pooling for Topic Modeling on Microblog Content (Anaïs Ollagnier, Hywel Williams)....Pages 80-87 Front Matter ....Pages 89-89 Bounds and Estimates on the Average Edit Distance (Michele Schimd, Gianfranco Bilardi)....Pages 91-106 Compact Data Structures for Shortest Unique Substring Queries (Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda)....Pages 107-123 Fast Cartesian Tree Matching (Siwoo Song, Cheol Ryu, Simone Faro, Thierry Lecroq, Kunsoo Park)....Pages 124-137 Inducing the Lyndon Array (Felipe A. Louza, Sabrina Mantaci, Giovanni Manzini, Marinella Sciortino, Guilherme P. Telles)....Pages 138-151 Minimal Absent Words in Rooted and Unrooted Trees (Gabriele Fici, Paweł Gawrychowski)....Pages 152-161 On Longest Common Property Preserved Substring Queries (Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Tomasz Kociumaka)....Pages 162-174 Online Algorithms on Antipowers and Antiperiods (Mai Alzamel, Alessio Conte, Daniele Greco, Veronica Guerrini, Costas Iliopoulos, Nadia Pisanti et al.)....Pages 175-188 Polynomial-Delay Enumeration of Maximal Common Subsequences (Alessio Conte, Roberto Grossi, Giulia Punzi, Takeaki Uno)....Pages 189-202 Searching Runs in Streams (Oleg Merkurev, Arseny M. Shur)....Pages 203-220 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 Front Matter ....Pages 239-239 Fast Identification of Heavy Hitters by Cached and Packed Group Testing (Yusaku Kaneta, Takeaki Uno, Hiroki Arimura)....Pages 241-257 Range Shortest Unique Substring Queries (Paniz Abedin, Arnab Ganguly, Solon P. Pissis, Sharma V. Thankachan)....Pages 258-266 An Optimal Algorithm to Find Champions of Tournament Graphs (Lorenzo Beretta, Franco Maria Nardini, Roberto Trani, Rossano Venturini)....Pages 267-273 A New Linear-Time Algorithm for Centroid Decomposition (Davide Della Giustina, Nicola Prezza, Rossano Venturini)....Pages 274-282 Front Matter ....Pages 283-283 COBS: A Compact Bit-Sliced Signature Index (Timo Bingmann, Phelim Bradley, Florian Gauger, Zamin Iqbal)....Pages 285-303 An Index for Sequencing Reads Based on the Colored de Bruijn Graph (Diego Díaz-Domínguez)....Pages 304-321 Linear Time Maximum Segmentation Problems in Column Stream Model (Bastien Cazaux, Dmitry Kosolobov, Veli Mäkinen, Tuukka Norri)....Pages 322-336 Space-Efficient Merging of Succinct de Bruijn Graphs (Lavinia Egidi, Felipe A. Louza, Giovanni Manzini)....Pages 337-351 Front Matter ....Pages 353-353 Run-Length Encoding in a Finite Universe (N. Jesper Larsson)....Pages 355-371 On the Computation of Longest Previous Non-overlapping Factors (Enno Ohlebusch, Pascal Weber)....Pages 372-381 Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets (Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda)....Pages 382-391 Parallel External Memory Wavelet Tree and Wavelet Matrix Construction (Jonas Ellert, Florian Kurpicz)....Pages 392-406 SACABench: Benchmarking Suffix Array Construction (Johannes Bahne, Nico Bertram, Marvin Böcker, Jonas Bode, Johannes Fischer, Hermann Foot et al.)....Pages 407-416 Front Matter ....Pages 417-417 Faster Dynamic Compressed d-ary Relations (Diego Arroyuelo, Guillermo de Bernardo, Travis Gagie, Gonzalo Navarro)....Pages 419-433 Faster Repetition-Aware Compressed Suffix Trees Based on Block Trees (Manuel Cáceres, Gonzalo Navarro)....Pages 434-451 A Practical Alphabet-Partitioning Rank/Select Data Structure (Diego Arroyuelo, Erick Sepúlveda)....Pages 452-466 Adaptive Succinctness (Diego Arroyuelo, Rajeev Raman)....Pages 467-481 Fast, Small, and Simple Document Listing on Repetitive Text Collections (Dustin Cobas, Gonzalo Navarro)....Pages 482-498 Implementing the Topological Model Succinctly (José Fuentes-Sepúlveda, Gonzalo Navarro, Diego Seco)....Pages 499-512 Space- and Time-Efficient Storage of LiDAR Point Clouds (Susana Ladra, Miguel R. Luaces, José R. Paramá, Fernando Silva-Coira)....Pages 513-527 Back Matter ....Pages 529-530