Table of Contents
Crowdsourcing and Recommendation
Querying the Web Graph (Invited Talk) Marc Najork 1
Incremental Algorithms for Effective and Efficient Query Recommendation Daniele Broccolo Ophir Frieder Franco Maria Nardini Raffaele Perego Fabrizio Silvestri 13
Fingerprinting Ratings for Collaborative Filtering - Theoretical and Empirical Analysis Yoram Bachrach Ralf Herbrich 25
On Tag Spell Checking Franco Maria Nardini Fabrizio Silvestri Hossein Vahabi Pedram Vahabi Ophir Frieder 37
Indexes and Compressed Indexes
Compressed Self-Indices Supporting Conjunctive Queries on Document Collections Diego Arroyuelo Senén González Mauricio Oyarzún 43
String Retrieval for Multi-pattern Queries Wing-Kai Hon Rahul Shah Sharma V. Thankachan Jeffrey Scott Vitter 55
Colored Range Queries and Document Retrieval Travis Gagie Gonzalo Navarro Simon J. Puglisi 67
Range Queries over Untangled Chains Francisco Claude J. Ian Munro Patrick K. Nicholson 82
Theory
Multiplication Algorithms for Monge Matrices Luís M.S. Russo 94
Why Large Closest String Instances Are Easy to Solve in Practice Christina Boucher Kathleen Wilkie 106
A PTAS for the Square Tiling Problem Amihood Amir Alberto Apostolico Gad M. Landau Oren Sar Shalom 118
On the Hardness of Counting and Sampling Center Strings Christina Boucher Mohamed Omar 127
String Algorithms I
Counting and Verifying Maximal Palindromes Tomohiro I Shunsuke Inenaga Hideo Bannai Masayuki Takeda 135
Identifying SNPs without a Reference Genome by Comparing Raw Reads Pierre Peterlongo Nicolas Schnel Nadia Pisanti Marie-France Sagot Vincent Lacroix 147
Dynamic Z-Fast Tries Djamal Belazzougui Paolo Boldi Sebastiano Vigna 159
Improved Fast Similarity Search in Dictionaries Daniel Karch Dennis Luxen Peter Sanders 173
Compression
Training Parse Trees for Efficient VF Coding Takashi Uemura Satoshi Yoshida Takuya Kida Tatsuya Asai Seishi Okamoto 179
Algorithms for Finding a Minimum Repetition Representation of a String Atsuyoshi Nakamura Tomoya Saito Ichigaku Takigawa Hiroshi Mamitsuka Mineichi Kudo 185
Faster Compressed Dictionary Matching Wing-Kai Hon Tsung-Han Ku Rahul Shah Sharma V. Thankachan Jeffrey Scott Vitter 191
Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval Shanika Kuruppu Simon J. Puglisi Justin Zobel 201
Querying and Search User Experience
Standard Deviation as a Query Hardness Estimator Joaquín Pérez-Iglesias Lourdes Araujo 207
Using Related Queries to Improve Web Search Results Ranking Georges Dupret Ricardo Zilleruelo-Ramos Sumio Fujita 213
Evaluation of Query Performance Prediction Methods by Range Joaquín Pérez-Iglesias Lourdes Araujo 225
Mining Large Query Induced Graphs towards a Hierarchical Query Folksonomy Alexandre P. Francisco Ricardo Baeza-Yates Arlindo L. Oliveira 237
String Algorithms II
Finite Automata Based Algorithms for the Generalized Constrained Longest Common Subsequence Problems Effat Farhana Jannatul Ferdous Tanaeem Moosa M. Sohel Rahman 243
Restricted LCS Zvi Gotthilf Danny Hermelin Gad M. Landau Moshe Lewenstein 250
Extracting Powers and Periods in a String from Its Runs Structure Maxime Crochemore Costas Iliopoulos Marcin Kubica Jakub Radoszewski Wojciech Rytter Tomasz Walen 258
On Shortest Common Superstring and Swap Permutations Zvi Gotthilf Moshe Lewenstein Alexandru Popa 270
Document Analysis and Comparison
A Self-Supervised Approach for Extraction of Attribute-Value Pairs from Wikipedia Articles Wladmir C. Brandão Edleno S. Moura Altigran S. Silva Nivio Ziviani 279
Temporal Analysis of Document Collections: Framework and Applications Omar Alonso Michael Gertz Ricardo Baeza-Yates 290
Text Comparison Using Soft Cardinality Sergio Jimenez Fabio Gonzalez Alexander Gelbukh 297
Hypergeometric Language Model and Zipf-Like Scoring Function for Web Document Similarity Retrieval Felipe Bravo-Marquez Gaston L'Huillier Sebastián A. Ríos Juan D. Velásquez 303
Compressed Indexes
Dual-Sorted Inverted Lists (Invited Talk) Gonzalo Navarro Simon J. Puglisi 309
CST++ Enno Ohlebusch Johannes Fischer Simon Gog 322
Succinct Representations of Dynamic Strings Meng He J. Ian Munro 334
Computing Matching Statistics and Maximal Exact Matches on Compressed Full-Text Indexes Enno Ohlebusch Simon Gog Adrian Kügel 347
The Gapped Suffix Array: A New Index Structure for Fast Approximate Matching Maxime Crochemore German Tischler 359
String Matching
Parameterized Searching with Mismatches for Run-Length Encoded Strings (Extended Abstract) Alberto Apostolico Péter L. Erdos Alpár Jüttner 365
Fast Bit-Parallel Matching for Network and Regular Expressions Yusaku Kaneta Shin-ichi Minato Hiroki Arimura 372
String Matching with Variable Length Gaps Philip Bille Inge Li Gørtz Hjalte Wedel Vildhøj David Kofoed Wind 385
Approximate String Matching with Stuck Address Bits Amihood Amir Estrella Eisenberg Orgad Keller Avivit Levy Ely Porat 395
Author Index 407
