Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2018 Nov 18;18(11):4020.
doi: 10.3390/s18114020.

Detecting Incremental Frequent Subgraph Patterns in IoT Environments

Kyoungsoo Bok  1 , Jaeyun Jeong  2 , Dojin Choi  3 , Jaesoo Yoo  4
Affiliations

Detecting Incremental Frequent Subgraph Patterns in IoT Environments

Kyoungsoo Bok et al. Sensors (Basel). .

Abstract

As graph stream data are continuously generated in Internet of Things (IoT) environments, many studies on the detection and analysis of changes in graphs have been conducted. In this paper, we propose a method that incrementally detects frequent subgraph patterns by using frequent subgraph pattern information generated in previous sliding window. To reduce the computation cost for subgraph patterns that occur consecutively in a graph stream, the proposed method determines whether subgraph patterns occur within a sliding window. In addition, subgraph patterns that are more meaningful can be detected by recognizing only the patterns that are connected to each other via edges as one pattern. In order to prove the superiority of the proposed method, various performance evaluations were conducted.

Keywords: IoT; frequent pattern detection; graph stream; incremental; subgraph pattern.

PubMed Disclaimer

Conflict of interest statement

The authors declare no conflict of interest.

Figures

Figure 1
Figure 1
Overall processing procedure.
Figure 2
Figure 2
Example of a graph stream, where Gt is a graph at time t.
Figure 3
Figure 3
New input graph stream, where G10 is a graph at time 10, G11 is a graph at time 11, and G12 is a graph at time 12.
Figure 4
Figure 4
Processing time of the proposed method according to sliding window size.
Figure 5
Figure 5
Processing time according to the number of edges.
Figure 6
Figure 6
Processing time according to the sliding window size.
Figure 7
Figure 7
Processing time according to threshold.
Figure 8
Figure 8
Memory usage.
See this image and copyright information in PMC

References

    1. Ma S., Li J., Hu C., Lin X., Huai J. Big graph search: challenges and techniques. Frontiers Comput. Sci. 2016;10:387–398. doi: 10.1007/s11704-015-4515-1. - DOI
    1. Zhang L., Gao J. Incremental graph pattern matching algorithm for big graph data. Sci. Program. 2018;2018:1–8. doi: 10.1155/2018/6749561. - DOI
    1. Labouseur A.G., Birnbaum J., Olsen P.W., Spillane S.R., Vijayan J., Hwang J., Han W. The G graph database: efficiently managing large distributed dynamic graphs. Distrib. Parallel Databases. 2015;33:479–514. doi: 10.1007/s10619-014-7140-3. - DOI
    1. Yan D., Bu Y., Tian Y., Deshpande A. Big graph analytics platforms. Found. Trends Databases. 2017;7:1–195. doi: 10.1561/1900000056. - DOI
    1. Jiang F., Leung C.K. Mining interesting “following” patterns from social networks; Proceedings of the International Conference on Data Warehousing and Knowledge Discovery; Munich, Germany. 2–4 September 2014; pp. 308–319.