Subsequence | EPFL Graph Search

In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence \langle A,B,D \rangle is a subsequence of \langle A,B,C,D,E,F \rangle obtained after removal of elements C, E, and F. The relation of one sequence being the subsequence of another is a preorder. Subsequences can contain consecutive elements which were not consecutive in the original sequence. A subsequence which consists of a consecutive run of elements from the original sequence, such as \langle B,C,D \rangle, from \langle A,B,C,D,E,F \rangle, is a substring. The substring is a refinement of the subsequence. The list of all subsequences for the word "apple" would be "a", "ap", "al", "ae", "app", "apl", "ape", "ale", "appl", "appe", "aple", "apple", "p", "pp", "pl", "pe", "ppl

Matching Seqlets: An Unsupervised Approach for Locality Preserving Sequence Matching

Pascal Fua, Xinchao Wang

In this paper, we propose a novel unsupervised approach for sequence matching by explicitly accounting for the locality properties in the sequences. In contrast to conventional approaches that rely on frame-to-frame matching, we conduct matching using sequencelet or seqlet, a sub-sequence wherein the frames share strong similarities and are thus grouped together. The optimal seqlets and matching between them are learned jointly, without any supervision from users. The learned seqlets preserve the locality information at the scale of interest and resolve the ambiguities during matching, which are omitted by frame-based matching methods. We show that our proposed approach outperforms the state-of-the-art ones on datasets of different domains including human actions, facial expressions, speech, and character strokes.

IEEE COMPUTER SOC2021

A Mobile World of Security

Christine Neuberg

Security in mobile communications is a topic of increasing relevance in everyday life. We all use mobile devices for everyday communications, maybe even for exchanging confidential information with the work place. This requires security systems that are reliable and stable even though mobility and number of users are increasing. An established solution in today's systems is to use symmetric cryptographic systems by relying on pre-established secrets. There are a few drawbacks. The first problem is that all security information is stored in one central storage place. This implies that users are required to trust this storage place. They need to trust that data is properly handled and well protected. The mechanism of storing pre-established long-term secrets at a central storage also makes it vulnerable to adversaries. As soon as someone gains access to it, he automatically has access to all secret information necessary to capture communications. A second problem is that security mechanisms implemented in today's mobile communication systems were designed for a moderate number of users. Since then, the number of users has grown significantly and continues to do so. It would thus be desirable to have a system that is flexible in terms of the number of users it can handle. The third and maybe the most crucial problem is the fact that today's security systems rely on computational cryptography. This means that the security mechanisms in cellular communication systems were designed with limited computational power of the adversary in mind. However, the computational power of computers is growing and systems might be breakable in the near future. A complementary notion of security is information-theoretic security. Systems built in this spirit are unbreakable even with unlimited computational power. These systems exploit the knowledge of statistical properties of the environment. This means mainly that security systems can be proved to be secure with respect to assumptions on the correlated sources and with respect to the nature of the knowledge the adversary can gain. The main idea of information-theoretic security is that two communication partners have access to correlated random sources. An adversary being potentially present in the system, has only degraded access to the source. The common knowledge can be used in order to generate sequences that are very similar among each other. Because the adversary has access to the random source, he is able to generate his own version of the sequence. It is fundamental that the sequences of the communicationpartners are stronger correlated among each other than with respect to the adversary. This advantage in knowledge can be interpreted as a secret among the communication partners to the adversary. In communicating over an authenticated but public channel, this secret can be extracted from the original sequence by both parties. In order for both keys to be equal, the original sequences need to coincide. This is not necessarily the case, but can be achieved by discussion over the public channel. In the first part of this thesis, we propose a security system that relies on information-theoretic security. We will demonstrate how this system can be implemented in cellular communication systems. The movement of the users is random and we want to use it as a random source. We assume that users are moving along a random itinerary while visiting a random sequence of cells. Users not only visit cells in a random order, they also stay for a random time in each cells. It turns out that it is the sequence of durations that contributes most to the randomness of the sequence. We call the sequence of durations timing. This sequence is known to users and to the infrastructure, but only parts of it are known to potential adversaries. By recording the sequence of cells along with the time of residence, both the user and the infrastructure will be able to acquire very similar sequences. After the collection process, a procedure for key agreement is applied. Due to the underlying process, the key will not be uniformly distributed. As this is a requirement for perfect secret keys, a final part of the protocol is privacy amplification, where the perfectly secret bits will be extracted. This system is lightweight as it is based on readily available information and only a small amount of post-processing is required. In the second part of this thesis, we analyze the performance of the system. For this, we demonstrate how the process of bit collection can be analytically modeled. Our analysis leads to two conclusions. It gives us intuition about how to choose parameters such that the scheme performs optimally. Our scheme can be applied to settings that fulfill certain conditions. Conclusions from analysis allow to specify such conditions. We will show the implication of this conclusion in sketching some alternative applications of our scheme.

EPFL2011

Taxonomy Induction using Hypernym Subsequences

Karl Aberer, Amit Gupta, Hamza Harkous, Rémi Philippe Lebret

We propose a novel, semi-supervised approach towards domain taxonomy induction from an input vocabulary of seed terms. Unlike all previous approaches, which typically extract direct hypernym edges for terms, our approach utilizes a novel probabilistic framework to extract hypernym subsequences. Taxonomy induction from extracted subsequences is cast as an instance of the minimumcost flow problem on a carefully designed directed graph. Through experiments, we demonstrate that our approach outperforms stateof- the-art taxonomy induction approaches across four languages. Importantly, we also show that our approach is robust to the presence of noise in the input vocabulary. To the best of our knowledge, no previous approaches have been empirically proven to manifest noise-robustness in the input vocabulary.

CIKM2017

A Mobile World of Security

Christine Neuberg

EPFL2011