• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Dong Rongsheng, Zhang Xinkai, Liu Huadong, Gu Tianlong. Representation and Operations Research of k\+2-MDD in Large-Scale Graph Data[J]. Journal of Computer Research and Development, 2016, 53(12): 2783-2792. DOI: 10.7544/issn1000-1239.2016.20160589
Citation: Dong Rongsheng, Zhang Xinkai, Liu Huadong, Gu Tianlong. Representation and Operations Research of k\+2-MDD in Large-Scale Graph Data[J]. Journal of Computer Research and Development, 2016, 53(12): 2783-2792. DOI: 10.7544/issn1000-1239.2016.20160589

Representation and Operations Research of k\+2-MDD in Large-Scale Graph Data

More Information
  • Published Date: November 30, 2016
  • Efficient and compact representation and operation of graph data which contains hundreds of millions of vertices and edges are the basis of analyzing and processing the large scale of graph data. Aiming at the problem, this paper proposes a representation of large-scale graph data based on the decision diagram, that is k\+2-MDD, providing the initialization of k\+2-MDD and the basic operation such as the edge query, inner(outer) neighbor query, finding out(in)-degree, adding(deleting) edge, etc. The representation method is optimized and improved on the basis of k\+2 tree, and after dividing the adjacency matrix of graph into k\+2, it is stored with the multi valued decision diagram, so as to achieve a more compact storage structure. According to the experimental results of a series of real Web graph and the social network graph data (cnr-2000, dewiki-2013, etc.) derived from the LAW laboratory at the University of Milan, it can be seen that the number of k\+2-MDD’ nodes is only 259%-451% of the k\+2 tree, which achieving the desired effect. According to the experimental results of random graphs, it can be seen that the k\+2-MDD structure is not only suitable for sparse graphs, but also for dense graphs. The graph data of k\+2-MDD shows that both containing the compact and query efficiency representation of k\+2 tree and realizing the efficient operation of the graph model can thus achieve the unity of description and computing power.
  • Related Articles

    [1]Li Fengying, Shen Huiqiang, Dong Rongsheng. Compact Representation of Temporal Graphs Based on kd-MDD[J]. Journal of Computer Research and Development, 2022, 59(6): 1286-1296. DOI: 10.7544/issn1000-1239.20200856
    [2]Li Song, Dou Yanan, Hao Xiaohong, Zhang Liping, Hao Zhongxiao. The Method of the K-Dominant Space Skyline Query in Road Network[J]. Journal of Computer Research and Development, 2020, 57(1): 227-239. DOI: 10.7544/issn1000-1239.2020.20190026
    [3]Zhang Chao, Li Deyu. Interval-Valued Hesitant Fuzzy Graphs Decision Making with Correlations and Prioritization Relationships[J]. Journal of Computer Research and Development, 2019, 56(11): 2438-2447. DOI: 10.7544/issn1000-1239.2019.20180314
    [4]Lu Youjun, Xu Daoyun. Phase Transition Properties of k-Independent Sets in Random Graphs[J]. Journal of Computer Research and Development, 2017, 54(12): 2843-2850. DOI: 10.7544/issn1000-1239.2017.20160694
    [5]Zhang Liping, Liu Lei, Hao Xiaohong, Li Song, Hao Zhongxiao. Voronoi-Based Group Reverse k Nearest Neighbor Query in Obstructed Space[J]. Journal of Computer Research and Development, 2017, 54(4): 861-871. DOI: 10.7544/issn1000-1239.2017.20151111
    [6]Li Pengyuan, Pan Haiwei, Li Qing, Han Qilong, Xie Xiaoqin, Zhang Zhiqiang. Top-k Medical Images Query Based on Association Graph[J]. Journal of Computer Research and Development, 2015, 52(9): 2033-2045. DOI: 10.7544/issn1000-1239.2015.20140692
    [7]Zheng Lili, Wu Jigang, Chen Yong, Zhu Meixia. Balanced k-Way Partitioning for Weighted Graphs[J]. Journal of Computer Research and Development, 2015, 52(3): 769-776. DOI: 10.7544/issn1000-1239.2015.20131508
    [8]Zhang Hui, Zheng Jiping, Han Qiuting. BTreeU-Topk: Binary-Tree Based Top-k Query Algorithms on Uncertain Data[J]. Journal of Computer Research and Development, 2012, 49(10): 2095-2105.
    [9]Zhang Xu, He Xiangnan, Jin Cheqing, and Zhou Aoying. Processing k-Nearest Neighbors Query over Uncertain Graphs[J]. Journal of Computer Research and Development, 2011, 48(10): 1871-1878.
    [10]Li Aijun, Luo Siwei, Huang Hua, Liu Yunhui. Decision Tree Based Neural Network Design[J]. Journal of Computer Research and Development, 2005, 42(8): 1312-1317.

Catalog

    Article views (1238) PDF downloads (436) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return