Approximation and Randomised String Processing – PARSe
PARSe
In this project we aimed to study the foundations of processing large-scale, noisy string data to understand the limit of computations, and to provide new ultra-efficient algorithms and data structures for processing such data, inspired by approaches in hashing and high-dimensional geometry.
Algorithms for Approximation and Randomised String Processing
The urgent need for large-scale methods for string processing is dictated by an ever-increasing pace of growth of the volume of available string data. The total amount of produced string data doubles approximately every seven months, which is faster than what was predicted by Moore's law. As if that was not enough, the data is often noisy, calling for robust processing methods. Many classical algorithms and data structures capable of solving this task have unfavourable time and space lower bounds and must be re-considered in order to adapt them to the scale of modern data sets. Two possible approaches to storing and processing large-scale data are distributed and cloud programming, but they may not be sufficient on their own and must be complemented by novel software tools. In this project we focused on a novel, sketch-based approach for processing massive string data. Our goal was to study the foundations of this approach to understand the limit of computations and provide ultra-efficient methods that could have impact in Bioinformatics, Information Retrieval, and Digital Security. Informally, a sketch is a compact description of the data that captures only those of its characteristics that are essential for answering the question of interest, in other words, a sketch can be considered as a lossy compression of the data. The central questions of our project were: For which string processing tasks sketches help to obtain efficient algorithms and data structures? What is the best sketch for a particular task? In particular, can we use the nature of the data to further improve the sketch? Which approximation schemes can be used?
Our research hypothesis was that sketches, randomisation, and approximation are the key to tasks such as processing large-scale, noisy data, and for which the classical approaches give unfeasible lower bounds. In order to inspect this hypothesis in full generality and respond to our central questions, we considered three work packages: String Comparison, Probabilistic Indexing, and Streaming Pattern Matching.
The project resulted in several publications in leading international conferences in theoretical computer science, including STOC, FOCS, SODA, ICALP, and ESA. In addition, two papers produced during the project received the Best Paper Award at CPM.
The major results of the project, which are closely aligned with the initial scientific objectives, include the following:
1) The development of a streaming algorithm for approximate pattern matching under edit distance.
2) The design of streaming algorithms for recognizing regular languages, visibly pushdown languages (VPL), as well as languages of palindromes and squares in the streaming model.
3) The development of sliding-window algorithms for regular languages, allowing efficient processing of dynamically changing streams.
4) The design of probabilistic data structures for dictionary matching with mismatches and for fundamental pattern matching queries.
Beyond its scientific contributions, the project also supported the training of young researchers. During the project, two PhD students successfully defended their theses, while another doctoral thesis is currently nearing completion. The project funding also enabled the recruitment of two postdoctoral researchers.
The project also contributed to the organization of scientific events aimed at disseminating knowledge and fostering collaboration within the community:
1) A summer school on Bioinformatics and String Algorithms, organized in 2023, which gathered approximately 50 student participants.
2) The international workshop “New Horizons of Stringology”, held at CIRM in Marseille in 2024, with approximately 50 participants.
The results of this project open up two promising research directions. The first concerns approximate and randomized algorithms for formal language recognition, which are essential for efficiently processing large, noisy data streams and identifying patterns of interest. The second focuses on privacy-preserving techniques for streaming string and pattern processing, notably ensuring confidentiality through differential privacy while maintaining theoretical guarantees on algorithmic accuracy. Both directions offer many opportunities for future research.
In this project we aim to study the foundations of processing large-scale, noisy string data. Our goal is to understand the limit of computations, and to provide new ultra-efficient algorithms and data structures for processing such data, inspired by approaches in hashing and high-dimensional geometry. We will focus on three research directions: streaming pattern matching, probabilistic text indexing, and sketching-based sting comparison. Algorithms and data structures on strings have traditionally been exploited in such fields as Bioinformatics, Information Retrieval, and Digital Security, and we expect our project to have a significant impact on these fields.
Project coordination
Tatiana Starikovskaya (Département d'Informatique de l'Ecole Normale Supérieure)
The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.
Partnership
University of Wroclaw / Institute of Informatics
DI ENS Département d'Informatique de l'Ecole Normale Supérieure
IRISA Institut de Recherche en Informatique et Systèmes Aléatoires
LIRMM Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier
Help of the ANR 202,340 euros
Beginning and duration of the scientific project:
December 2020
- 48 Months
