Michelle Sweering

String Sanitization

Sequential Data

A large number of applications, in domains ranging from transportation to web analytics and bioinformatics feature data modelled as strings, i.e. sequences of letters over some finite alphabet. For instance, a string may represent the history of visited locations of one or more individuals, with each letter corresponding to a location. Similarly, it may represent the history of search query terms of one or more web users, with letters corresponding to query terms, or a medically important part of the DNA sequence of a patient, with letters corresponding to DNA bases. Analyzing such strings is key in applications including location-based service provision, product recommendation, and DNA sequence analysis. Therefore, such strings are often disseminated beyond the party that has collected them.

String Sanitization

However, disseminating a string intact may result in the exposure of confidential knowledge. Thus, it may be necessary to sanitize a string prior to its dissemination, so that confidential knowledge is not exposed. At the same time, it is important to preserve the utility of the sanitized string, so that data protection does not outweigh the benefits of disseminating the string to the party that disseminates or analyzes the string, or to society at large. For example, a retailer should still be able to obtain actionable knowledge in the form of frequent patterns from the marketing agency that analyzed their outsourced data; and researchers should still be able to perform analyses such as identifying significant patterns in DNA sequences.

Combinatorial String Dissemination Model

Motivated by the discussion above, we introduce the following model which we call Combinatorial String Dissemination (CSD). In CSD, a party has a string W that it seeks to disseminate while satisfying a set of constraints and a set of desirable properties. For instance, the constraints aim to capture privacy requirements and the properties aim to capture data utility considerations (e.g., posed by some other party based on applications). To satisfy both, W must be transformed into another string by applying a sequence of edit operations. The computational task is to determine this sequence of edit operations so that the transformed string satisfies the desirable properties subject to the constraints. Clearly, the constraints and the properties must be specified based on the application. In our research, we have designed sanitization algorithms for various natural classes of privacy constraints and utility properties.

Publications

Combinatorial Algorithms for String Sanitization
By Giulia Bernardini, Huiping Chen, Alessio Conte, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone and Michelle Sweering
ACM Transactions on Knowledge Discovery from Data (TKDD) • Volume 15 • Issue 1 • February 2021.

String Sanitization Under Edit Distance
By Giulia Bernardini, Huiping Chen, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Leen Stougie, Michelle Sweering
31st Annual Symposium on Combinatorial Pattern Matching (CPM) • June 2020

String Sanitization Under Edit Distance: Improved and Generalized
By Takuya Mieno, Solon P. Pissis, Leen Stougie and Michelle Sweering
32nd Annual Symposium on Combinatorial Pattern Matching (CPM) • June 2021

Hide and Mine in Strings: Hardness and Algorithms
By Giulia Bernardini, Alessio Conte, Garance Gourdel, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Giulia Punzi, Leen Stougie and Michelle Sweering
2020 IEEE International Conference on Data Mining (ICDM) • November 2020

Hide and Mine in Strings: Hardness, Algorithms, and Experiments
By Giulia Bernardini, Alessio Conte, Garance Gourdel, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Giulia Punzi, Leen Stougie and Michelle Sweering
IEEE Transactions on Knowledge and Data Engineering (TKDE) • March 2022

Poster

---

Graph Sanitization

Network Communities

Graphs naturally model relationships between entities in a multitude of domains such as social networks, communication networks, or the web. A fundamental data analysis task in these domains is community detection (i.e., the identification of cohesive or dense subgraphs of a given graph), which employs different notions of graph community; these include the notions of k-plex, n-clan, n-club, k-core, k-ECC, and k-truss. These notions relax the classic notion of clique (i.e., the ideal situation, where all nodes are pairwise connected), either to capture practical application considerations or to enable more efficient enumeration. Regardless of the community notion, the community structure is a key property of a graph. It is therefore essential to study how such a structure can be maintained or broken.

Community Breaking

Here we investigate the following general problem.

Community Breaking (CB) problem: Given an undirected graph G, a subset of its nodes U, and a notion of community, identify the smallest subset of edges such that after removing these edges no community contains a node in U.

The CB problem is motivated by the following real-world applications:

1. Maintaining communities in social networks. The edges identified in the output of CB correspond to critical edges for maintaining user engagement in communities.
2. Assessing resilience to attacks or errors in communication networks. The edges identified in the output of CB correspond to vital connections in the network.
3. Enabling social network users to hide friendships, so that they are not seen as belonging to communities that could lead to their discrimination or unwanted targeted advertisement (e.g., through friend-based profile attribute inference attacks). The edges identified in the output of the CB problem correspond to friendships users could opt to hide.
4. Preventing the detection of confidential communities by sanitizing a graph prior to its dissemination, in the spirit of sanitization works on transaction or sequential data. The edges identified in the output of the CB problem must be removed to hide these communities in the sanitized graph.

Identifying a small edge subset is natural yet crucial. For example, in A and B, it allows less costly maintenance of user engagement and network infrastructure improvements, respectively. In C and D, it allows less effort from users and a more accurate analysis of the sanitized graph, respectively.

Publication

On Breaking Truss-Based Communities
By Huiping Chen, Alessio Conte, Roberto Grossi, Grigorios Loukides, Solon P. Pissis and Michelle Sweering
Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (KDD) • August 2021.

Elastic-Degenerate Strings

Uncertainty in sequences

String matching (or pattern matching) is a fundamental task in computer science. It consists in finding all occurrences of a short string, known as the pattern, in a longer string, known as the text. Many representations have been introduced over the years to account for unknown or uncertain letters in the pattern or in the text, a phenomenon that often occurs in real data. In the context of computational biology, for example, the IUPAC notation is used to represent locations of a DNA sequence for which several alternative nucleotides are possible. Such a notation can encode the consensus of a population of DNA sequences in a gapless multiple sequence alignment.

Elastic-degenerate strings

Iliopoulos et al. generalized these representations to also encode insertions and deletions (gaps) occurring in multiple sequence alignments by introducing the notion of elastic-degenerate strings. Elastic degenerate strings consist of a sequence of sets of strings, where each set describes all variations at that location. We say a string S matches an elestic-degenerate string T if it can be obtained by picking one string from each set in T. Below you can find an example of a multiple sequence alignment and an elastic-degenerate string matching all three of its strings (with the first match illustrated in blue).

We have studied the elastic-degenerate string matching problem, which consists in reporting all occurrences of a pattern of length m in an elastic-degenerate text.

Publication

Elastic-Degenerate String Matching with 1 Error
By Giulia Bernardini, Estéban Gabory, Solon P. Pissis, Leen Stougie, Michelle Sweering and Wiktor Zuba
Latin American Symposium on Theoretical Informatics (LATIN) • October 2022

---

String Sampling

Minimizers

The minimizers sampling mechanism is a popular mechanism for string sampling introduced independently by Schleimer et al. [SIGMOD 2003] and by Roberts et al. [Bioinf. 2004]. Given two positive integers w and k, it selects the lexicographically smallest length-k substring in every fragment of w consecutive length-k substrings (in every sliding window of length w + k − 1).

Example 1. The set M_w,k of minimizers for w = k = 3 for string T = aabaaabcbda (using a 1-based index) is M_3,3(T) = {1, 4, 5, 6, 7} and for string Q = abaaa is M_3,3(Q) = {3}. Indeed Q occurs at position 2 in T; and Q and T[2 . . 6] have the minimizers 3 and 4, respectively, which both correspond to string aaa of length k = 3.

Minimizers samples are approximately uniform, locally consistent, and computable in linear time. Although they do not have good worst-case guarantees on their size, they are often small in practice. They thus have been successfully employed in several string processing applications. Two main disadvantages of minimizers sampling mechanisms are: first, they also do not have good guarantees on the expected size of their samples for every combination of w and k; and, second, indexes that are constructed over their samples do not have good worst-case guarantees for on-line pattern searches.

bd-Anchors

To alleviate these disadvantages, we introduce bidirectional string anchors (bd-anchors), a new string sampling mechanism. Given a positive integer l, our mechanism selects the lexicographically smallest rotation in every length-l fragment (in every sliding window of length l).

Example 2. The set A_l of bd-anchors for l = 5 for string T = aabaaabcbda (using a 1-based index) is A₅(T) = {4, 5, 6, 11} and for string Q = abaaa, A₅(Q) = {3}. Indeed Q occurs at position 2 in T; and Q and T[2 . . 6] have the bd-anchors 3 and 4, respectively, which both correspond to the rotation aaaab.

We show that bd-anchors samples are also approximately uniform, locally consistent, and computable in linear time. In addition, our experiments using several datasets demonstrate that the bd-anchors sample sizes decrease proportionally to l; and that these sizes are competitive to or smaller than the minimizers sample sizes using the analogous sampling parameters. We provide theoretical justification for these results by analyzing the expected size of bd-anchors samples. As a negative result, we show that computing a total order ≤ on the input alphabet, which minimizes the bd-anchors sample size, is NP-hard.

We also show that by using any bd-anchors sample, we can construct, in near-linear time, an index which requires linear (extra) space in the size of the sample and answers on-line pattern searches in near-optimal time. We further show, using several datasets, that a simple implementation of our index is consistently faster for on-line pattern searches than an analogous implementation of a minimizers-based index [Grabowski and Raniszewski, Softw. Pract. Exp. 2017].

Finally, we highlight the applicability of bd-anchors by developing an efficient and effective heuristic for top-K similarity search under edit distance. We show, using synthetic datasets, that our heuristic is more accurate and more than one order of magnitude faster in top-K similarity searches than the state-of-the-art tool for the same purpose [Zhang and Zhang, KDD 2020].

Preprint

String Sampling with Bidirectional String Anchors
By Grigorios Loukides, Solon P. Pissis and Michelle Sweering.

Code available in C++.

---

Connecting Strings

De Bruijn Graphs

The order-k de Bruijn graph (dBG) of a collection S of strings is a directed multigraph G_S,k(V, E) such that

• V is the set of length-(k − 1) substrings of the strings in S and
• G_S,k contains an edge (u, v) with multiplicity m_u,v if and only if the string u[0] · v is equal to the string u · v[k − 2] and this string occurs exactly m_u,v times in total in strings in S.

When S is generated by a sequencing experiment from a genome, any Eulerian walk of G_S,k(V, E) — i.e. a walk on the graph that visits each edge (u, v) exactly m_u,v times — corresponds to a single genome reconstruction. It goes without saying that genome assembly is one of the most important bioinformatics tasks. However, G_S,k is almost surely not Eulerian in practice due to sequencing errors. One could thus try to make it Eulerian by duplicating some of its existing edges. In this case, one would naturally like to minimize the total cost of this extension. Even worse, G_S,k would likely not be weakly connected, and thus edge duplication is not sufficient to make G_S,k Eulerian.

Computing a string which contains a set of given substrings arises naturally as an encoding problem in many other contexts as well, such as data privacy and data compression. Depending on the application, we may or may not require the order and/or frequency of the substrings to be preserved. Moreover, we may want to avoid occurrences of specific forbidden patterns modelling confidential knowledge.

Publications

Making de Bruijn Graphs Eulerian
By Giulia Bernardini, Huiping Chen, Grigorios Loukides, Solon P. Pissis, Leen Stougie and Michelle Sweering
33rd Annual Symposium on Combinatorial Pattern Matching (CPM) • June 2022

Code available in C++.

On Strings Having the Same Length-k Substrings
By Giulia Bernardini, Alessio Conte, Estéban Gabory, Roberto Grossi, Grigorios Loukides, Solon P. Pissis, Giulia Punzi and Michelle Sweering
33rd Annual Symposium on Combinatorial Pattern Matching (CPM) • June 2022

Constructing Strings Avoiding Forbidden Substrings
By Giulia Bernardini, Alberto Marchetti-Spaccamela, Solon P. Pissis, Leen Stougie and Michelle Sweering
32nd Annual Symposium on Combinatorial Pattern Matching (CPM) • June 2021

---

Periodicity

Borders and periods

A word can overlap itself if one of its prefixes is equal to one of its suffixes. The corresponding prefix (or suffix) is called a border and the shift needed to match the prefix to the suffix is called a period. For example, consider the word abracadabra: then, abra is its longest border of abracadabra and corresponds to a period of 7, but a is also a border of abracadabra corresponding to a period of 10, and finally, the word abracadabra is a border itself corresponding to a trivial period of 0. Importantly, a period is an offset at which two occurrences of a word w can overlap themselves.

..........1..........
01234567890..........
abracadabra----------
-------abracadabra---
----------abracadabra

The notions of borders and periods are key in word combinatorics, in stringology, and especially in pattern matching algorithms. The set of periods of a word impacts how occurrences of this word can appear in random texts.

Autocorrelations

Consider words of length n. The set of all periods a word of length n is a subset of {0, 1, 2, . . . , n−1}. However, any subset of {0, 1, 2, . . . , n−1} is not necessarily a valid set of periods. In a seminal paper in 1981, Guibas and Odlyzko proposed to encode the set of periods of a word into an n-long binary string, called autocorrelation, where a 1 at position i denotes a period of i (revisiting the example above, the string abracadabra has period set {0, 7, 10} and autocorrelation 10000001001). They considered the question of recognizing a valid period set, and also studied the number of valid period sets for length n, denoted κ_n. They conjectured that ln(κ_n) asymptotically converges to a constant times ln²(n). If improved lower bounds for ln(κ_n) / ln²(n) were proposed in 2001 by Rivals and Rahmann, the question of a tight upper bound has remained open since Guibas and Odlyzko’s paper.

In our paper, we exhibit an asymptotically matching upper bound for this fraction, which implies its convergence, and closes this long-standing conjecture. Moreover, we extend our result to find similar bounds for the number of correlations: a generalization of autocorrelations which encodes the overlaps between two strings.

Preprint

Convergence of the number of period sets in strings
By Eric Rivals, Michelle Sweering and Pengfei Wang.
50th EATCS International Colloquium on Automata, Languages and Programming (ICALP) • July 2023

Poster