Traffic Status Prediction and Analysis Based on Mining Frequent Subgraph Patterns

Abstract:

With the development of the city, the traffic congestion and traffic accidents on the urban road increase frequently. Using traffic modeling and analysis to improve the traffic conditions become more important. Now, using the traffic flow model to study the traffic problems has made many achievements. However, traffic flow model cannot be a good choice for describing the relations of the traffic element at a specific moment, but these relations are indeed significant for forecasting traffic status from that moment on. In this paper, a graph model for the static traffic was studied, and then analyzed the feature of a graph substructure for traffic congestion at one moment. We propose an effective frequent subgraph mining algorithm to find the frequent substructure that represent traffic congestion status in a graph. Our mining algorithm can enhance the efficiency of finding the congestion subgraph. Analyzing the proportion of the congestion subgraph in a graph for traffic to forecast the traffic status at that moment later, thus to find ways to improve traffic conditions.

• Periodical: Advanced Materials Research (Volumes 605-607)
• Pages: 2543-2548
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.605-607.2543
• Online since: December 2012
• Authors: Gang Xu, Hai He Jin, Jing Liu
• Keywords: Frequent Subgraph Pattern Mining, Graph Modeling, Traffic Status

References

[1] M Cremer and J Ludwig 1986 A fast simulation model for traffic flow on the basis of Boolean operations (Mathematics and Computers in Simulation vol28) Issue 4 pp.297-303.

DOI: 10.1016/0378-4754(86)90051-0

[2] D Cakrabarti and Christos Faloutsos : Graph mining: Laws, generators, and algorithms (ACM Computing Surveys Vol 38 Article 2).

DOI: 10.1145/1132952.1132954

[3] A Inokuchi, T Washio and H Motoda : An apriori-based algorithm for mining frequent substructures from graph data (Data Mining and Knowledge Discovery Sept 2000).

DOI: 10.1007/3-540-45372-5_2

[4] M. Kuramochi and G. Karypis : Frequent subgraph discovery(Data Mining 2001).

DOI: 10.1109/icdm.2001.989534

[5] J Huan, W Wang, and J. Prins : Efficient mining of frequent subgraphs in the presence of isomorphism(Data Mining 2003).

DOI: 10.1109/icdm.2003.1250974

[6] S Nijssen and J N Kok : A quickstart in frequent structure mining can make a difference (ACM SIGKDD 2004).

DOI: 10.1145/1014052.1014134

[7] X Yan and J Han : Closegraph: Mining closed frequent graph patterns(ACM SIGKDD 2004).

DOI: 10.1145/956750.956784

[8] E Keogh and S Kasetty : On the Need for Time Series Data Mining Benchmarks: A Survey and EmPirical Demonstration (Data Mining and Knowledge Discovery 2003).

DOI: 10.1145/775047.775062

[9] Y Tian, R A Hankins and J M Patel : Effcient aggregation for graph summarization(ACM SIGMOD 2008).

[10] N Zhang, Y Tian and J M Patel : Discovery-driven graph summarization(ICDE 2010).

[11] E M Knorr and R T Ng: Algorithms for mining distance-based outliers in large datasets (VLDB 1998).