Search

Graphs are the most complex data structure that involves heavy mathematical computations. Various real-time applications use the graph at storage, processing, object characterization, and behavior specification stages. The connectivity analysis, coverage building, and routing are the critical applications of graph evaluation. Various associated applications need the exploration of a graph with a practical and real-time outcome. The processing of larger graphs is a big challenge for the researcher. In this paper, a hybrid graph-based computation optimization method is designed to optimize the performance of graph processing in multi-core processors. The BFS algorithm is applied over the multiple processors to optimize the functional response. The multithreaded-BFS is implemented to reduce the time of graph processing and computation. The proposed algorithm is implemented in the OpenMP environment. The experimentation is done on two-core and four-core processors. The experiment is conducted on a 100 to 1000-node network. The traversing and graph coloring algorithms are implemented for the analysis. The comparative analysis is conducted on single-core and multi-core processors with DFS and BFS-based algorithms. The analysis results identified that the proposed algorithm reduced the processing time effectively. [ABSTRACT FROM AUTHOR]

Graph is a widely used data structure which can be regarded as a generalized measure metirc space. Since a graph not only includes points but also relation between points, the distance between two graphs is difficult to measure. In recent years, Gromov-Wasserstein discrepancy has been proposed as a pseudometirc on graphs which has a complete theoretical basis, but has few applications. Therefore, this paper reviews the basic ideas, applications and improvements of Gromov-Wasserstein. Since Gromov-Wasserstein discrepancy is a quadratic programming and difficult to calculate, this paper focuses on the iterative algorithm for solving this discrepancy. At the end, we look forward to the development of Gromov-Wasserstein discrepancy. [ABSTRACT FROM AUTHOR]

K-Nearest Neighbors (KNN) are very popular supervised machine learning algorithm which can be effectively used for both multi-class classification and regression utilizing multiple features of the dataset. It trains extremely fast, that is with time complexity of O(n). However, the time complexity for generating results with KNN is O(n3dk) (where k=number of neighbours, d=dimension of data, n=number of training points) and hence it becomes very difficult to work with larger dataset. Although there are parallelizing and distributed computing techniques available for speeding up KNN, it still have limitations on horizontal scalability, fault tolerance and incremental learning capabilities. To solve these issues, the paper presents a KNN inspired novel Supervised Machine Learning algorithm called Distributed Nearest Hash utilizing unique usage of hashmap and primary key clustering order with help of wide column store databases facilitating easy incremental near-realtime scalability to train unlimited datapoints with O(n) time complexity and also predict them in near realtime with O(1) time complexity considering n >> d. This can be readily integrated in any system that uses KNN as a base classifier or regressor. The experimental results shows that the proposed DNH model is 25% faster than state of the art distributed KNN algorithm. Integrating with fuzzy logic the algorithm can be used for several class classification. Using this could aid in building very powerful smart decision making systems with very little computational power. [ABSTRACT FROM AUTHOR]

The continuous improvement of sequencing technologies has been paralleled by the development of efficient algorithms and data structures for sequencing data analysis and processing. Suffix array is one of data structures that are used to construct the Burrows-Wheeler transform (BWT) for long length genomes. Building a suffix array itself is an expensive-resource process since the computations are dominant by sorting suffixes in a lexical order. Most of the suffix array construction algorithms consider the general and integer alphabets without utilizing special cases for fixed-size ones such as DNA alphabets. In this paper, we exploit the nature of four-sized DNA alphabets and utilize their predefined lexicographical ordering in order to construct suffix arrays for genomic data correctly and efficiently. The suffix array construction algorithm for DNA alphabets is evaluated using three real data sets with different lengths ranging from small E-coli genome to long length Homo sapiens GRCh38.p13 chromosomes. For long length genomes, their corresponding sequence is divided into parts (i.e. reads) with a minimum overlap length, the suffix array is computed for each part separately, and finally all partially computed arrays are merged together into a single one. We studied the effects of varying the reads/overlap lengths on the running time of the proposed suffix array construction algorithm and conclude that the minimum overlap length should be equal to the average length of the longest common prefix between the adjacent parts. [ABSTRACT FROM AUTHOR]

An initializable array is an array that supports the read and write operations for any element and the initialization of the entire array. This paper proposes a simple in-place algorithm to implement an initializable array of length N containing ℓ ∈ O (w) bits entries in N ℓ + 1 bits on the word RAM model with w bits word size, i.e., the proposed array requires only 1 extra bit on top of a normal array of length N containing ℓ bits entries. Our algorithm supports the all three operations in constant worst-case time, that is, it runs in-place using at most constant number of words O (w) bits during each operation. The time and space complexities are optimal since it was already proven that there is no implementation of an initializable array with no extra bit supporting all the operations in constant worst-case time (Hagerup and Kammer, 2017 [12]). Our algorithm significantly improves upon the best algorithm presented in the earlier studies (Navarro, 2014 [5]) which uses N + o (N) extra bits to support all the operations in constant worst-case time. [ABSTRACT FROM AUTHOR]

Given two sequences A and B of lengths m and n , respectively, the consecutive suffix alignment (CSA) problem is to compute the longest common subsequence (LCS) between A and each suffix of B. The data structure of two-dimensional matrix for solving the CSA problem is named S-table. The S-table would be infeasible due to its quadratic-space requirement for long sequences. The linear-space S-table, proposed by Alves et al. (2005), consists of the first row of the S-table and the changes between every two consecutive rows. However, there is no further discussions and practical applications for the linear-space S-table. This paper proposes algorithms for improving three problems, related to LCS and S-table, by using the linear-space S-table. Suppose that A = A (1) A (2) (concatenation of two substrings), and we are given the S-table of A (2) and B , as well as the alignment result (LCS length) of A (1) to each prefix of B. The concatenated LCS (CoLCS) problem is to find the alignment result of A and B. For the CoLCS problem, this paper proposes an O(n)-time algorithm with the technique of set union-find to achieve the linear space. Next, for merging two linear S-tables, we propose an O (n log ⁡ n) -time algorithm with the technique of range query and update to improve the quadratic-time algorithm using quadratic-space S-tables. Then, we propose an O(n)-time algorithm to update the linear-space S-table of A and B to obtain the linear-space S-table of Aσ and B , where σ denotes a new character appended to the tail of A. For further applications to long sequences by using the linear-space S-table, the algorithms proposed in this paper are essential and necessary. [ABSTRACT FROM AUTHOR]

Multi-view clustering, which aims at dividing data with similar structures into their respective groups, is a popular research subject in computer vision and machine learning. In recent years, Non-negative matrix factorization (NMF) has received constant concern in multi-view clustering due to its ability to deal with high-dimensional data. However, most existing NMF methods may fail to integrate valuable information from multi-view data adequately, and the local geometry structure in data is also not fully considered. Thus, it's still a crucial but challenging problem, which effectively extracts multi-view information while maintaining the low-dimensional geometry structure. In this paper, we propose an innovative multi-view clustering method, referred to as re-weighted multi-view clustering via triplex regularized non-negative matrix factorization (SMCTN), which is a unified framework and provides the following contributions: 1) pairwise regularization can extract complementary information between views and is suitable for both homogeneous and heterogeneous perspectives; 2) consensus regularization can process the consistent information between views; 3) graph regularization can preserve the geometric structure of data. Specifically, SMCTN applies a re-weighted strategy to assign suitable weights for multiple views according to their contributions. Besides, an effective iterative updating algorithm is developed to solve the non-convex optimization problem in SMCTN. Extensive experimental results on textual and image datasets indicate that the superior performance of the proposed method. [ABSTRACT FROM AUTHOR]

A graph is called a 1-planar graph, if it admits a 1-plane embedding (i.e., an embedding with at most one crossing per edge). Thomassen characterized forbidden configuration for straight-line drawings of 1-plane graphs [Thomassen (1988) [38] ]. In this paper, we investigate the problem of re-embedding a 1-plane graph (i.e., 1-planar graph with a given 1-planar embedding) to admit a straight-line drawing, preserving the original set of edge crossings of 1-plane graphs. More specifically, we characterize forbidden configurations such that a given 1-plane graph can be re-embedded into a straight-line drawable 1-plane embedding if and only if it does not contain the configurations. We present a linear-time algorithm for computing a straight-line drawable 1-plane re-embedding, if one exists, or finding the forbidden configuration, otherwise. To design a linear-time algorithm, we exploit a data structure called an inclusion-forest that summarizes the inclusion relationships between non-intersecting cycles of a plane graph. [ABSTRACT FROM AUTHOR]

Learning causal structures from observational data is of great challenge and interest in many disciplines. Various methods have demonstrated their effectiveness for causal structure learning on different types of data, but most of them are suffered from the indeterminacy of Markov equivalence classes, especially on discrete data. A recent breakthrough formulates the problem as finding a hidden compact representation (HCR) with lower cardinality to distinguish the correct causal direction. However, method based on the HCR model is only applicable in bivariate cases. In this paper, we generalize the HCR model to multivariate cases and provide an effective likelihood-based algorithm for causal structure learning in presence of hidden compact representation. Our theoretical results show that under some weak technique conditions about the underlying causal mechanism, causal directions are still identifiable even in multivariate cases. Our empirical studies demonstrate the effectiveness of proposed methods on various types of data and structures. [ABSTRACT FROM AUTHOR]

We consider the single-machine scheduling problem to tradeoff between the number and the length of accepted jobs. The algorithm introduced by Lin and Wang (2007) (called Lin-Wang's algorithm), for solving the single-machine scheduling problem to minimize the number of tardy jobs, is closely related to our research. The original version of Lin-Wang's algorithm runs in O (n 2) time. By using the technique of the preemptive scheduling combined with a data structure, we show in this paper that a variant of Lin-Wang's algorithm actually runs in O (n log ⁡ n) time. This enables us to further show that the tradeoff problem can be solved in O (n log ⁡ n) time. [ABSTRACT FROM AUTHOR]

• Optimizes the clustering result and the common representation subspace simultaneously across multiple views. • Untangle heavily mixed clusters by optimizing a single continuous objective. • Without the requirement of the number of clusters given in advance. • Not prone to stick into bad local minima even with outliers in data. This paper proposed a novel Robust Multi-View Continuous Subspace Clustering (RMVCSC) algorithm, which can untangle heavily mixed clusters by optimizing a single continuous objective. The proposed objective uses robust estimators to automatically clip specious inter-cluster connections while maintaining convincing intra-cluster correspondences in the common representation subspace learned from multiple views. The common representation subspace can reveal the underlying cluster structure in data. RMVCSC is optimized in an alternating minimization scheme, in which the clustering result and the common representation subspace are simultaneously optimized. Since different views can describe distinct perspectives of input data, the proposed algorithm has more accurate clustering performance than conventional algorithms by exploring information among multi-view data. In other words, the proposed algorithm optimizes a novel continuous objective in the simultaneously learned common representation subspace across multiple views. By using robust redescending estimators, the proposed algorithm is not prone to stick into bad local minima even with outliers in data. This kind of robust continuous clustering methods has never been used for multi-view clustering before. Moreover, the convergence of the proposed algorithm is theoretically proved, and the experimental results show that the proposed RMVCSC can outperform several very recent proposed algorithms in terms of clustering accuracy. [ABSTRACT FROM AUTHOR]

High utility pattern mining (HUPM) plays a significant role in data mining technologies. Traditional HUPM algorithms may produce a large number of high utility patterns (HUPs) when the database is dense or the data is massive. To address this issue, closed high utility pattern (CHUP) mining was proposed, providing a high-level overview of the HUPs and helpful information for decision-makers. However, CHUPs do not consider the factors of period and recency. Therefore, this paper is the first to introduce period and recency into closed high utility pattern mining and proposes the CPR-Miner algorithm to mine closed periodic recent high utility patterns. These patterns have more practical value since they are closed sets of HUPs. Due to the increasing number of factors to be considered, new upper bounds and pruning strategies are also proposed, significantly improving the algorithm's efficiency. To test the performance of our algorithm and our new pruning strategies, we improved the PHM algorithm to generate the PR-Miner algorithm. Experimental results show a significant efficiency of the new pruning strategies and demonstrate that CPR-Miner outperforms the PR-Miner algorithm in all aspects. • Periodicity and recency are introduced within closed high utility pattern mining. • New data structures are designed to store the utility, period, and recency information. • Novel pruning strategies are proposed to avoid unnecessary list joint operation. • The proposed algorithm gets significant results on several datasets. [ABSTRACT FROM AUTHOR]

(Aim) Gene expression data is typically high dimensional with a limited number of samples and contain many features that are unrelated to the disease of interest. Existing unsupervised feature selection algorithms primarily focus on the significance of features in maintaining the data structure while not taking into account the redundancy among features. Determining the appropriate number of significant features is another challenge. (Method) In this paper, we propose a clustering-guided unsupervised feature selection (CGUFS) algorithm for gene expression data that addresses these problems. Our proposed algorithm introduces three improvements over existing algorithms. For the problem that existing clustering algorithms require artificially specifying the number of clusters, we propose an adaptive k -value strategy to assign appropriate pseudo-labels to each sample by iteratively updating a change function. For the problem that existing algorithms fail to consider the redundancy among features, we propose a feature grouping strategy to group highly redundant features. For the problem that the existing algorithms cannot filter the redundant features, we propose an adaptive filtering strategy to determine the feature combinations to be retained by calculating the potentially effective features and potentially redundant features of each feature group. (Result) Experimental results show that the average accuracy (ACC) and matthews correlation coefficient (MCC) indexes of the C4.5 classifier on the optimal features selected by the CGUFS algorithm reach 74.37% and 63.84%, respectively, significantly superior to the existing algorithms. (Conclusion) Similarly, the average ACC and MCC indexes of the Adaboost classifier on the optimal features selected by the CGUFS algorithm are significantly superior to the existing algorithms. In addition, statistical experiment results show significant differences between the CGUFS algorithm and the existing algorithms. [ABSTRACT FROM AUTHOR]

With the development of technology and the arrival of the era of big data, a large number of complex data structures have been generated, which makes matrix minimization become important and necessary. However, in the process of analyzing those data, there exist some latent structures such as low-rank and sparse decomposition. To address this issue, in this paper, we propose and study a novel low-rank and sparse regularized matrix minimization. Then an efficient semi-proximal alternating direction method of multipliers (sPADMM) is developed from the dual perspective. In theoretical analysis, it has proved that the sequence generated by the sPADMM converges to a global minimizer. Furthermore, the non-asymptotic statistical property is derived which suggests that the gap between the corresponding estimators and the true values is bounded with high probability and their consistency is guaranteed under rather weak regularity conditions. We also prove that the sequence generated by the proposed algorithm converges to the true value with high probability. Finally, extensive numerical experiments are conducted to verify the superiority of the proposed method in wide applications such as signal processing, image reconstruction, and video denoising. [ABSTRACT FROM AUTHOR]

The Voronoi tessellation is a fundamental geometric data structure which has numerous applications in various scientific and technological fields. For large particle datasets, computing Voronoi tessellations must be conducted in parallel on a distributed-memory supercomputer in order to satisfy time and memory-size constraints. However, due to load balance and communication, the parallelization of the Voronoi tessellation renders a challenge. In this paper, we present a scalable parallel algorithm for constructing 3D Voronoi tessellations, which evenly distributes the input particles between blocks through kd-tree decomposition. In order to construct the correct global Voronoi topology, we investigate both parametric and non-parametric methods for particle communication among the blocks of a spatial decomposition. The algorithm is implemented exploiting process-level and thread-level parallelization and can be used in a diverse architectural landscape. Using datasets containing up to 330 million particles, we show that our algorithm achieves parallel efficiency up to 57% using 4096 cores on a distributed-memory computer. Moreover, we compare our algorithm with previous attempts to parallelize Voronoi tessellations showing encouraging improvements in terms of computation time. • A new parallel algorithm for computing 3D Voronoi based on kdtree decomposition. • Parametric and non-parametric methods for establish communication. • An evaluation of the algorithm, including parallel accuracy and scalability. • A publicly available library (named ParVoro++) implemented as a fork of Voro++. [ABSTRACT FROM AUTHOR]

Set similarity join (SSJ) is a well studied problem with many algorithms proposed to speed up its performance. However, its scalability and performance are rarely discussed in modern multicore environments. Existing algorithms assume a single-threaded execution that leaves the abundant parallelism provided by modern machines unused, or use distributed setups that may not yield efficient runtimes and speedups that are proportional to the amount of hardware resources (e.g., CPU cores). In this paper, we focus on a widely-used family of SSJ algorithms that are based on the filter-and-verification paradigm, and study the potential of speeding them up in the context of multicore machines. We adapt state-of-the-art SSJ algorithms including PPJoin and AllPairs. Our experiments using 12 real-world datasets highlight important findings: (1) Using the exact number of hardware-provided hyperthreads leads to optimal runtimes for most experiments, (2) hand-crafted data structures do not always lead to better performance, and (3) PPJoin's position filter is more effective in the multithreaded case compared to the single-threaded execution. • Multi-threading has not yet been considered to speed up set similarity joins. • We propose a novel data-parallel set similarity join algorithm. • Multi-threading speeds up the set similarity join 2 to 10 times. • Implementation optimizations are not benefitial for the runtime. [ABSTRACT FROM AUTHOR]

HUIM (High utility itemset mining) is a key problem in data mining. The goal is to find itemsets having a high importance or profit in a database, to identify useful knowledge that can support decision-making. In recent years, many HUIM algorithms have been put forward. Among them, utility-list-based algorithms have become very popular as they are easily extendable and efficient. Although several improvements were made, efficiency remains a critical issue. To address this problem, this paper proposes to improve the utility-list construction process, a key operation that has not been much studied in prior work. A novel set of bitwise operations is proposed called BEO (Bit mErge cOnstruction) to speed up the construction process. Besides, a novel data structure called UBP (Utility Bit Partition) is designed to support BEO. This structure is integrated into a novel UBP-Miner algorithm, which also applies several search space reduction strategies. Experimental results show that UBP-Miner is faster than several state-of-the-art algorithms such as HUI-Miner* and ULB-Miner on common benchmark datasets. [ABSTRACT FROM AUTHOR]

• A new face-based data structure for storing information of the Voronoi diagram and Delaunay triangulation is proposed. • A simple, fast and robust incremental algorithm with optimal complexity is proposed. • Data structure could be easily converted to other edge-based data structures. In this paper, a new incremental algorithm with an overall complexity of O (n logn) for constructing both the 2D Voronoi diagram (VD) and Delaunay triangulation (DT) is proposed. Moreover, a new face-based data structure is proposed which is more cost-effective in terms of memory than the previous edge-based data structures. The proposed data structure maintains the VD and DT in separate matrices, while establishing a connection between these two, allowing extracting neighborhoods and geometric information without the need for further processing in many applications. Moreover, the proposed data structure can be easily converted to the other edge-based data structures such as the Doubly Connected Edge List. The proposed algorithm for finding the nearest neighbor to the added point, in this incremental algorithm, has O(logn) complexity. Evaluations performed by points with different numbers and distributions confirm the high robustness of the proposed algorithm against different point distributions and its O(n logn) overall complexity. [ABSTRACT FROM AUTHOR]

Message passing is a class of extremely powerful distributed iterative algorithms based on probabilistic graphic model, in which little computation performed per iteration on minimal data structure. As a prototypical message-passing algorithm, belief propagation (BP) algorithm has wide applications in various fields of coding theory, machine learning and combinatorial optimization. Due to its distributed and iterative nature, BP algorithm can run effectively and fast on large data networks. In this paper, we study the behavior of Min-Sum BP algorithm for the capacitated directed Chinese postman problem (CDCP). We derive the iterative process of message passing for solving CDCP. As the main result, for any weighted digraph G of size n , if the weight on each edge is nonnegative integral, then our algorithm converges to the optimal solution of CDCP after O (w ∗ n 2) iterations, provided that CDCP has a unique optimal solution, where w ∗ = max { w e : e ∈ E (G) }. [Display omitted] • Message passing is a class of extremely powerful distributed iterative algorithms based on probabilistic graphic model. • Due to its distributed and iterative nature, belief propagation (BP) algorithm can run effectively and fast on large data networks. • BP-based algorithms can also run fast on a large data network in synchronous circumstances. • Min-Sum BP algorithm could converge to the optimal solution of the capacitated directed Chinese postman problem after O (w m a x n 2) iterations. [ABSTRACT FROM AUTHOR]

• A low-rank plus sparse tensor model to decompose the urban traffic data into normal and anomalous components. • Imposed temporal smoothness on the sparse part of the tensor through total variation regularization. • Introduced graph regularization to exploit the geometric structure of the data. • Solve a tensor completion problem simultaneously with the anomaly detection problem. • The resulting spatiotemporal features can be scored by any conventional anomaly scoring algorithm. Anomaly detection in spatiotemporal data is a problem encountered in a variety of applications including urban traffic monitoring. For urban traffic data, anomalies refer to unusual events such as traffic congestion and unexpected crowd gatherings. Detecting these anomalies is challenging due to the scarcity of anomalous events and the dependence of anomaly definition on time and space. Existing spatiotemporal anomaly detection methods cannot preserve the spatial and temporal correlations and do not take the structure of anomalies into account. In this paper, we introduce a temporally regularized, locally consistent, robust low-rank plus sparse tensor model for spatiotemporal anomaly detection. The proposed method takes the spatially sparse and temporally smooth structure of urban anomalies into account by modeling the anomalies as the sparse part of the tensor and minimizing the total variation across the temporal mode of this part. The local consistency of the low-rank part is ensured using a manifold embedding approach. The proposed approach is referred to as Graph Regularized Low-rank plus Temporally Smooth Sparse decomposition (GLOSS) and is evaluated on synthetic and real spatiotemporal urban traffic data. The results illustrate the accuracy and robustness of the proposed method with respect to missing data, noise and anomaly strength. [ABSTRACT FROM AUTHOR]

Indexes provide a method to access data in databases quickly. It can improve the response speed of subsequent queries by building a complete index in advance. However, it also leads to a huge overhead of the continuous updating during creating the index. An in-memory database usually has a higher query processing performance than disk databases and is more suitable for real-time query processing. Therefore, there is an urgent need to reduce the index creation and update cost for in-memory databases. Database cracking technology is currently recognized as an effective method to reduce the index initialization time. However, conventional cracking algorithms are focused on simple column data structure rather than those complex index structures for in-memory databases. In order to show the feasibility of in-memory database index cracking and promote to future more extensive research, this paper conducted a case study on the Adaptive Radix Tree (ART), a popular tree index structure of in-memory databases. On the basis of carefully examining the ART index construction overhead, an algorithm using auxiliary data structures to crack the ART index is proposed. This makes it possible to build up an ART index step by step with incessant queries, and hence avoids the poor instant availability of a complete index which is constructed once and for all, but is time consuming. Furthermore, updating a cracking ART index is considered as well. Extensive experiments show that the average initialization time of the ART cracker index is reduced by 75%, and the query response time gradually approaches the original ART algorithm with the coming queries. • In-memory database indexes have more extensive research and application space. • Database Cracking is used as a method applied to in-memory database indexes. • The algorithm has better performance advantages under random queries. [ABSTRACT FROM AUTHOR]

• Presenting a new multi-label feature selection method that efficiently combines manifold regularization and dependence maximization. • Introducing a HSIC-based measurement to evaluate the dependence between the manifold space and label space. • Developing an iterative optimization method to solve the objective function of our method MRDM with good convergence. • Conducting extensive experiments on various multi-label data sets to demonstrate the superiority of the proposed method. Feature selection is able to select more discriminative features for classification and plays an important role in multi-label learning to alleviate the effect of the curse of dimensionality. Recently, the multi-label feature selection methods based on the sparse regression model have received increasing attentions. However, most of these methods directly project original data space to label space in the regression model, which is inappropriate because the linear assumption between data space and label space doesn't hold in most cases. In the paper, we propose a feature selection method named multi-label feature selection via manifold regularization and dependence maximization (MRDM). In the regression model of MRDM, the original data space is projected to a low-dimensional manifold space, which not only has the same topological structure with the original data, but also has a strong dependence with the class labels. Then, an objective function involving l 2 , 1 -norm regularization is formulated, and an alternating optimization-based iterative algorithm is designed to obtain the sparse coefficients for multi-label feature selection. Extensive experiments on various multi-label data sets demonstrate the superiority of the proposed method compared with some state-of-the-art multi-label feature selection methods. [ABSTRACT FROM AUTHOR]

• Design a branch and bound strategy for identifying non-contributed points and non-longest paths. • Construct a much smaller DAG than those constructed by the existing algorithms. • Design a strategy for deleting points in the Hash table timely. • Propose a new data structure for storing Small-DAG to avoid topological sorting. • Propose a new algorithm for larger-scale MLCS problems with lower time and space cost. Finding the multiple longest common subsequences (MLCS) among many long sequences (i.e., the large scale MLCS problem) has many important applications, such as gene alignment, disease diagnosis, and documents similarity check, etc. It is an NP-hard problem (Maier et al., 1978). The key bottle neck of this problem is that the existing state-of-the-art algorithms must construct a huge graph (called direct acyclic graph, briefly DAG), and the computer usually has no enough space to store and handle this graph. Thus the existing algorithms cannot solve the large scale MLCS problem. In order to quickly solve the large-scale MLCS problem within limited computer resources, this paper therefore proposes a branch and bound irredundant graph algorithm called Big-MLCS, which constructs a much smaller DAG (called Small-DAG) than the existing algorithms do by a branch and bound method, and designs a new data structure to efficiently store and handle Small-DAG. By these schemes, Big-MLCS is more efficient than the existing algorithms. Also, we compare the proposed algorithm with two state-of-the-art algorithms through the experiments, and the results show that the proposed algorithm outperforms the compared algorithms and is more suitable to large-scale MLCS problems. [ABSTRACT FROM AUTHOR]

Supervised multi-view feature selection has recently been proven to be a valid way for reducing the dimensionality of data. This paper proposes a robust supervised multi-view feature selection method based on weighted shared loss and maximum margin criterion. Specifically, we fuse all weighted views to establish a shared loss term to maintain the complementary information of views, where the weight of each view can be automatically adjusted according to its contribution to the final task. Moreover, we adopt the capped l 2 -norm rather than the widely used l 2 -norm to measure the loss and remove the potential outliers. Further, we introduce the maximum margin criterion (MMC) into the feature selection and design a weighted view-based MMC such that it is a proper regularization associated with the proposed model. In this way, the inter-class and intra-class structure information of data is well exploited, which makes the margins of the samples belonging to the different classes increase and the margins of the samples belonging the same class decrease. Then the discriminative features of all views can be selected. The corresponding problem can be solved by the alternating direction method of multipliers (ADMM), which can realize the view-block calculation and reduce the computational complexity. Comprehensive experiments on various benchmark datasets and the application on the hydraulic system confirm the validity of our method. • A multi-view feature selection based on weighted shared loss and MMC is proposed. • Weighted shared loss is designed to maintain the complementary information of views. • Weighted view-based MMC regularizer is designed to learn view's structure knowledge. • The proposed algorithm realizes the view-block calculation via ADMM. • The extensive experiments demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Biclustering (co-clustering, two-mode clustering), as one of the classical unsupervised learning methods, has been applied in many different fields in recent years. Different types of biclustering methods have been developed such as probabilistic methods, two-way clustering methods, variance minimization methods, and so on. However, few regression-based methods have been proposed to the best of our knowledge. Such methods have been applied in traditional clustering, which can improve both the computational efficiency and the clustering accuracy. In this paper, we present a penalized regression-based method for localizing the biclusters (PRbiclust). By imposing Truncated LASSO Penalty (TLP) and group TLP terms to penalize the column vectors and the row vectors in the regression model, the structure of biclusters in the data matrix is recovered. The model is formulated as an optimization problem with nonconvex penalties, and a computationally efficient algorithm is proposed to solve it. Convergence of the algorithm is proved. To extract the biclusters from the recovered data matrix, we propose a graph-based localization method. An evaluation criterion is also proposed to measure the efficiency of bicluster localization when noise entries exist. We apply the proposed method to both simulated datasets with different setups and a real dataset. Experiments show that this method can well capture the bicluster structure, and performs better than the existing works. [ABSTRACT FROM AUTHOR]