In this paper we address a classical sequence mining problem, namely, that of finding the Closest Pair of Subsequences. Given a sequence A of length n, the problem is to identify two non-overlapping subsequences of length l each in A, such that their distance is minimum from among all such pairs. This is a fundamental problem that has a wide range of applications such as time series data mining, sequence data pattern matching, data signature identification, biological motif mining, metagenomic clustering, etc. To solve this problem, the state-of-the-art algorithm takes advantage of the overlapping parts of consecutive subsequences. By exploiting these overlaps, researchers have developed an algorithm with a run time of O(n²), which is independent of the dimension l. In this paper, we propose a deterministic algorithm called JUMP, which further pushes the limit by skipping unnecessary comparisons and multiplication operations, and improves the running time by a large factor. We have performed extensive experiments using standard benchmark datasets, and found that JUMP outperforms existing O(n²) methods by a factor of up to 100. Our experiments cover different settings of n and l and provide the readers a comprehensive and unbiased comparison under different conditions.

Discovering patterns in biological sequences is a crucial step to extract useful information from them. Motif search has numerous applications including the identification of transcription factors and their binding sites, composite regulatory patterns etc. The general problem of motif search is intractable. One of the most studied models of motif search proposed in literature is Edit-distance based Motif Search (EMS). In EMS, people are interested in finding a pattern of length $l$ which occurs with an edit-distance of at most $d$ in each of the input sequences. There exists some algorithms proposed in the literature to solve EMS problem. However, in terms of challenging instances and large datasets, they are still not efficient. In this paper, current state-of-the-art EMS solver is advanced by exploiting the idea of projecting the alphabet. Compared to some of the previous algorithms which are either approximate or fall under the heuristic category, EMS3 is an exact algorithm. EMS3 can be also viewed as a divide and conquer algorithm. In this paper, solid theoretical analyses prove the efficiency of EMS3. Extensive experiments on commonly used benchmark synthetic datasets as well as real datasets show that the proposed algorithm outperforms the existing state-of-the-art algorithm (EMS2).

In this paper, we propose a new MAC protocol for multi-beam directional antenna. In the protocol, each beam-sector has its own control channel, thus the communications among different beam-sectors are independent. It uses the Directional Network Allocation Vector (DNAV) to record the establishment processes. After sensing all the sectors of multi-beam antenna, it uses the global assignment strategy to assign the directional communication channels. Extensive simulation results show that our protocol can significantly improve the throughput of entire wireless network at the expense of the slightly increased RTS/DRTS requests during establishment process.

Polyspectral estimation is a problem of great importance in the analysis of nonlinear time series that has applications in biomedical signal processing, communications, geophysics, image, radar, sonar and speech processing, etc. Higher order spectra (HOS) have been used in unsupervised and supervised clustering in big data scenarios, in testing for Gaussianity, to suppress Gaussian noise, to characterize nonlinearities in time series data, and so on . Any algorithm for computing the $k$th order spectra of a time series of length $n$ needs $\Omega(n^{k-1})$ time since the output size will be $\Omega(n^{k-1})$ as well. Given that we live in an era of big data, $n$ could be very large. In this case, sequential algorithms might take unacceptable amounts of time. Thus it is essential to develop parallel algorithms. There is also room for improving existing sequential algorithms. In addition, parallel algorithms in the literature are nongeneric. In this paper we offer generic sequential algorithms for computing higher order spectra that are asymptotically faster than any published algorithm for HOS. Further, we offer memory efficient algorithms. We also present optimal parallel implementations of these algorithms on parallel computing models such as the PRAM and the mesh. We provide experimental results on our sequential and parallel algorithms. Our parallel implementation achieves very good speedups.

In simultaneous translation (SimulMT), the most widely used strategy is the wait-k policy thanks to its simplicity and effectiveness in balancing translation quality and latency. However, wait-k suffers from two major limitations: (a) it is a fixed policy that can not adaptively adjust latency given context, and (b) its training is much slower than full-sentence translation. To alleviate these issues, we propose a novel and efficient training scheme for adaptive SimulMT by augmenting the training corpus with adaptive prefix-to-prefix pairs, while the training complexity remains the same as that of training full-sentence translation models. Experiments on two language pairs show that our method outperforms all strong baselines in terms of translation quality and latency.