Research On Graph Mining Algorithms Based On RFID Logistics

With the advances in technology, RFID (Radio Frequency Identification) technology has been widely used in many fields, such as the warehouse management and logistics, mail/express parcel processing, library management, health care and so on. RFID technology combined to the Internet and communication technology, can make the item numbering, identification, cataloging, tracking and information sharing achive on a global scale. Taking the RFID technology into supply chain management, can track the trajectory of moving objects in logistics network, and provide strong support for the users’ decision. Commodity flows will produce large amount of structural data, mining in such RFID path data faces problems mainly in the following several aspects:(1) Lack of model that can effective present a variety of information on RFID applications;(2) Unfavorable to data analysis for huge amount of raw RFID data and the lowest level of abstraction;(3) Trajectory clustering can effectively predict the trend of movement of objects. Existing trajectory clustering algorithms group similar trajectories as a whole, but it could miss common sub-trajectories.The most important data in RFID system is the data of moving, called path data or track data. The main task for RFID data mining is mining frequency paths. We research the path data, propose some methods for mining high frequency path in database, and the users can understand the moving trends to optimize the supply chain. In this paper, based on the research at home and abroad, we design efficient graph modeling method of RFID data warehouse, propose frequent paths mining algorithm for graph-based data, compress RFID data warehouse, and discuss tracks of moving objects classification-clustering methods in RFID tracking system. Main innovations are as follows:1) The traditional data warehouse did not consider the relationship between different tuples, while the RFID data tuple contains structure, such as the path information. In this paper, for such structural data, we propose a graph modeling method, which will apply the graph-based OLAP framework into the RFID logistics management, then establish graph model for the transport paths of goods. Based on FlowGraph thought that apply graph to the logistics, which means using graph to represent logistics information, users can do relevant OLAP operations on graph sets according to their own interest, so to get useful results, to improve query efficiency. 2) For the atlas based on RFID logistics data, we will provide the Rmine algorithm in this paper. The problem of mining frequent path will be converted into frequent graph mining. While generating a large number of logistic graphs, and the user is only interested in one part of them, we can start to find out graph sets to meet customer needs from atlas, and then we take the DFS (depth first search) method to generate frequent subgraphs, thus it can reduce the costs of subgraphs isomorphism enumeration, and speed up the rate of frequent graphs mining.3) Unfavorable to data analysis for huge amount of raw RFID data and the lowest level of abstraction. Construct RFID data warehouse by graph, and propose the graph generalization method. We can divide the nodes of the graph into groups, according to attributes and relationships selected by the user, and the level of generalization controlled by the user. Namely, the size of graph summarization depends on k (the number of groups). According to the size of the current group, choose either the divide operation to make more precise division on the original group, or the merge operation to combine the original ones. Using prune to compress atlas, reduce the data sets, let frequent graph mining algorithm execute on the shrinked graph and raise the efficiency of the frequent graph mining algorithm.4) Existing trajectory clustering algorithms group similar trajectories as a whole, but it could miss common sub-trajectories. However, in practical applications, the user may focuse only on particular areas, which needs to find similar sub-trajectories in some regions. In this paper, we propose PT-CLUS algorithm, which first partitions a trajectory into a set of line segments and prunes by coarse-fine strategy and speed up at the clustering phase. Then, it searches clusters in the sub-trajectories by checking the neighborhood of each line segment, and uses hierarchical clustering method to clustering trajectories.