# Invited Speakers

Alistair Moffat
Alistair Moffat has been involved in research in text compression and information retrieval for more than three decades, and has published numerous papers in the areas of index compression, text compression, and dynamic pruning mechanisms, all of which help support efficient ranked querying. Alistair is a co-author of the 1994 (revised 1999) book Managing Gigabytes, and also co-author of the 2002 book Compression and Coding Algorithms. Much of Alistair’s recent work has examined the issue of IR system evaluation, and, with other co-authors in Australia, he has focused on the relationship between models of user interactions with search results pages, and the effectiveness metrics that those interactions correspond to. Alistair was co-Chair for SIGIR 1998 in Melbourne, and for CIKM 2015, also held in Melbourne; and co-Program Committee Chair for SIGIR 2005 (Salvador, Brazil) and SIGIR 2015 (Santiago, Chile). WSDM, held in Melbourne in February 2019, was Alistair’s most recent conference project.
Alistair has been a teaching/research faculty member at the University of Melbourne since 1986, and was Department Chair from 2007-2011. During his career at Melbourne he has taught programming skills to well in excess of 15,000 undergraduate students, has authored a C programming textbook (Programming, Problem Solving, and Abstraction with C, 2002, revised 2012), and has received awards for his teaching and lecturing skills.
Alistair’s PhD was completed in 1985, at the University of Canterbury, in New Zealand, in the area of shortest path algorithms.

Gonzalo Navarro
Gonzalo Navarro completed his PhD in Computer Science in 1998 at the University of Chile, where he is currently full professor. His areas of interest include algorithms and data structures, text searching, compression, and metric space searching.
He has directed the Millennium Nucleus Center for Web Research, RIBIDI (an Ibero American project funded by CYTED), and a project funded by Yahoo! Research, apart from smaller projects. He has participated in various research projects, such as the Millennium Institute for Cell Dynamics and Biotechnology, an ECOS/CONICYT project (Chile-France cooperation), AMYRI (a CYTED project), and a Fondef project. Currently, he participates in the Millennium Nucleus Information and Coordination in Networks and in the Center for Biotechnology and Bioengineering.
He has been PC (co-)chair of several conferences: SPIRE 2001, SCCC 2004, SPIRE 2005, SIGIR 2005 Posters, IFIP TCS 2006, a track of ENC 2007, SISAP 2008, SISAP 2012, LATIN 2016, SPIRE 2018, and CPM 2018. He co-created SISAP on 2008, and was Steering Committee member of SPIRE, LATIN, and SISAP. He is a member of the Editorial Board of the journals Information Retrieval, ACM Journal of Experimental Algorithmics, and Information Systems. He has been guest editor of special issues in ACM SIGSPATIAL, Journal of Discrete Algorithmics, Information Systems, and Algorithmica. He has been PC member of more than 50 international conferences and reviewer for about 40 international journals. He has given around 50 invited talks in several universities and international conferences, including 12 plenary talks and 5 tutorials in international conferences. He created in 2005 the Workshop on Compression, Text, and Algorithms, which has become a permanent satellite of SPIRE.
He has coauthored two books published by Cambridge University Press, about 25 book chapters, 8 proceedings of international conferences (editor), more than 150 papers in international journals, and over 230 in international conferences. He is one of the most prolific and highly cited authors in Latin America.
He has advised 6 postdocs, 18 PhDs, 15 MScs, and 16 undergraduate theses.

Veli Mäkinen
Veli Mäkinen is Professor of Computer Science at the University of Helsinki. He heads the Genome-scale algorithmics research group and is the Director of the Master’s Programme in Computer Science. He has adviced 8 postdocs and supervised 4 PhD theses and 36 Master’s theses. He is currently supervising three PhD theses.
Veli Mäkinen started his career in string algorithms and compressed data structures. As of 2019, he has over 100 publications on these and related topics, with the focus being shifted towards algorithmic bioinformatics, where different high-throughput sequencing data analysis scenarios make near-linear time algorithms that work in small space an appealing target of study. Inspired by this new angle to bioinformatics algorithms, Veli Mäkinen co-authored a textbook on Genome-scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing, published by Cambridge University Press, 2015.
The new textbook works as the main material for two algorithmic bioinformatics courses taught frequently by Veli Mäkinen. He also teaches the general algorithms courses Design and Analysis of Algorithms, String Processing Algorithms, Data Compression Techniques, and projects and seminars related to these topics.
Some current research interests include studying algorithms and computational complexity when moving from sequences to variation graphs in (pan-)genomics, and studying applications of different index structures related to the variants of the Burrows-Wheeler transform.
Besides research and teaching, Veli Mäkinen has an active role in the research community. Some recent activities include co-chairing IWOCA 2016 and guest editing a special issue for Theory of Computing Systems, program committee memberships (WABI 2013-2018, MFCS 2016, RECOMB 2017-2019, SPIRE 2018, CPM 2018-2019), and a keynote talk at the ECCB 2016 workshop on Computational Pan-Genomics.

# Programme

All papers accepted in SPIRE 2019 have been allocated a time slot for oral presentation of 20min and 10min respectively for regular and short papers. (Printable Programme in PDF here)

The venue is Campus Maria Zambrano that includes the school of Informatics. All talks will be presented at room G.121 (first floor) with the exception of the opening session that will be held on the main hall («ágora») within the building.

 Sunday, October 6th 21:00 Welcome cocktail    (@ Hotel San Antonio El Real.)

 Monday, October 7th 09:00 Registration 09:30 Opening 10:00 – 11:00 S1 : Data Compression (chair: Rossano Venturini) [Regul] Approximation ratios of RePair, LongestMatch and Greedy on unary strings. Danny Hucke. [Regul] Lossless Image Compression Using List Update Algorithms. Arezoo Abdollahi, Neil Bruce, Shahin Kamali and Rezaul Karim. [Short] Rpair: Scaling up RePair with Rsync. Travis Gagie, Tomohiro I, Giovanni Manzini, Gonzalo Navarro, Hiroshi Sakamoto and Yoshimasa Takabatake. 11:00 Coffee 11:30 – 12:30 S2 : Information Retrieval (chair: Ricardo Baeza-Yates) [Regul] Position Bias Estimation for Unbiased Learning-to-Rank in eCommerce Search. Grigor Aslanyan and Utkarsh Porwal. [Short] An Optimal Algorithm to Find Champions of Tournament Graphs. Lorenzo Beretta, Franco Maria Nardini, Roberto Trani and Rossano Venturini. [Short] Network-Based Pooling for Topic Modeling on Microblog Content. Anais Ollagnier and Hywel Williams. 12:30 – 13:30 Invited Talk 1 :♦:  Alistair Moffat (AU) :♦:  C/W/L Spells «Cool»: User-Based Evaluation in Information Retrieval 13:30 – 15:30 Lunch    (@ Hotel San Antonio El Real.) 15:30 – 17:00 S3 : String Algorithms (chair: Gabriele Fici) [Regul] Bounds and Estimates on the Average Edit Distance. Michele Schimd and Gianfranco Bilardi. [Regul] Compact Data Structures for Shortest Unique Substring Queries. Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. [Regul] Fast Cartesian Tree Matching. Siwoo Song, Cheol Ryu, Simone Faro, Thierry Lecroq and Kunsoo Park. [Regul] Inducing the Lyndon Array. Felipe A. Louza, Sabrina Mantaci, Giovanni Manzini, Marinella Sciortino and Guilherme P. Telles. 17:00 – 21:00 GUIDED VISIT: Segovia and the Alcázar 21:00 Monday Dinner    (@ Restaurante Casares.)

 Tuesday, October 8th 08:50 Registration 09:00 – 11:00 S4 : String Algorithms (chair: Travis Gagie) [Regul] On Longest Common Property Preserved Substring Queries. Kazuki Kai, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda and Tomasz Kociumaka. [Regul] Online Algorithms on Antipowers and Antiperiods. Mai Alzamel, Alessio Conte, Daniele Greco, Veronica Guerrini, Costas Iliopoulos, Nadia Pisanti, Nicola Prezza, Giulia Punzi and Giovanna Rosone. [Regul] Polynomial-Delay Enumeration of Maximal Common Subsequences. Alessio Conte, Roberto Grossi, Giulia Punzi and Takeaki Uno. [Regul] Searching Runs in Streams. Oleg Merkurev and Arseny Shur. [Regul] Weighted Shortest Common Supersequence Problem Revisited. Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba. 11:00 Coffee 11:30 – 12:30 S5 : Algorithms (chair: Giovanni Manzini) [Regul] Fast Identification of Heavy Hitters by Cached and Packed Group Testing. Yusaku Kaneta, Takeaki Uno and Hiroki Arimura. [Short] Range Shortest Unique Substring Queries. Paniz Abedin, Arnab Ganguly, Solon Pissis and Sharma Thankachan. [Short] Minimal Absent Words in Rooted and Unrooted Trees. Gabriele Fici and Pawel Gawrychowski. [Short] A new Linear-time Algorithm for Centroid Decomposition. Davide Della Giustina, Nicola Prezza, and Rossano Venturini. 12:30 – 13:30 Invited Talk 2 :♦:  Veli Mäkinen (FIN) :♦:  When Stringology Meets Graphs 13:30 – 15:30 Lunch    (@ Hotel San Antonio El Real.) 15:30 – 17:00 S6 : Computational Biology (chair: Solon P. Pissis) [Regul] COBS: a Compact Bit-Sliced Signature Index. Timo Bingmann, Phelim Bradley, Florian Gauger and Zamin Iqbal. [Regul] An Index for Sequencing Reads Based on The Colored de Bruijn Graph. Diego Diaz. [Regul] Linear Time Maximum Segmentation problems in Column Stream Model. Bastien Cazaux, Dmitry Kosolobov, Veli Mäkinen, and Tuukka Norri. [Regul] Space-Efficient Merging of Succinct de Bruijn Graphs. Lavinia Egidi, Felipe A. Louza and Giovanni Manzini. 17:00 Coffee 17:30 – 18:30 Business Meeting 21:00 – 23:30 Conference banquet    (@ Restaurante – Asador El Hidalgo.)

 Wednesday, October 9th 09:20 Registration 09:30 – 11:00 S7 : Indexing and Compression (chair: Kunsoo Park) [Regul] Run-Length Encoding in a Finite Universe. N. Jesper Larsson. [Short] On the computation of longest previous non-overlapping factors. Enno Ohlebusch and Pascal Weber. [Regul] Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. [Regul] Parallel External Memory Wavelet Tree and Wavelet Matrix Construction. Jonas Ellert and Florian Kurpicz. [Short] SACABench: Benchmarking Suffix Array Construction. Johannes Bahne, Nico Bertram, Marvin Böcker, Jonas Bode, Johannes Fischer, Hermann Foot, Florian Grieskamp, Florian Kurpicz, Marvin Löbel, Oliver Magiera, Rosa Pink, David Piper and Christopher Poeplau. 11:00 Coffee 11:30 – 12:30 S8 : Compressed Data Structures (chair: José R. Paramá) [Regul] Faster Dynamic Compressed $d$-ary Relations. Diego Arroyuelo, Guillermo De Bernardo, Travis Gagie and Gonzalo Navarro. [Regul] Faster Repetition-Aware Compressed Suffix Trees based on Block Trees. Manuel Cáceres and Gonzalo Navarro. [Regul] A Practical Alphabet-Partitioning Rank/Select Data Structure. Diego Arroyuelo and Erick Sepúlveda. 12:30 – 13:30 Invited Talk 3 :♦:  Gonzalo Navarro (CHL) :♦:  Repetitiveness and Indexability 13:30 – 15:30 Lunch    (@ Hotel San Antonio El Real.) 15:30 – 17:00 S9 : Compressed Data Structures (chair: Nicola Prezza) [Regul] Adaptive Succinctness. Diego Arroyuelo and Rajeev Raman. [Regul] Fast, Small, and Simple Document Listing on Repetitive Text Collections. Dustin Cobas and Gonzalo Navarro. [Regul] Implementing the Topological Model Succinctly. Jose Fuentes, Gonzalo Navarro and Diego Seco. [Regul] Space- and Time-Efficient Storage of LiDAR Point Clouds. Susana Ladra, Miguel R. Luaces, Jose R. Parama and Fernando Silva-Coira. 17:00 Closing

# Social Programme: Welcome cocktail; Guided visit+ Monday dinner; and Conference Banquet

On Sunday 6th, we will enjoy a Welcome cocktail at 21:00h at Hotel San Antonio El Real.

On Monday 7th, there will be a Guided tour around the city that will start at «Plaza del Azoguejo» (main view of the Aqueduct) at 17.30h, and will end at «Plaza Mayor» around 20:30h. We will visit the most representative areas/monuments/places of the city including among others the Aqueduct, the Jewish quarter, a guided visit to the Alcázar de Segovia (the beautiful fortress in the North-East side of the city), the Cathedral, and Plaza Mayor.
After the tour we will enjoy a «rather informal» Monday Dinner at Restaurante Casares at 21:00h.

On Tuesday 8th, we will have the conference banquet at Restaurante – Asador El Hidalgo. at 21:00h

# Regular Papers Accepted

Arezoo Abdollahi, Neil Bruce, Shahin Kamali and Rezaul Karim.
Lossless Image Compression Using List Update Algorithms
Abstract: We consider lossless image compression using a technique similar to bZip2 for sequential data. Given an image represented with a matrix of pixel values, we consider different approaches for linearising the image into a sequence and then encoding the sequence using the Move-To-Front list update algorithm. In both linearisation and encoding stages, we exploit the locality present in the images to achieve encodings that are as compressed as possible. We consider a few approaches, and in particular Hilbert space-filling curve, for linearising the image. Using a natural model of locality for images introduced by Albers et al. [J. Comput. Syst. Sci. 2015], we establish the advantage of Hilbert-filling curve over other linearisation techniques such as row-major or column-major curves for preserving the locality during the linearisation. We also use a result by Angelopoulos and Schweitzer [J. ACM 2013] to select Move-To-Front as the best list update algorithm for encoding the linearised sequence. In summary, our theoretical results show that a combination of Hilbert space-filling curve and Move-To-Front encoding has advantage over other approaches. We verify this with experiments on a dataset consisting of different categories of images.
Billel Aklouche, Ibrahim Bounhas and Yahya Slimani.
BM25 Beyond Query-Document Similarity
Abstract: The massive growth of information produced and shared online has made retrieving relevant documents a difficult task. Query Expansion (QE) based on term co-occurrence statistics has been widely applied in an attempt to improve retrieval effectiveness. However, selecting good expansion terms using co-occurrence graphs is challenging. In this paper, we present an adapted version of the BM25 model, which allows measuring the similarity between terms. First, a context window-based approach is applied over the entire corpus in order to construct the term co-occurrence graph. Afterward, using the proposed adapted version of BM25, candidate expansion terms are selected according to their similarity with the whole query. This measure stands out by its ability to evaluate the discriminative power of terms and select semantically related terms to the query. Experiments on two ad-hoc TREC collections (the standard Robust04 collection and the new TREC Washington Post collection) show that our proposal outperforms the baselines over three state-of-the-art IR models and leads to significant improvements in retrieval effectiveness.
Mai Alzamel, Alessio Conte, Daniele Greco, Veronica Guerrini, Costas Iliopoulos, Nadia Pisanti, Nicola Prezza, Giulia Punzi and Giovanna Rosone.
Online Algorithms on Antipowers and Antiperiods
Abstract: The definition of antipower introduced by Fici et al. (ICALP 2016) captures the notion of being the opposite of a power: a sequence of k pairwise distinct blocks of the same length.
Recently, Alamro et al. (CPM 2019) defined a string to have an antiperiod if it is a prefix of an antipower, and gave complexity bounds for the offline computation of the minimum antiperiod and all the antiperiods of a word.
In this paper, we address the same problems in the online setting. Our solutions rely on new arrays that compactly and incrementally store antiperiods and antipowers as the word grows, obtaining in the process this information for all the word’s prefixes. We show how to compute those arrays online in O(n \log n) space, O(n\log n) time, and o(n^\epsilon) delay per character, for any constant \epsilon>0. Running times are worst-case and hold with high probability. We also discuss more space-efficient solutions returning the correct result with high probability, and small data structures to support random access to those arrays.
Diego Arroyuelo, Guillermo De Bernardo, Travis Gagie and Gonzalo Navarro.
Faster Dynamic Compressed $d$-ary Relations
Abstract: The $k^2$-tree is a successful compact representation of binary relations that exhibit sparseness and/or clustering properties. It can be extended to $d$ dimensions, where it is called a $k^d$-tree. The representation boils down to a long bitvector. We show that interpreting the $k^d$-tree as a dynamic trie on the Morton codes of the points, instead of as a dynamic representation of the bitvector as done in previous work, yields operation times that are below the lower bound of dynamic bitvectors and offers improved time performance in practice.
Diego Arroyuelo and Erick Sepúlveda.
A Practical Alphabet-Partitioning Rank/Select Data Structure
Abstract: This paper proposes a practical implementation of an alphabet-partitioning compressed data structure, which represents a string within compressed space and supports the fundamental operations rank and select efficiently. We show experimental results that indicate that our implementation outperforms the current realizations of the alphabet-partitioning approach (which is one of the most efficient approaches in practice). In particular, the time for operation select can be reduced by about 80%, using only 11% more space than current alphabet-partitioning schemes. We also show the impact of our data structure on several applications, like the intersection of inverted lists (where improvements of up to 60% are achieved, using only 2% of extra space), and the distributed-computation processing of rank and select operations. As far as we know, this is the first study about the support of rank/select operations on a distributed-computing environment.
Diego Arroyuelo and Rajeev Raman.