Welcome to WTCA 2017

This is an annual satellite workshop of SPIRE mostly focusing on compression, data structures and string processing topics. We invite an abstract for presentation (15-25 minutes) of preferably unpublished work, published results, work in progress, surveys of interest, open problems, etc. Since WCTA has no proceedings, it will not preclude a possibility of submitting presenting results to other conferences or publishing them in journals. WCTA will be free for all attendees.

Important Dates

  • Abstract deadline: August 18th, 2017, anywhere on Earth
  • Notification: August 27th, 2017
  • Workshop: 29th September, 2017

Invited Speakers

Knut Reinert

Freie Universität Berlin

Knut Reinert holds the chair of the Algorithms in Bioinformatics group at the Institute of Bioinformatics at Freie Universität Berlin. In addition, he is a Max Planck fellow at the Max Planck Institute for Molecular Genetics. He and his team focus on the development of novel algorithms and data structures for practical problems arising in the analysis of biomedical mass data and the efficient implementation of the algorithms in software libraries like SeqAn or OpenMS. Previously, Knut did his Phd at the Max-Planck-Institute for Computer Science in the group of Kurt Mehlhorn. After receiving his PhD he joint Gene Myers in the Informatics Research team at Celera Genomics, where he worked on bioinformatics algorithms and software for genome assembly and mass spectrometry. In 2002 he became full professor at the Freie Universtät Berlin and since then graduated numerous PhD and MSc students and coauthored around 100 research papers. He served on numerous PC committees as committe member and (co)chair.

Sebastiano Vigna

Università degli Studi di Milano

Sebastiano Vigna's research focuses on the interaction between theory and practice. He has worked on highly theoretical topics such as computability on the reals, distributed computability, self-stabilization, minimal perfect hashing, succinct data structures, query recommendation, algorithms for large graphs, pseudorandom number generation, theoretical/experimental analysis of spectral rankings such as PageRank, and axiomatization of centrality measures, but he is also (co)author of several widely used software tools ranging from high-performance Java libraries to a model-driven software generator, a search engine, a crawler, a text editor and a graph compression framework. In 2011 he collaborated to the computation the distance distribution of the whole Facebook graph, from which it was possible to evince that on Facebook there are just 3.74 degrees of separation. Recently, he participated to the analysis of the largest available public web crawl (Common Crawl 2012), which led to the publication of the first open ranking of web sites. His work on Elias-Fano coding and quasi-succinct indices is at the basis of the code of Facebook's "folly" library . He also collaborated to the first open ranking of Wikipedia pages, which is based on his body of work on centrality in networks. His pseudorandom number generator xorshift128+ is currently used by the JavaScript engine V8 of Chrome, as well by Safari and Firefox, and it is the stock generator of the Erlang language. Sebastiano Vigna obtained his PhD in Computer Science from the Università degli Studi di Milano, where he is currently a Full Professor.


Friday, 29 September 2017
8:45-9:00 Opening and Welcome
Session A
9:00-09:30 Short tutorial
Alistair Moffat
ANS Compression
09:30-09:50 Nieves R. Brisaboa, Travis Gagie, Adrian Gomez-Brandon, and Gonzalo Navarro
Two Dimensional Block Trees
09:50-10:30 Hayam Alamro, Lorraine A.K. Ayad, Panagiotis Charalampopoulos, Costas S. Iliopoulos, and Solon P. Pissis
Longest Common Prefixes with k-Mismatches & Applications
10:30-10:50 Coffee Break
Session B
10:50-11:40 Invited Talk
Sebastiano Vigna
(Quasi) Succinct Data Structures and Information Retrieval
11:40-12:00 Nicola Prezza
String Attractors
12:00-12:20 Sahar Hooshmand and Sharma V. Thankachan
Non-overlapping Indexing in External Memory
12:20-14:00 Lunch
Session C
14:00-14:50 Invited Talk
Knut Reinert
Engineering meets Biomedicine
14:50-15:10 Jose Fuentes-Sepulveda and Gonzalo Navarro
Space-efficient parallel construction of the Burrows-Wheeler transform
15:10-15:30 Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Piatkowski
Indexing the Bijective BWT
15:30-15:50 Coffee Break
Session D
15:50-16:10 Jacqueline W. Daykin, Richard Groult, Yannick Guesnet, Thierry Lecroq, Arnaud Lefebvre, Martine Leonard, Laurent Mouchard, Elise Prieur-Gaston, and Bruce Watson
Efficient pattern matching in degenerate strings with the Burrows-Wheeler transform
16:10-16:30 Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Almost linear time computation of maximal repetitions in run length encoded strings

Programme Chairs


Please submit abstracts by emailing copies (preferable PDF) to both WCTA co-chiars (sgog@ebay.com, giovanna.rosone@unipi.it).