دانلود کتاب String Processing and Information Retrieval: 14th International Symposium, SPIRE 2007 Santiago, Chile, October 29-31, 2007 Proceedings (Lecture Notes in Computer Science, 4726)

فهرست مطالب :

Title Page
Preface
Organization
Table of Contents
A Chaining Algorithm for Mapping cDNA Sequences to Multiple Genomic Sequences
Introduction
The Fragments
Definitions
Computing the Fragments
Chaining Fragments with Overlaps
Geometry-Based Solution
Special Cases
Using $multi-MUMs$ or Rare $multi-MEMs$
Restricting the Amount of Overlapping
Experimental Results
Conclusions
Edge-Guided Natural Language Text Compression
Introduction
Modelling Natural Language Texts
$K$-th Order Models
Edge-Guided Text Compression
Definitions
Edge-Guided Compression Algorithm
Example
Evaluation
Conclusions and Future Work
Local Transpositions in Alignment of Polyphonic Musical Sequences
Introduction
Representation of Musical Pieces
Alignment, Best-Fit and Edit Distance
Transposition Invariance
Limitations of the Representation of Notes in Polyphony
Multiple Local Transpositions
Algorithm
Definitions and Problem
Algorithm
Improvement
Demonstrative Example
Experiments
Scoring Scheme
Monophonic Music
Polyphonic Music
Discussion and Conclusion
Efficient Computations of 1 and ∞Rearrangement Distances
Introduction
Approximating the $\\ell$_1 Rearrangement Distance
Preliminaries
The Approximation Algorithm
The $\\ell_\\infty$ Rearrangement Distance
Exact $\\ell_\\infty$ Rearrangement Distance
Approximating the $\\ell_\\infty$ Distance
Generalized LCS
Introduction
Preliminaries
Two Dimensional LCS
$2D\\_LCS$ Is $ \\cal{NP}$-Hard
Largest Common Subtree (LCStree)
Constrained-LCStree
LCStree of 3 and More Trees (LCSktrees)
Unordered Trees
Constrained LCStree for 3 and More Unordered Trees
Ordered Trees
LCSktree for Ordered Trees
Constrained LCSKtree for Ordered Trees (Con-LCSktree)
Conclusions and Open Problems
Exploiting Genre in Focused Crawling
Introduction
Related Work
Overview of the Proposed Approach to Focused Crawling
Experimental Evaluation
Experimental Design and Setup
Effectiveness
Efficiency and Scalability
Conclusions
Admission Policies for Caches of Search Engine Results
Introduction
Data Characterization
Polluting Queries
Admission Policies and Caching
Stateful Features
Stateless Features
Evaluation
Experimental Setting
Results
On the Design of New Features
Conclusions
A Pocket Guide toWeb History
Introduction
Related Work
PageRank Score Normalization
Rank Synopses
Rank Synopses Construction
Reconstructing Historical PageRank Scores
Rank Synopses Maintenance
Search Engine Integration
Experimental Evaluation
Accuracy and Storage
Reconstructing Non-input Observations
Scalability
Summing Up
Conclusions
Jump-Matching with Errors
Introduction
Jump-Matching
Approximate Jump-Matching
Deterministic Algorithm
Randomized Algorithm
Estimating Number of Citations Using Author Reputation
Introduction
Related Work
Dataset
Features
Experimental Results
Conclusions and Future Work
A Fast and Compact Web Graph Representation
Introduction
Related Work
Re-Pair and Our Approximate Version
A Compressed Graph Representation
Experimental Results
Conclusions
A Filtering Algorithm for $k$-Mismatch with Don’t Cares
Introduction
Related Work and Previous Results
Problem Definition and Preliminaries
Filtering for the $k$-Mismatch Problem
The New Filtering Algorithm
Fewer Than $f$ Frequent Symbols
At Least $f$ Frequent Symbols
Discussion
Compact Set Representation for Information Retrieval
Introduction
Sets and Set Operations
Set Representations
Intersection Algorithms
Practical Indexing
Experiments
Approximate Swap and Mismatch Edit Distance
Introduction
Problem Definition
Convolutions
Algorithm for Binary Alphabets
Grouping Text Segments by Parity of Starting and Ending Location
Grouping the Pattern Segments
Segments with Equal Parity Start or End
The Odd-Even Even-Odd Segments
Grouping Text and Pattern Segments by Length
The Convolutions for the Odd-Even Even-Odd Segments Case
The Odd-Odd Even-Even Segments
The Convolutions for the Odd-Odd Even-Even Segments Case
Approximate Solution for General Alphabet
Reduction from $Mismatch to Swap and Mismatch$
Approximating Constrained LCS
Introduction
Preliminaries
Approximating LCS
Approximating Constrained LCS
An $O(mn)$ Time Approximation
A Linear Time Approximation
Open Questions
Tuning Approximate Boyer-Moore for Gene Sequences
Introduction
Previous Work
Algorithm for the $k$-Mismatch Problem
Algorithms for the $k$-Difference Problem
Experimental Results
Concluding Remarks
Optimal Self-adjusting Trees for Dynamic String Data in Secondary Storage
Introduction
Self-adjusting Suffix Tree
Updating the Partitions
Self-adjusting Performance
Discussion
Conclusion
Indexing a Dictionary for Subset Matching Queries
Introduction
A Haplotype Trie from a Genotype Dictionary
An $O(nm+|\\Sigma|^k n\\lg n)$ Time Construction
An $O(nm+|\\Sigma|^k n\\lg m)$ Time Construction
An $O(nm+|\\Sigma|^k n +|\\Sigma|^{k/2} n\\lg (\\min\\{n,m\\}))$ Time Construction
Fractional Cascading
Conclusion and Open Problems
Extending Weighting Models with a Term Quality Measure
Introduction
Related Studies
Methodology
Deriving Term Quality from Parts of Speech
Integrating Term Quality to Term Weighting
Evaluation
Conclusion
Highly Frequent Terms and Sentence Retrieval
Introduction
Related Work
Highly Frequent Terms and Sentence Retrieval
Experiments
Conclusions and Future Work
Implicit Compression Boosting with Applications to Self-indexing
Introduction
Definitions
Previous Results
Entropy-Bound Structures for Bit Vectors
Wavelet Trees and Entropy-Bound Structures for Sequences
Full-Text Self-indexes
Implicit Compression Boosting
Discussion
Application to Space-Efficient Construction of (Dynamic) Self-indexes
Final Practical Considerations
A Web-Page Usage Prediction Scheme Using Weighted Suffix Trees
Introduction
Definitions and Background
Prediction/Recommendation Model
WAS Maintenance
WAS Clustering
WAS Cluster Representation
WST Utilization - Recommendation/Prediction Method
Evaluation
Conclusions and Open Issues
Enhancing Educational-Material Retrieval Using Authored-Lesson Metadata
Introduction
Authoring a Course as a Graph
Querying a Repository from Inside the Lesson Graph
Using the Lesson Graph to Evaluate Potential Results
Using Value Restrictions as Classifiers
Using Value Suggestions as Classifiers
Combining Classifiers
Experiments
Description
Result Analysis
Discussion
Approximate String Matching with Lempel-Ziv Compressed Indexes
Introduction and Related Work
Our Contribution in Context
An Improved $q$-Samples Index
Varying the Error Distribution
Partial $q$-Sample Matching
A Hybrid $q$-Samples Index
Using a Lempel-Ziv Self-index
Handling Different Lengths
A Hybrid Lempel-Ziv Index
Practical Issues and Testing
Conclusions and Future Work
Algorithms for Weighted Matching
Introduction
Definitions
Previous Work
Shift-Add for Weighted Matching
Enumeration Algorithms
Experimental Results
Conclusions
Efficient Text Proximity Search
Introduction
Related Work
Processing Model
Proximity Scoring
Proximity Scoring Models
Büttcher\'s Scoring Model
Modified Büttcher Scoring Model
Indexing and Evaluation Framework
Precomputed Index Lists and Evaluation Strategies
Index List Pruning
Evaluation
Setup
Results with Unpruned Index Lists
Results with Pruned Index Lists
Conclusion
Prefix-Shuffled Geometric Suffix Tree
Introduction
Preliminaries
RMSD: The Root Mean Square Deviation
Geometric Suffix Trees
Prefix-Shuffled Structures
Prefix-Shuffled Geometric Suffix Trees
Experiments
Discussion
Author Index