String Processing and Information Retrieval

Name: String Processing and Information Retrieval | 25th International Symposium, SPIRE 2018, Lima, Peru, October 9-11, 2018, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

25th International Symposium, SPIRE 2018, Lima, Peru, October 9-11, 2018, Proceedings

Travis Gagie Alistair Moffat Gonzalo Navarro Ernesto Cuadros-Vargas(Herausgeber*in)

Springer (Verlag)

Erschienen am 1. Oktober 2018

XVII, 364 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-030-00479-8 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Organization
Abstracts of Invited Talks
Techniques for Grammar-Based Compression
Mining the Integrated Connectedness of Biomedical Systems
Data Compression: The Whole is Larger than the Sum of Its Parts
Contents
Recoloring the Colored de Bruijn Graph
1 Introduction
2 Preliminaries
3 Recoloring a Colored de Bruijn Graph with the Minimum Number of Colors
4 Recoloring the Colored de Bruijn Graph
4.1 A Practical Algorithm
4.2 Implementation and Datasets
4.3 Experiments
5 Conclusion
References
Efficient Computation of Sequence Mappability
1 Introduction
2 Preliminaries
3 O(n logk+1 n)-Time and O(n)-Space Algorithm
4 O(nmk)-Time and O(n)-Space Algorithm
5 Computing (k,m)-Mappability for All k or for All m
6 Conditional Hardness for k,m = (logn)
7 Final Remarks
References
Longest Common Prefixes with k-Errors and Applications
1 Introduction
1.1 Our Model
1.2 Related Work
1.3 Our Results
2 Preliminaries
3 Computing PLCPk
3.1 Bounding the PLCPk Values
3.2 Improved Algorithm for Hamming Distance
3.3 Extension to Edit Distance
4 Applications
4.1 Genome Mappability Data Structure
4.2 Longest Common Substring with k-Errors
4.3 All-Pairs Suffix/Prefix Overlaps with k-Errors
A K-Combinations Generation Process
References
Longest Property-Preserved Common Factor
1 Introduction
1.1 Definitions and Notation
1.2 Algorithmic Toolbox
2 Square-Free-Preserved Matching Statistics
3 Longest Periodic-Preserved Common Factor
4 Final Remarks
References
Adaptive Computation of the Discrete Fréchet Distance
1 Introduction
2 Preliminaries
3 An Opportunistic Dynamic Program
4 Parameterized Upper Bound
5 Discussion
References
Indexed Dynamic Programming to Boost Edit Distance and LCSS Computation
1 Introduction
2 Preliminaries
2.1 Parikh Vector
2.2 Rank and Select in Strings
3 Adaptive Dynamic Programs
3.1 LCSS and DI-Edit Distance
3.2 Levenshtein Distance, or DIR-Edit Distance
3.3 DR-Edit Distance and IR-Edit Distance
4 Experiments
5 Discussion
References
Compressed Communication Complexity of Longest Common Prefixes
1 Introduction
2 Definition and Preliminaries
3 Noisy Search
4 Communication Protocol for Lcp
4.1 The Lcpk Case
5 Self-referencing LZ77
5.1 Lcpk in the Self-referential Case
6 Obtaining a Trade-Off via D-ary Search
References
New Structures to Solve Aggregated Queries for Trips over Public Transportation Networks
1 Introduction
2 A Model to Describe a Public Transportation Network
3 Towards a Practical Representation: Common Structures to Represent the Offer
4 Topology&Trip-Aware CTR (TTCTR): A Representation Focused on User's Trips
4.1 Representing the Spatial Component of TTCTR with a CSA
4.2 Representing the Temporal Component of TTCTR with a WM
5 Dealing with Aggregated Data: Accumulated-Matrix
6 Performing Queries on TTCTR and AcumM
7 Experimental Evaluation
8 Conclusions and Future Work
References
3DGraCT: A Grammar-Based Compressed Representation of 3D Trajectories
1 Introduction
2 Background
3 3DGraCT
4 Querying
5 Experimental Evaluation
6 Conclusions
A Appendix
References
Towards a Compact Representation of Temporal Rasters
1 Introduction
2 Related Work
3 T-k2raster: A Temporal Representation for Raster Data
4 Querying Temporal Raster Data
5 Experimental Evaluation
6 Conclusions and Future Work
References
On Extended Special Factors of a Word
1 Introduction
2 A Lower Bound on Extended Bispecial Factors
3 Minimal Absent Words via Extended Special Factors
3.1 The Data Structure
3.2 Sequence Comparison
References
Truncated DAWGs and Their Application to Minimal Absent Word Problem
1 Introduction
2 Preliminaries
2.1 Strings
2.2 LZ77 Factorization
2.3 Suffix Trees and DAWGs
2.4 k-truncated Suffix Trees
3 k-truncated DAWGs
4 Construction of Truncated DAWG
5 Applications of Truncated DAWGs for Minimal Absent Words
6 Conclusion
References
The Colored Longest Common Prefix Array Computed via Sequential Scans
1 Introduction
2 Preliminaries
3 Colored Longest Common Prefix Array
4 Lightweight Computation of cLCP
5 Multi-string ACS Computation by cLCP
6 Preliminary Experiments
7 Conclusion and Future Work
References
Early Commenting Features for Emotional Reactions Prediction
1 Introduction
2 Related Work
3 Problem Definition
4 Features
4.1 Term Frequencies
4.2 Early Commenting Features
5 Experimental Setup
5.1 Dataset
5.2 Experimental Settings
6 Results and Discussion
7 Conclusions and Future Work
References
Block Palindromes: A New Generalization of Palindromes
1 Introduction
2 Preliminaries
3 Properties of Block Palindromes
4 Enumeration of Maximal Block Palindromes
5 Conclusions
References
Maximal Motif Discovery in a Sliding Window
1 Introduction
2 Definitions and Algorithmic Toolbox
3 Sliding Window
3.1 Update of Set of Motifs for a Sliding Window
3.2 On-Line Update of Suffix Tree for a Sliding Window
4 Maximal Motif Discovery Algorithm
4.1 Reading a Letter on the Right
4.2 Deleting a Letter from the Left
4.3 Updating the Score Array
5 Algorithm Analysis
6 Concluding Remarks
References
Compressed Range Minimum Queries
1 Introduction
1.1 Our Results and Techniques
2 RMQ on Compressed Representations
2.1 Compressing the String
2.2 Compressing the Cartesian Tree
3 Compressing the String vs. the Cartesian Tree
4 Conclusions
References
Fast Wavelet Tree Construction in Practice
1 Introduction
2 Preliminaries
2.1 Wavelet Trees
3 Proposed Wavelet Tree Construction
3.1 Two-Phase Wavelet Tree Construction
3.2 CPU Instructions for Efficient Bit and Byte Manipulation
3.3 Practical Techniques for Bit Packing
3.4 Practical Techniques for List Splitting
4 Experiments
5 Conclusion
References
Faster Recovery of Approximate Periods over Edit Distance
1 Introduction
2 Approximate Pattern Matching in Periodic Texts
2.1 Wrap-Around Dynamic Programming
2.2 Wrap-Around DP with Kangaroo Jumps
2.3 Main Results
References
Searching for a Modified Pattern in a Changing Text
1 Introduction
2 Problem Formulation
3 Preliminaries
4 The Cover Idea and Previous Work
5 Supporting the Online Text
5.1 Idea
5.2 Substring Concatenation
6 Supporting Copy-Pasting and Deleting Substrings
7 Reporting Pattern Occurrences in O(occ) Time
8 Conclusion
References
Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays
1 Introduction
2 Preliminaries
2.1 Strings
2.2 Suffix Arrays and Permutations
3 Strings over an Alphabet of Smallest Size
3.1 Computing a String from the Forward Suffix Array
3.2 Computing a String from Forward and Backward Suffix Arrays
4 Counting Strings from Forward and Backward Suffix Arrays
5 Enumerating Strings from Suffix Arrays
5.1 Enumerating Strings from the Forward Suffix Array
References
Optimal In-Place Suffix Sorting
1 Introduction
1.1 Problem Setting
1.2 Related Work and Our Contributions
1.3 Difficulties and Our Approach
2 Preliminaries
3 Suffix Sorting for Read-Only Integer Alphabets
3.1 Framework
3.2 Sort All LMS-Characters of T
3.3 Sort All LMS-Suffixes of T by Solving the Reduced Problem T1
3.4 Induced-Sort All Suffixes of T from the Sorted LMS-Suffixes
4 Conclusion
References
Computing Burrows-Wheeler Similarity Distributions for String Collections
1 Introduction
2 Background
2.1 Notation
2.2 Burrows-Wheeler Similarity Distribution
3 Algorithm 1
3.1 Theoretical Costs
3.2 Implementation Alternatives
4 Algorithm 2
4.1 Theoretical Costs
5 Experiments
5.1 Running Time
5.2 Peak Memory
6 Conclusions
References
Better Heuristic Algorithms for the Repetition Free LCS and Other Variants
1 Introduction
2 Dynamic Programming (DP) Heuristic for RFLCS
3 Top-k Heuristic for RFLCS
4 A Polynomial Time Reduction from RFLCS to MIS
5 Experimental Results Regarding Our Heuristics
6 A 2min(n,m)-approximation for RFLCS
7 Approximation Algorithm for MRCS
8 A Polynomial Time Algorithm for MRCS with Constant Size Alphabet
9 Conclusions and Future Work
References
Linear-Time Online Algorithm Inferring the Shortest Path from a Walk
1 Introduction
2 Preliminaries
3 Irreducible and Suffix-Reducible Strings
4 Algorithm
4.1 Outline of Our Algorithm
4.2 Correctness and Complexity of the Algorithm
5 Experiments
References
Trickier XBWT Tricks
1 Introduction
2 The New Algorithm
3 Saving Space
4 Experimental Results
5 Concluding Remark
References
Fast and Effective Neural Networks for Translating Natural Language into Denotations
1 Introduction
2 Related Work
3 Conditionally-Independent Models
3.1 Fast Semantic Parsing
3.2 Reduced Fast Semantic Parsing
3.3 Reduced MultiLinear Network
4 Experiments
4.1 Dataset
4.2 Models
4.3 Baselines
4.4 Setup
4.5 Results and Discussion
5 Conclusions
References
Faster and Smaller Two-Level Index for Network-Based Trajectories
1 Introduction
2 Background and Related Work
3 Data Structures for Network-Based Trajectories
3.1 Temporal Level: Data Structures for the Interval Intersection Problem
4 Experimental Results
4.1 Evaluation of Interval Intersection Data Structures
4.2 Overall Evaluation
5 Conclusions
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken