String Processing and Information Retrieval

The papers contained in this volume were presented at the 12th edition of the International Symposium on String Processing and Information Retrieval (SPIRE), held November 2 4, 2005, in Buenos Aires, Argentina. They were - lected from 102 papers submitted from 25 countries in response to the Call for Papers.Atotalof27submissionswereacceptedasfullpapers,yieldinganacc- tancerateofabout26%.Inviewofthelargenumberofgood-qualitysubmissions the conference program also included 17 short papers that also appear in the proceedings.In addition, the Steering Committee invited the following speakers: Prabhakar Raghavan (Yahoo! Research, USA), Paolo Ferragina (University of Pisa, Italy), and Gonzalo Navarro (University of Chile, Chile). Papers solicited for SPIRE 2005 were meant to constitute original cont- butions to areas such as string processing (dictionary algorithms, text sear- ing, pattern matching, text compression, text mining, natural language p- cessing, and automata-basedstring processing); information retrieval languages, applications, and evaluation (IR modeling, indexing, ranking and ?ltering, - terface design, visualization, cross-lingual IR systems, multimedia IR, digital libraries,collaborativeretrieval,Web-relatedapplications,XML, information- trievalfromsemi-structureddata,textmining,andgenerationofstructureddata from text); and interaction of biology and computation (sequencing and app- cations in molecular biology, evolution and phylogenetics, recognition of genes and regulatory elements, and sequence-driven protein structure prediction).

Inhalt
String Processing and Information Retrieval 2005.- Enhanced Byte Codes with Restricted Prefix Properties.- Experimental Analysis of a Fast Intersection Algorithm for Sorted Sequences.- Compressed Perfect Embedded Skip Lists for Quick Inverted-Index Lookups.- XML Retrieval with a Natural Language Interface.- Recommending Better Queries from Click-Through Data.- A Bilingual Linking Service for the Web.- Evaluating Hierarchical Clustering of Search Results.- Counting Suffix Arrays and Strings.- Towards Real-Time Suffix Tree Construction.- Rank-Sensitive Data Structures.- Cache-Conscious Collision Resolution in String Hash Tables.- Measuring the Difficulty of Distance-Based Indexing.- N-Gram Similarity and Distance.- Using the k-Nearest Neighbor Graph for Proximity Searching in Metric Spaces.- Classifying Sentences Using Induced Structure.- Counting Lumps in Word Space: Density as a Measure of Corpus Homogeneity.- Multi-label Text Categorization Using K-Nearest Neighbor Approach with M-Similarity.- Lydia: A System for Large-Scale News Analysis.- Composite Pattern Discovery for PCR Application.- Lossless Filter for Finding Long Multiple Approximate Repetitions Using a New Data Structure, the Bi-factor Array.- Linear Time Algorithm for the Generalised Longest Common Repeat Problem.- Application of Clustering Technique in Multiple Sequence Alignment.- Stemming Arabic Conjunctions and Prepositions.- XML Multimedia Retrieval.- Retrieval Status Values in Information Retrieval Evaluation.- A Generalization of the Method for Evaluation of Stemming Algorithms Based on Error Counting.- Necklace Swap Problem for Rhythmic Similarity Measures.- Faster Generation of Super Condensed Neighbourhoods Using Finite Automata.- Restricted Transposition Invariant Approximate String Matching UnderEdit Distance.- Fast Plagiarism Detection System.- A Model for Information Retrieval Based on Possibilistic Networks.- Comparison of Representations of Multiple Evidence Using a Functional Framework for IR.- Deriving TF-IDF as a Fisher Kernel.- Utilizing Dynamically Updated Estimates in Solving the Longest Common Subsequence Problem.- Computing Similarity of Run-Length Encoded Strings with Affine Gap Penalty.- L 1 Pattern Matching Lower Bound.- Approximate Matching in the L ??? Metric.- An Edit Distance Between RNA Stem-Loops.- A Multiple Graph Layers Model with Application to RNA Secondary Structures Comparison.- Normalized Similarity of RNA Sequences.- A Fast Algorithmic Technique for Comparing Large Phylogenetic Trees.- Practical and Optimal String Matching.- A Bit-Parallel Tree Matching Algorithm for Patterns with Horizontal VLDC's.- A Partition-Based Efficient Algorithm for Large Scale Multiple-Strings Matching.