Currently,the top-rank-k has been widely applied to mine frequent patterns with a rank not exceeding k.In the existing algorithms,although a level-wise-search could fully mine the target patterns,it usually leads to t...Currently,the top-rank-k has been widely applied to mine frequent patterns with a rank not exceeding k.In the existing algorithms,although a level-wise-search could fully mine the target patterns,it usually leads to the delay of high rank patterns generation,resulting in the slow growth of the support threshold and the mining efficiency.Aiming at this problem,a greedy-strategy-based top-rank-k frequent patterns hybrid mining algorithm(GTK)is proposed in this paper.In this algorithm,top-rank-k patterns are stored in a static doubly linked list called RSL,and the patterns are divided into short patterns and long patterns.The short patterns generated by a rank-first-search always joins the two patterns of the highest rank in RSL that have not yet been joined.On the basis of the short patterns satisfying specific conditions,the long patterns are extracted through level-wise-search.To reduce redundancy,GTK improves the generation method of subsume index and designs the new pruning strategies of candidates.This algorithm also takes the use of reasonable pruning strategies to reduce the amount of computation to improve the computational speed.Real datasets and synthetic datasets are adopted in experiments to evaluate the proposed algorithm.The experimental results show the obvious advantages in both time efficiency and space efficiency of GTK.展开更多
Array partitioning is an important research problem in array management area,since the partitioning strategies have important influence on storage,query evaluation,and other components in array management systems.Mean...Array partitioning is an important research problem in array management area,since the partitioning strategies have important influence on storage,query evaluation,and other components in array management systems.Meanwhile,compression is highly needed for the array data due to its growing volume.Observing that the array partitioning can affect the compression performance significantly,this paper aims to design the efficient partitioning method for array data to optimize the compression performance.As far as we know,there still lacks research efforts on this problem.In this paper,the problem of array partitioning for optimizing the compression performance(PPCP for short)is firstly proposed.We adopt a popular compression technique which allows to process queries on the compressed data without decompression.Secondly,because the above problem is NP-hard,two essential principles for exploring the partitioning solution are introduced,which can explain the core idea of the partitioning algorithms proposed by us.The first principle shows that the compression performance can be improved if an array can be partitioned into two parts with different sparsities.The second principle introduces a greedy strategy which can well support the selection of the partitioning positions heuristically.Supported by the two principles,two greedy strategy based array partitioning algorithms are designed for the independent case and the dependent case respectively.Observing the expensive cost of the algorithm for the dependent case,a further optimization based on random sampling and dimension grouping is proposed to achieve linear time cost.Finally,the experiments are conducted on both synthetic and real-life data,and the results show that the two proposed partitioning algorithms achieve better performance on both compression and query evaluation.展开更多
基金This research was supported in part by the Hunan Province’s Strategic and Emerging Industrial Projects under Grant 2018GK4035in part by the Hunan Province’s Changsha Zhuzhou Xiangtan National Independent Innovation Demonstration Zone projects under Grant 2017XK2058+1 种基金in part by the National Natural Science Foundation of China under Grant 61602171in part by the Scientific Research Fund of Hunan Provincial Education Department under Grant 17C0960 and 18B037.
文摘Currently,the top-rank-k has been widely applied to mine frequent patterns with a rank not exceeding k.In the existing algorithms,although a level-wise-search could fully mine the target patterns,it usually leads to the delay of high rank patterns generation,resulting in the slow growth of the support threshold and the mining efficiency.Aiming at this problem,a greedy-strategy-based top-rank-k frequent patterns hybrid mining algorithm(GTK)is proposed in this paper.In this algorithm,top-rank-k patterns are stored in a static doubly linked list called RSL,and the patterns are divided into short patterns and long patterns.The short patterns generated by a rank-first-search always joins the two patterns of the highest rank in RSL that have not yet been joined.On the basis of the short patterns satisfying specific conditions,the long patterns are extracted through level-wise-search.To reduce redundancy,GTK improves the generation method of subsume index and designs the new pruning strategies of candidates.This algorithm also takes the use of reasonable pruning strategies to reduce the amount of computation to improve the computational speed.Real datasets and synthetic datasets are adopted in experiments to evaluate the proposed algorithm.The experimental results show the obvious advantages in both time efficiency and space efficiency of GTK.
基金This work was supported by the National Natural Science Foundation of China under Grant Nos.61832003 and U1811461.
文摘Array partitioning is an important research problem in array management area,since the partitioning strategies have important influence on storage,query evaluation,and other components in array management systems.Meanwhile,compression is highly needed for the array data due to its growing volume.Observing that the array partitioning can affect the compression performance significantly,this paper aims to design the efficient partitioning method for array data to optimize the compression performance.As far as we know,there still lacks research efforts on this problem.In this paper,the problem of array partitioning for optimizing the compression performance(PPCP for short)is firstly proposed.We adopt a popular compression technique which allows to process queries on the compressed data without decompression.Secondly,because the above problem is NP-hard,two essential principles for exploring the partitioning solution are introduced,which can explain the core idea of the partitioning algorithms proposed by us.The first principle shows that the compression performance can be improved if an array can be partitioned into two parts with different sparsities.The second principle introduces a greedy strategy which can well support the selection of the partitioning positions heuristically.Supported by the two principles,two greedy strategy based array partitioning algorithms are designed for the independent case and the dependent case respectively.Observing the expensive cost of the algorithm for the dependent case,a further optimization based on random sampling and dimension grouping is proposed to achieve linear time cost.Finally,the experiments are conducted on both synthetic and real-life data,and the results show that the two proposed partitioning algorithms achieve better performance on both compression and query evaluation.
