Efficient mining of group patterns for mobile users
Yida Wang · 2005
Mobile phones and other mobile devices are fast becoming indispensable in our modern society, inspiring many emerging applications.In this thesis, we propose novel approaches to derive useful grouping information from a movement database of users' locations gathered from mobile devices over a time period.We are interested in discovering groups of users such that members in the same group are spatially close to one another for significant amount of time.Such a user group is also known as group pattern.In order to discover the complete set of valid group patterns, we develop two algorithms, namely AGP and VG-growth.AGP is derived from the well known Apriori algorithm [AS94], while VG-growth adopts a mining strategy similar to FP-growth algorithm [HPY00] but is based on a novel data structure known as VG-graph.We have conducted extensive experiments to evaluate the performance of AGP and VG-growth using datasets synthetically generated by IBM City Simulator [KMJ01].The results have shown that VGgrowth is much faster than AGP for mining valid k-groups (k > 2), especially for small min wei threshold.As the mining of valid groups of size two is a bottleneck for both AGP and VG-growth, especially for large number of users and long logging duration, we further propose a group pattern mining framework that accommodates different location summarization methods.Each method reduces the number of time points to be scanned and the number of candidate 2-groups to be examined.Under this framework, several location summarization methods have been proposed.Experiments have shown that the location summarization based algorithms reduce the mining overhead for valid group patterns of size two significantly.We finally identify the redundancy problem of mining the complete set of valid group patterns due to the exponential enumeration of all possible valid groups.We therefore address this problem by mining only the set of maximal valid groups, which provides the i