16. SPIRE 2009: Saariselkä, Finland

Jussi Karlgren, Jorma Tarhio, Heikki Hyyrö (Eds.): String Processing and Information Retrieval, 16th International Symposium, SPIRE 2009, Saariselkä, Finland, August 25-27, 2009, Proceedings. Lecture Notes in Computer Science 5721 Springer 2009, ISBN 978-3-642-03783-2

Algorithms on Trees

Travis Gagie, Simon J. Puglisi, Andrew Turpin:
Range Quantile Queries: Another Virtue of Wavelet Trees. 1-6
Daiji Fukagawa, Tatsuya Akutsu, Atsuhiro Takasu:
Constant Factor Approximation of Edit Distance of Bounded Height Unordered Trees. 7-17
Nieves R. Brisaboa, Susana Ladra, Gonzalo Navarro:
k2-Trees for Compact Web Graph Representation. 18-30
Taehyung Lee, Joong Chae Na, Kunsoo Park:
On-Line Construction of Parameterized Suffix Trees. 31-38

Alan Tam, Edward Wu, Tak Wah Lam, Siu-Ming Yiu:
Succinct Text Indexing with Wildcards. 39-50
Enno Ohlebusch, Simon Gog:
A Compressed Enhanced Suffix Array Supporting Fast String Matching. 51-62
Jouni Sirén:
Compressed Suffix Arrays for Massive Data. 63-74
Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan, Jeffrey Scott Vitter:
On Entropy-Compressed Text Indexing in External Memory. 75-89

Daisuke Okanohara, Kunihiko Sadakane:
A Linear-Time Burrows-Wheeler Transform Using Induced Sorting. 90-101
Kazumasa Inagaki, Yoshihiro Tomizawa, Hidetoshi Yokoo:
Novel and Generalized Sort-Based Transform for Lossless Data Compression. 102-113
Joaquín Adiego, Nieves R. Brisaboa, Miguel A. Martínez-Prieto, Felipe Sánchez-Martínez:
A Two-Level Structure for Compressing Aligned Bitexts. 114-121
Nieves R. Brisaboa, Susana Ladra, Gonzalo Navarro:
Directly Addressable Variable-Length Codes. 122-130

Marcelo Mendoza, Juan Zamora:
Identifying the Intent of a User Query Using Support Vector Machines. 131-142
Niranjan Balasubramanian, James Allan:
Syntactic Query Models for Restatement Retrieval. 143-155
Olga Craveiro, Joaquim Macedo, Henrique Madeira:
Use of Co-occurrences for Temporal Expressions Annotation. 156-164
André Pinto Geraldo, Viviane Pereira Moreira, Marcos André Gonçalves:
On-Demand Associative Cross-Language Information Retrieval. 165-173
Connie R. Adsett, Yannick Marchand:
A Comparison of Data-Driven Automatic Syllabification Methods. 174-181

Wing-Kai Hon, Rahul Shah, Shih-Bin Wu:
Efficient Index for Retrieving Top-k Most Frequent Documents. 182-193
Marjan Celikik, Hannah Bast:
Fast Single-Pass Construction of a Half-Inverted Index. 194-205
Esteban Feuerstein, Mauricio Marín, Michel Mizrahi, Veronica Gil Costa, Ricardo A. Baeza-Yates:
Two-Dimensional Distributed Inverted Files. 206-213
Gonzalo Navarro, Leena Salmela:
Indexing Variable Length Substrings for Exact and Approximate Matching. 214-221

Cinzia Pizzi, Mauro Bianco:
Expectation of Strings with Mismatches under Markov Chain Distribution. 222-233
Amihood Amir, Gad M. Landau, Joong Chae Na, Heejin Park, Kunsoo Park, Jeong Seop Sim:
Consensus Optimizing Both Distance Sum and Radius. 234-242
Christina Boucher:
Faster Algorithms for Sampling and Counting Biological Sequences. 243-253

Amihood Amir, Haim Parienty:
Towards a Theory of Patches. 254-265
Guy Feigenblat, Ofra Itzhaki, Ely Porat:
The Frequent Items Problem, under Polynomial Decay, in the Streaming Model. 266-276
Zvi Gotthilf, Moshe Lewenstein:
Improved Approximation Results on the Shortest Common Supersequence Problem. 277-284

Ariel Shiftan, Ely Porat:
Set Intersection and Sequence Matching. 285-294
Raphaël Clifford, Aram Wettroth Harrow, Alexandru Popa, Benjamin Sach:
Generalised Matching. 295-301
Lucian Ilie, Liviu Tinta:
Practical Algorithms for the Longest Common Extension Problem. 302-309

Flavio Ferrarotti, Mauricio Marín, Marcelo Mendoza:
A Last-Resort Semantic Cache for Web Queries. 310-321
Shanu Sushmita, Hideo Joho, Mounia Lalmas:
A Task-Based Evaluation of an Aggregated Search Interface. 322-333
Walid Magdy, Kareem Darwish, Motaz El-Saban:
Efficient Language-Independent Retrieval of Printed Documents without OCR. 334-343
Yoram Bachrach, Ralf Herbrich, Ely Porat:
Sketching Algorithms for Approximating Rank Correlations in Collaborative Filtering Systems. 344-352