Algorithm of maximum frequent sub-tree mining based on graph data

TANG De-quan; HUANG Jin-gui

Chinese

您当前的位置：

首页 >

文章列表页 >

Algorithm of maximum frequent sub-tree mining based on graph data

更新时间：2026-09-04

- Algorithm of maximum frequent sub-tree mining based on graph data
- Vol. 37, Issue 10, Pages: 54-58(2020)
- 作者机构：
  
  1. 湖南师范大学数学与统计学院,湖南,长沙,410081
  2. 湖南警察学院信息技术系,湖南,长沙,410138
  3. 湖南师范大学信息科学与工程学院,湖南,长沙,410081
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2020
- 稿件说明：
移动端阅览
唐德权, 黄金贵. 基于图数据的极大频繁子树挖掘算法研究[J]. 微电子学与计算机, 2020, 37(10): 54-58.

TANG De-quan, HUANG Jin-gui. Algorithm of maximum frequent sub-tree mining based on graph data[J]. 2020, 37(10): 54-58.
唐德权, 黄金贵. 基于图数据的极大频繁子树挖掘算法研究[J]. 微电子学与计算机, 2020, 37(10): 54-58. DOI：

TANG De-quan, HUANG Jin-gui. Algorithm of maximum frequent sub-tree mining based on graph data[J]. 2020, 37(10): 54-58. DOI：

摘要

由于极大频繁子树中已经隐含了所有频繁子树信息，尤其处理大型图数据集时候，挖掘极大频繁子树对提高频繁子树挖掘算法效率具有重要意义.首先在有效编码的基础上提出连接和扩展操作算法，通过两个算法产生所有极大候选子树；其次引入嵌入集计算解决子树同构问题，对子树同构问题进行了优化，进一步提出了一种新的极大频繁子树挖掘算法(MFST)；最后证明了算法的正确性和分析了算法在最坏情况下的时间性能，并与其它基于半结构化数据集的频繁子树挖掘算法进行了比较.实验结果表明，MFST算法具有更好的时间性能和空间性能，可以在图数据集中有效挖掘频繁子树.

Abstract

In view of the the current frequent subtree mining problems

the maximal frequent subtree mining algorithm can improve the efficiency of the frequent subtree mining algorithm. Firstly

propose two operations of the join and extension on the basis of effective coding

which are generate all candidate subtrees. Secondly

the embedded set is used to solve the problem of subtree isomorphism

and a new maximum frequent subtree mining algorithm(MFST) is proposed. Finally

the correctness of the algorithm is proved and the time performance of the algorithm in the worst case is analyzed. And compared with other frequent subtree mining algorithms based on semi-structured data sets

prove this algorithm is superior to the current frequent subtree mining algorithms. The experimental results show that the MFST algorithm has better time and spatial performance

and can effectively mining frequent subtree on the graph data sets.

关键词

Keywords

references

HAN K, LV W, YIN B, et al.Constrained frequent subtree mining method [C]// Luo X N, Luo Z X. Digital Home, Better Life: Proceedings of the 2014 5th International Conference on Digital Home.Washington, DC: IEEE Computer Society, 2014: 287-292.

ZHANG S, DU Z, WANG J T. New techniques for mining frequent patterns in unordered trees [J]. IEEE Transactions on Cybernetics, 2015, 45(6):1113-1125. DOI: 1113

RON S, DEKEL T. Faster subtree isomorphism [J]. Journal of Algorithms, 1999, 33(2):267-280. DOI: 267

PETER W S. A New Proof of Cayley's Formula for Counting Labeled Trees [J].Journal of Combinatorial Theory, Series A. 1995, 71(1):154-158. DOI: 154

WANG J, LIU Z, LI W, et al. Research on a frequen maximal induced subtrees mining method based on the compression tree sequence [J]. Expert Systems with Applications, 2015, 42(1):94-100. DOI: 94

YANG P, TAN Q. Maximum frequent tree mining and its applications [J]. Computer Science, 2008, 35(2):150-153. DOI: 150

AKSHAY D, DAVID F B, SRIKANTA T, et al. EvoMiner: frequent subtree mining in phylogenetic databases [J].Knowledge and Information Systems, 2014, 41(3):559-590. DOI: 559

TANG D Q, XIE W J. A new frequent subtree mining algorithm research and implementation [J]. Computer Applications and Software, 2012, 29(4): 174-177 DOI: 174

TANG D Q, TAN Y. Algorithm for frequent subgraph mining [J]. Computer Engineering, 2012, 38(7): 31-33. DOI: 31

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

High gain stability high temperature operational amplifier based on reverse body bias

Microservices anomaly detection based on the correlation of monitoring metrics

Aerial small object detection algorithm based on improved RT-DETR

Design of ultra-low power real-time clock circuits

Research on the design of blockchain-based AI-generated content traceability framework

Related Author

No data

Related Institution

No data

AI问答

Postal code：100079
Tel：（010）53879206 Email：tmw@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09082226号-64 京公网安备11010602201714号
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰