Parallel Tucker Decomposition And Application Based On PowerGraph

Tensor decomposition is a classic and basic data analysis method,which has been applied in various popular research fields.The industry has accumulated rich research theories and experiences.Due to the rapid increase of data scale,the traditional tensor decomposition algorithm in the stand-alone environment has been unable to adapt the requirements of the big data era.Therefore,the study on the parallelization of tensor decomposition is of great practical significance.Two main decomposition methods of tensor decomposition are CP decomposition and Tucker decomposition.Both are widely used with different emphasis.The CP decomposition can be regarded as a special case of Tucker decomposition under certain conditions.There are lots of studies on the parallelization of the Tucker decomposition algorithm,which have their own advantages.At present,many real data sets exhibit the network characteristics represented by the graph data.More and more research is focused on graph data processing.The graph data and tensor data can be converted to each other,so there is a close relationship between them.Many researchers consider introducing tensor and tensor decomposition into the research field of graph data processing,aiming at mining the potential knowledge from the graph data.By analyzing several parallel computing frameworks,this thesis adopts PowerGraph as the physical environment for the experiments.At the same time,some applications of the paralleling Tucker decomposition based on the PowerGraph have been tried.The main work is divided into the following three parts:1.Design and implementation of the parallel algorithm of truncating SVD(TRSVD).The SVD has important research value and practical significance in the fields of machine learning and data mining,which is often used as an update method for alternating least squares(ALS).TRSVD is an improved strategy for SVD.In this thesis,the author firstly analyzes the basic principle of TRSVD.Then core steps of the TRSVD algorithm are decomposition by splitting the row vectors.In order to execute the algorithm on the PowerGraph framework the author declare a graph data structure.The experimental results show that the paralleling TRSVD algorithm can deal with larger scale matrices with less computation time.At the same time,it is base of the paralleling Tucker decomposition algorithm,which improves the computational efficiency of the algorithm.2.Design and implementation of the Tucker decomposition parallel algorithm.By deeply analyzing the basic principle and feasibility of the Tucker decomposition algorithm,the paralleling TRSVD algorithm is adopted to reconstruct the corresponding graph data structure.The Tucker decomposition algorithm is implemented highly parallel on the PowerGraph framework.The algorithm was tested and analyzed several times from different directions.The experimental results show that the parallel Tucker decomposition algorithm can handle larger tensors with higher computational efficiency.3.Design and implementation two kinds of applications based on parallel Tucker decompositionFirst,the concepts of RESCAL decomposition model and hidden factor matrix are cited.A Tucker decomposition parallel algorithm is applied to a multi-relational network data set.The community discovery algorithm of the multi-relational network is implemented on the PowerGraph framework.Secondly,a color image is represented as a tensor.A Tucker decomposition parallel algorithm is applied on a color image.The data compression algorithm of the color image is implemented on the PowerGraph framework.The correctness and practical significance of the Tucker decomposition parallel algorithm are proved by the above two applications.