In this paper, we explore a new data mining capability that involves mining calling path patterns in global system for mobile communication (GSM) networks. Our proposed method consists of two phases. First, we devise a data structure to convert the original calling paths in the log file into a frequent calling path graph. Second, we design an algorithm to mine the calling path patterns from the frequent calling path graph obtained. By using the frequent calling path graph to mine the calling path patterns, our proposed algorithm does not generate unnecessary candidate patterns and requires less database scans. If the corresponding calling path graph of the GSM network can be fitted in the main memory, our proposed algorithm scans the database only once. Otherwise, the cellular structure of the GSM network is divided into several partitions so that the corresponding calling path sub-graph of each partition can be fitted in the main memory. The number of database scans for this case is equal to the number of partitioned sub-graphs. Therefore, our proposed algorithm is more efficient than the PrefixSpan and a priori-like approaches. The experimental results show that our proposed algorithm outperforms the a priori-like and PrefixSpan approaches by several orders of magnitude.
With the increasing use of computing for various applications, the importance of mining knowledge from large databases is growing at a rapid pace recently. There is a large amount of valuable information embedded in databases or data warehouses which is useful for analyzing customer’s buying behavior and thus improving the business decisions.
Data mining is an application-specific issue and various mining techniques have been developed to solve different application problems, such as mining association rules [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11] and [12], classification [13], [14], [15] and [16], clustering [17], [18], [19], [20], [21] and [22], sequential patterns [23], [24], [25] and [26], partial periodic patterns [27], and path traversal patterns in World Wide Web [28].
To the best of our knowledge, there are no data mining techniques specially designed to analyze the sequential patterns of users’ calling paths in a global system for mobile communication (GSM) network, and we believe that it is an interesting issue especially on providing mobile broadband services. A GSM network is based on the cellular radio technology [29]. A particularly characteristic feature of cellular radio is that each hexagonal (six-sided polygon) cell (the radius of a base station) is surrounded by at most six neighboring cells. Fig. 1 illustrates the cellular structure of a GSM network.
In this paper, we explore a new data mining capability that involves mining calling path patterns in GSM networks. Since a vertex in the corresponding calling path graph of the GSM network has at most 36 in–out paths and six out-edges, we require the fixed amount of storage to store the information of those in–out paths and out-edges for each vertex. By using the constraint of limited number of neighboring cells in GSM networks, we devise a data structure, called frequent calling path graph (or sub-graphs), to store the necessary information of mining PMFCPs. Then, we design the graph-based mining algorithm to mine the PMFCPs from the frequent calling path graph (or sub-graphs) obtained.
By using the frequent calling path graph (or sub-graphs) to mine the calling path patterns, our proposed algorithm requires less database scans and does not generate unnecessary candidates. Therefore, our proposed algorithm is much more efficient than the a priori-like and the PrefixSpan algorithms. The experimental results show that our proposed algorithm performs significantly better than the a priori-like and the PrefixSpan algorithms by several orders of magnitude.
