Welcome to SPIRE 2017

SPIRE 2017 is the 24th edition of the annual Symposium on String Processing and Information Retrieval. SPIRE has its origins in the South American Workshop on String Processing, which was first held in Belo Horizonte, Brazil, in 1993. Since 1998 the focus of the workshop has also included information retrieval, due to its increasing relevance to and inter-relationship with string processing.
SPIRE 2017 will be held in Palermo, Italy.

The poster of SPIRE 2017 is available here.
Springer

As in past editions, the proceedings of SPIRE 2017 will be published by Springer in the Lecture Notes in Computer Science (LNCS) series.

Free access to the conference proceedings from here.

A Best Paper Award, sponsored by Springer, will be given to the author(s) of the most outstanding work included in the proceedings of SPIRE 2017 and presented at the event.

The main conference will be 26th September to 28th September 2017. The Workshop on Compression, Text and Algorithms (WCTA) will be held on September 29th. The venue will be the same of SPIRE.

Important Dates

  • Paper deadline: May 19th, 2017, anywhere on Earth
  • Notification: July 10th, 2017
  • Camera-ready due: July 24th, 2017
  • Early bird registration: July 29th, 2017
  • Main conference: 26th - 28th September, 2017
  • Workshop: 29th September, 2017

Scope
SPIRE 2017 covers research in all aspects of string processing, information retrieval, computational biology, and related applications. Typical topics of interest include (but are not limited to):

  • String Processing: string pattern matching, text indexing, data structures for string processing, text compression, compressed data structures, compressed string processing, text mining, 2D pattern matching, automata based string processing.
  • Information Retrieval (IR): retrieval models, indexing, evaluation, algorithms and data structures for IR, efficient implementation of IR systems, interface design, text classification and clustering, text analysis and mining, collaborative and content-based filtering, topic modeling for IR, search tasks (Web search, enterprise search, desktop search, legal search, cross-lingual retrieval, federated search, (micro) blog search, XML retrieval, multimedia retrieval), digital libraries.
  • Computational Biology: high-throughput DNA sequencing (assembly, read alignment, read error correction, metagenomics, transcriptomics, proteomics), evolution and phylogenetics, gene and regulatory element recognition, motif finding, protein structure prediction.

Location

Palermo is a city of Southern Italy. The city is noted for its history, culture, architecture and gastronomy. Palermo is located in the northwest of the island of Sicily, right by the Gulf of Palermo in the Mediterranean sea.
Central Palermo is well connected and has many transport options; there is a fast and frequent bus connection to the airport. Weather in Palermo at the end of September is generally warm and sunny, with an average daytime temperature around 25°C.



Venue

Eurostars Centrale Palace


Address: via Vittorio Emanuele 327,
90134 Palermo, Italy
Phone: +39 091 8539

The hotel is located just near the Quattro Canti square (at the crossing of the main streets of Palermo historical center: via Maqueda and via Vittorio Emanuele). The square is at the core of the UNESCO’s World Heritage "Arab-Norman Palermo and the Cathedral Churches of Cefalù and Monreale".



How to get there

The easiest way to reach Palermo is by flight. The international airport Falcone-Borsellino (Palermo, Punta Raisi) is 30 Km away from the town and is connected to Palermo by the motorway A29. The airport website indicates flight schedules and connections.

For the airport-city connections, there are two main options:

  • A shuttle bus (every 30 minutes, from 5 am to midnight), run by the company Prestia e Comandè. The bus itinerary follows the following stops: Airport, via Belgio, Piazza De Gasperi, via Croce Rossa, via Libertà (3 stops), Politeama, Palermo Central Station. Buses run every 30 minutes. The ticket costs 6,30 euros (single way) and can be bought at the dedicated kiosk inside the arrivals area of the airport, or onboard at the other stops. For more information please refer here.
  • A taxi service, run by the companies Coop. Trinacria (+39 091 225455 or +39 091 6878) and Coop. Autoradio taxi (+39 091 513311 or +39 091 8481). Fares from the airport to the city are about €40/€45. A suggested option is shared taxi. Two platforms are located at the arrivals area for the taxi sharing cars. The price is 8 euros per passenger and will be applied only with a minimum of 4 users. The service is provided by the Coop Radio Taxi Trinacria and by the Coop Autoradio Taxi. The shared taxi follows the same itinerary and stops as the shuttle bus. Specific stops within Palermo center can be arranged with the driver with an additional cost of 2 euros.
Note that the railway service is currently not operating due to upgrading works on the infrastructure.

Programme Committee Chairs

Steering Committee

Local Organizing Committee

Programme Committee

Invited Speakers

Flavio Chierichetti

Sapienza Università di Roma

Flavio Chierichetti is an associate professor in the Computer Science department at Sapienza Università di Roma. His interests intersect algorithmics, data mining and data modeling. Flavio obtained his PhD in Computer Science from Sapienza University; after his PhD, he held a post-doctoral position at Cornell University. Outside academia, Flavio spent various semesters as a visiting researcher at Google Mountain View. Flavio received an ERC Starting Grant, a Google Focused Research Award, and a SIR grant. He is also the recipient of the 2014 Best Young Researcher in Theoretical Computer Science award of the Italian Chapter of EATCS, and co-recipient of the 2015 KDD Best Paper Award.

Moshe Lewenstein

Bar Ilan University

Moshe Lewenstein is a professor in the Computer Science department at Bar-Ilan University, where he conducts research on algorithms with a special emphasis on data structures, texts and hardness in P. He received his Ph.D. from Bar-Ilan University in 2000 and spent the year 2000 in New York University as a visiting assistant professor. During the years of 2001 and 2002 he was with IBM Research in Yorktown Heights, NY in the department of Mathematical Sciences as the recipient of the prestigious Herman Goldstine postdoctoral fellowship. In late 2002 he joined the faculty of the Computer Science department in Bar Ilan University, where he is a full Professor since 2012. From 2007-2010 he served as the department chair. During the year 2012-2013 he was a visiting professor in the Computer Science department of the University of Waterloo, Canada. Since 2015 he is dean of Exact Sciences in Bar Ilan University. He has graduated numerous Ph.D. and M.Sc. students, co-authored over 70 papers, edited several books, serves as an editor of JDA and served on numerous PC committees, co-chairing CPM 2016, SPIRE 2013 and CPM 2006.

Stéphane Vialette

CNRS & Université Paris-Est Marne-la-Vallée

Stéphane Vialette is a CNRS senior researcher in the Gaspard-Monge Computer Science lab (LIGM UMR 8049) at Paris-Est Marne-la-Vallée University, where he conducts research on algorithms. He received his Ph.D. under the supervision of Christian Choffrut from Paris 7 University in 2001. During the years of 2002 and 2003, he was a postdoc researcher in the Biology department at Ecole Normale Supérieure. From late 2003 to 2007, he was an assistant professor in the Computer Science lab (LRI UMR 8623) at Paris-Sud University. In late 2007, he joined the Gaspard-Monge Computer Science lab (LIGM UMR 8049) in Paris-Est Marne-la-Vallée University as a CNRS researcher and he took the head of the algorithmic team (MoA) in 2011. Since 2015 he is a scientific project manager at INS2I CNRS (Institut des Sciences de l'Information et de leurs Interactions). He has graduated 4 Ph.D., co-authored over 45 journal papers and 1 book, and served on numerous PC committees.

Programme

Monday, 25 September 2017
19:00-21:00 Welcome cocktail at Eurostars Centrale Palace.


Tuesday, 26 September 2017
8:30-9:00 Registration
9:00-9:10 Welcome
9:10-9:30 Opening Lecture
Ricardo Baeza-Yates
The interaction between combinatorial pattern matching and search
Session 1 Chair: Gabriele Fici
9:30-10:30 Invited talk
Moshe Lewenstein
Conditional Lower Bounds for String Problems
10:30-11:00 Coffee Break
Session 2 Chair: Travis Gagie
11:00-11:25 Amihood Amir, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis and Jakub Radoszewski
Longest common factor after one edit operation
11:25-11:50 Giulia Bernardini, Nadia Pisanti, Solon P. Pissis and Giovanna Rosone
Pattern Matching on Elastic-Degenerate Text with Errors
11:50-12:15 Lavinia Egidi and Giovanni Manzini
Lightweight BWT and LCP Merging via the Gap algorithm
12:15-12:30 Tenma Nakamura, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda
Order preserving pattern matching on trees and DAGs
(Short paper)
12:30-14:30 Lunch
Session 3 Chair: Jakub Radoszewski
14:30-14:55 Johannes Fischer and Dominik Köppl
Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries
14:55-15:20 Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov and Simon Puglisi
On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation
15:20-15:45 Diego Arroyuelo, Rodrigo Canovas, Gonzalo Navarro and Rajeev Raman
LZ78 Compression in Low Main Memory Space
15:45-16:00 Yusaku Kaneta
Faster Practical Block Compression for Rank/Select Dictionaries
(Short paper)
16:00-16:30 Coffee Break
Session 4 Chair: Simon Puglisi
16:30-16:55 Gonzalo Navarro
A Self-Index on Block Trees
16:55-17:20 Shmuel Tomi Klein, Tamar C Serebro and Dana Shapira
Optimal Skeleton Huffman Trees
17:20-17:35 Philip Bille, Anders Roy Christiansen, Nicola Prezza and Frederik Rye Skjoldjensen
Succint Partial Sums and Fenwick Trees
(Short paper)
17:45-18:45 Business Meeting


Wednesday, 27 September 2017
Session 5 Chair: Ricardo Baeza-Yates
9:30-10:30 Invited talk
Flavio Chierichetti
Locality Sensitive Hashing, Similarities and Distortion
10:30-11:00 Coffee Break
Session 6 Chair: Hideo Bannai
11:00-11:25 Takuya Takagi, Keisuke Goto, Yuta Fujishige, Shunsuke Inenaga and Hiroki Arimura
Linear-size CDAWG: new repetition-aware indexing and grammar compression
11:25-11:50 Djamal Belazzougui and Fabio Cunial
Fast label extraction in the CDAWG
11:50-12:15 Nieves R. Brisaboa, Travis Gagie, Adrián Gómez-Brandón, Gonzalo Navarro and Jose R. Parama
Efficient Compression and Indexing of Trajectories
12:15-12:30 Golnaz Badkobeh, Juha Kärkkäinen, Simon Puglisi and Bella Zhukova
On suffix tree breadth
(Short paper)
12:30-14:00 Lunch
14:00-17:15 Excursion to Cefalù
17:15-19:00 Free time
19:00-20:00 Cocktail in Cefalù “Al Porticciolo”
20:00-22:45 Social Dinner in Cefalù “Al Porticciolo”


Thursday, 28 September 2017
Session 7 Chair: Marinella Sciortino
9:30-10:30 Invited talk
Stéphane Vialette
Permutationology: Stringology for Permutations
10:30-11:00 Coffee Break
Session 8 Chair: Golnaz Badkobeh
11:00-11:25 Dmitry Kosolobov, Florin Manea and Dirk Nowotka
Detecting One-variable Patterns
11:25-11:50 Mikhail Rubinchik and Arseny Shur
Counting Palindromes in Substrings
11:50-12:15 Mika Amit and Pawel Gawrychowski
Distinct squares in circular words
12:15-12:30 Szymon Grabowski
Regular Abelian periods and longest common Abelian factors on run-length encoded strings
(Short paper)
12:30-14:30 Lunch
Session 9 Chair: Nadia Pisanti
14:30-14:55 Shunsuke Kanda, Kazuhiro Morita and Masao Fuketa
Practical Implementation of Space-Efficient Dynamic Keyword Dictionaries
14:55-15:20 Cedric Chauve, Mark Jones, Manuel Lafond, Céline Scornavacca and Mathias Weller
Constructing a Consensus Phylogeny from a Leaf-Removal Distance
15:20-15:45Jarno Alanko and Tuukka Norri
Greedy shortest common superstring approximation in compact space
15:45-16:00 Heikki Hyyrö
Mining bit-parallel LCS length algorithms
(Short paper)
16:00-16:30 Coffee Break
Session 10 Chair: Pawel Gawrychowski
16:30-16:55 Alessio Conte, Roberto Grossi, Andrea Marino, Takeaki Uno and Luca Versari
Listing Maximal Independent Sets with Minimal Space and Bounded Delay
16:55-17:20 Jan Broß, Simon Gog, Matthias Hauck and Marcus Paradies
Fast Construction of Compressed Web Graphs
17:20-17:35 Philip Bille, Finn Fernstrøm and Inge Li Gørtz
Tight Bounds for Top Tree Compression
(Short paper)
17:35-18:00 Closing

Registration

At least one author for each accepted paper must register at the conference at the appropriate conference rate. Registration deadlines and charges are:

Registration Deadline Regular Student
Early July 29th, 2017 € 390 € 250
Late September 11th, 2017 € 460 € 300

For student registrations, please send us an email to spire2017@easychair.org with subject line "Registration - Student" in which you declare that you are currently a student and you do not hold a PhD.

The registration fees include:
  • Attendance to SPIRE 2017 sessions and invited talks
  • LNCS Proceedings (electronic version)
  • Conference material
  • Coffee breaks
  • Lunches
  • Social dinner and excursion

    • Extra tickets for the social event (excursion and dinner) will be available on site at the cost of 50,00 euros per person.

    Method of payment: Bank Transfer
    Bank account holder: Università degli Studi di Palermo
    IBAN: IT 09 A 02008 04682 000300004577
    SWIFT code: UNCRITMMPAE
    ABI code: 02008
    CAB code: 04682
    Bank account number: 000300004577
    Bank Name: UNICREDIT SPA
    Address: VIA ROMA 185, 90133 PALERMO

    Along with the payment, the following information must be included as the reason of the payment: "Registration fee SPIRE17 – DMI Palermo - name of the participant - affiliation". In order to actually perform a registration, please send us a receipt of payment by email to spire2017@easychair.org.
    Please make sure that the bank transfer is free of charge for the beneficiary.

    History

    SPIRE 2017 is the 24th edition of the International Symposium on String Processing and Information Retrieval. The first four editions of the conference focused primarily on string processing and were held in South America under the title WSP (South American Workshop on String Processing). WSP was transformed into SPIRE in 1998, when the scope of the conference was broadened to include information retrieval.

    The list of past venues is the following:

    • 23rd SPIRE: Beppu, Japan, October 2016
    • 22nd SPIRE: London, UK, September 2015
    • 21st SPIRE: Ouro Preto, Brazil, October 2014
    • 20th SPIRE: Jerusalem, Israel, October 2013
    • 19th SPIRE: Cartagena, Columbia, October 2012
    • 18th SPIRE: Pisa, Italy, October 2011
    • 17th SPIRE: Los Cabos, Mexico, October, 2010
    • 16th SPIRE: Saariselkä, Finland, August, 2009
    • 15th SPIRE: Melbourne Australia, November, 2008
    • 14th SPIRE: Santiago, Chile, October 2007
    • 13th SPIRE: Glasgow, Scotland, October 2006
    • 12th SPIRE: Buenos Aires, Argentina, October 2005
    • 11th SPIRE: Padova, Italy, October 2004
    • 10th SPIRE: Manaus, Brazil, October 2003
    • 9th SPIRE: Lisbon, Portugal, September 2002
    • 8th SPIRE: Laguna de San Rafael, Chile, November 2001
    • 7th SPIRE: A Coruna, Spain, September 2000
    • 6th SPIRE: Cancun, Mexico, September 1999
    • 5th SPIRE: Santa Cruz, Bolivia, September 1998
    • WSP 1997: Valparaiso, Chile
    • WSP 1996: Recife, Brazil
    • WSP 1995: Valparaiso, Chile
    • WSP 1993: Belo Horizonte, Brazil