基于图数据的极大频繁子树挖掘算法研究

唐德权; 黄金贵

Chinese

您当前的位置：

首页 >

文章列表页 >

基于图数据的极大频繁子树挖掘算法研究

更新时间：2026-09-04

- 基于图数据的极大频繁子树挖掘算法研究
- Algorithm of maximum frequent sub-tree mining based on graph data
- 微电子学与计算机 2020年37卷第10期页码：54-58
- 作者机构：
  
  1. 湖南师范大学数学与统计学院,湖南,长沙,410081
  2. 湖南警察学院信息技术系,湖南,长沙,410138
  3. 湖南师范大学信息科学与工程学院,湖南,长沙,410081
- 作者简介：
- 基金信息：
  
  国家自然科学基金资助项目 61471169湖南省科技重大专项项目 2017SK1040
- DOI：
  中图分类号：
- 纸质出版：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

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

V型沟槽SiC中子探测器的蒙特卡洛分析

面向处理器分支预测单元的Spectre攻击轻量化防御方法

注意力机制与改进密集卷积引导的信息隐藏模型

超低功耗实时时钟电路的设计

基于改进RT-DETR的航拍小目标检测算法