Mining multiple longest common subsequences (MLCS) from a set of sequences of three or more over a finite alphabet$\Sigma$(a classical NP-hard problem [1]) is an important task in many fields, e.g., bio-informatics, computational genomics, pattern recognition, information extraction, etc. Applications in these fields often involve generating very long sequences (length$\geq 10_{,}000)$, referred to as big sequences. However, both existing exact and approximate MLCS algorithms face severe challenges in handling big sequences due to the over-whelming size of their problem-solving graph model MLCS­-$DAG$(Directed Acyclic Graph), leading to the issue of memory explosion or extremely high time complexity.

Mining multiple longest common subsequences (MLCS) from a set of sequences of length three or more over a finite alphabet (a classical NP-hard problem) is an important task in many fields, e.g., bioinformatics, computational genomics, pattern recognition, information extraction, etc. Applications in these fields often involve generating very long sequences (length$\geqslant$10,000), referred to as big sequences. Despite efforts in improving the time and space complexities ofMLCSmining algorithms, both existing exact and approximate algorithms face challenges in handling big sequences due to the overwhelming size of their problem-solving graph modelMLCS-DAG(DirectedAcyclicGraph), leading to the issue of memory explosion or extremely high time complexity. To bridge the gap, this paper first proposes a new identification and deletion strategy for different classes of non-critical points in the mining ofMLCS, which are the points that do not contribute to theirMLCSs mining in theMLCS-DAG. It then proposes a newMLCSproblem-solving graph model, namely$DAG_{KP}$(a newMLCS-DAGcontaining onlyKeyPoints). A novel parallelMLCSalgorithm, calledKP-MLCS(KeyPoint basedMLCS), is also presented, which can mine and compress allMLCSs of big sequences effectively and efficiently. Extensive experiments on both synthetic and real-world biological sequences show that the proposed algorithmKP-MLCSdrastically outperforms the existing state-of-the-artMLCSalgorithms in terms of both efficiency and effectiveness.

Many big data applications produce a massive amount of high-dimensional, real-time, and evolving streaming data. Clustering such data streams with both effectiveness and efficiency are critical for these applications. Although there are well-known data stream clustering algorithms that are based on the popular online-offline framework, these algorithms still face some major challenges. Several critical questions are still not answer satisfactorily: How to perform dimensionality reduction effectively and efficiently in the online dynamic environment? How to enable the clustering algorithm to achieve complete real-time online processing? How to make algorithm parameters learn in a self-supervised or self-adaptive manner to cope with high-speed evolving streams? In this paper, we focus on tackling these challenges by proposing a fully online data stream clustering algorithm (called ESA-Stream) that can learn parameters online dynamically in a self-adaptive manner, speedup dimensionality reduction, and cluster data streams effectively and efficiently in an online and dynamic environment. Experiments on a wide range of synthetic and real-world data streams show that ESA-Stream outperforms state-of-the-art baselines considerably in both effectiveness and efficiency.

With ever-increasing data streams from various applications such as smart phones, network monitoring, Internet of Things (IoT), etc., unsupervised clustering of data streams has become an important problem for machine learning and big data analysis. As data streams are data-intensive, temporally ordered, and rapidly evolving, efficiently and effectively online clustering of data streams presents a challenging problem [1] .

Linear discriminant analysis (LDA) is one of the important techniques for dimensionality reduction, machine learning, and pattern recognition. However, in many applications, applying the classical LDA often faces the following problems: (1) sensitivity to outliers, (2) absence of local geometric information, and (3) small sample size or matrix singularity that can result in weak robustness and efficiency. Although several researchers have attempted to address one or more of the problems, little work has been done to address all of them together to produce a more effective and efficient LDA algorithm. This article proposes 3E-LDA, an enhanced LDA algorithm, that deals with all three problems as an attempt to further improve LDA. It proposes to learn a weighted median rather than the mean of the samples to deal with (1), to embed both between-class and within-class local geometric information to deal with (2), and to calculate the projection vectors in the null space of the matrix to deal with (3). Experiments on six benchmark datasets show that these three enhancements enable 3E-LDA to markedly outperform state-of-the-art LDA baselines in both accuracy and efficiency.

Information usually can be abstracted as a character sequence over a finite alphabet. With the advent of the era of big data, the increasing length and size of the sequences from various application fields (e.g., biological sequences) result in the classical NP-hard problem, searching for the Multiple Longest Common Subsequences of multiple sequences (i.e., MLCS problem with many applications in the areas of bioinformatics, computational genomics, pattern recognition, etc.), becoming a research hotspot and facing severe challenges. In this paper, we firstly reveal that the leading dominant-point-based MLCS algorithms are very hard to apply to long and large-scale sequences alignments. To overcome their defects, based on the proposed problem-solving model and parallel topological sorting strategies, we present a novel efficient parallel MLCS algorithm. The comprehensive experiments on the benchmark datasets of both random and biological sequences demonstrate that both the time and space complexities of the proposed algorithm are only linearly related to the dominants from aligned sequences, and that the proposed algorithm greatly outperforms the existing state-of-the-art dominant-point-based MLCS algorithms, and hence it is very suitable for long and large-scale sequences alignments.

Information in various applications is often expressed as character sequences over a finite alphabet (e.g., DNA or protein sequences). In Big Data era, the lengths and sizes of these sequences are growing explosively, leading to grand challenges for the classical NP-hard problem, namely searching for the Multiple Longest Common Subsequences (MLCS) from multiple sequences. In this paper, we first unveil the fact that the state-of-the-art MLCS algorithms are unable to be applied to long and large-scale sequences alignments. To overcome their defects and tackle the longer and large-scale or even big sequences alignments, based on the proposed novel problem-solving model and various strategies, e.g., parallel topological sorting, optimal calculating, reuse of intermediate results, subsection calculation and serialization, etc., we present a novel parallel MLCS algorithm. Exhaustive experiments on the datasets of both synthetic and real-world biological sequences demonstrate that both the time and space of the proposed algorithm are only linear in the number of dominants from aligned sequences, and the proposed algorithm significantly outperforms the state-of-the-art MLCS algorithms, being applicable to longer and large-scale sequences alignments.

A key problem of retrieving, integrating and mining rich and high quality information from massive Deep Web Databases (WDBs) online is how to automatically and effectively discover and recognize domain-specific WDBs' entry points, i.e., searchable forms, in the Web. It has been a challenging task because domain-specific WDBs' forms with dynamic and heterogeneous properties are very sparsely distributed over several trillion Web pages. Although significant efforts have been made to address the problem and its special cases, more intelligent and effective solutions remain to be further explored. In this paper, a new architecture of an intelligent agent-based crawler (iCrawler) for domain-specific Deep Web databases has been proposed to address the limitations of the existing methods. The iCrawler, based on intelligent learning agents and domain ontology, and a series of novel and effective strategies, including a two-step page classifier, a link scoring strategy, etc, can improve the performance of the existing methods. Experiments of the iCrawler over a number of real Web pages in a set of representative domains have been conducted and the results show that the iCrawler outperforms the existing domain-specific Deep Web Form-Focused Crawlers (FFCs) in terms of the harvest rate, coverage rate and time performance.