Mobile Trajectories Mining Algorithmic Design And System Implementation

In daily activities of people,there produces a wide variety of trajectory data, such as GPS trajectory data, mobile trajectory data, etc. Trajectory data contains a large amount of information and there are a wide range of research and application prospect in the field of security monitoring and data mining, and it is a hot research topic mining trajectory data at different scales. We regard trajectory data as the research object, mining trajectory data on micro angle and macro angle, and put forward some algorithms respectively on the trajectory retrieval problem and community searching problem,and we also designed a demo system.At the micro issues involving the specific trajectory of retrieval, we propose some new index structures and algorithms to retrieve mobile phone trajectory. Its innovations are as follows: 1. we are the first to design a new threaded tree structure to index mobile phone trajectory. 2. We are the first to adopt a heuristics based query optimization algorithm to retrieve mobile phone trajectory and prune unnecessary data access. This new algorithm is used in Security monitoring to help people with video data of monitoring and we put forward a new mobile phone identify and track method. When given a spatio-temporal sequence of one suspect which is captured by the surveillance cameras, we can trace his phone by searching for the phones which have trajectories compatible with this sequence, after that we can get the suspect’s phone number. The mobile phone trajectory dataset(40GB, more than 100 million records) of Guangzhou in China was used to test our new algorithms, and we found one suspect’s phone can be uniquely identi?ed while he is captured by more than four cameras distributed in different cells of the mobile network, and the searching job took less than one second.At the macro issues involving community searching base on trajectory data, we put forward a new hierarchical clustering algorithm based on entropy. Its innovations are as follows: 1. We are the first to use this new entropy guidance function to guide the merging of different community. 2. We are the first to guide the merging with both spatial information and topology relationship of trajectory data, and it is a new hierarchical clustering algorithm. We use the new algorithm to discover community or regional group from trajectory dataset. This new algorithm can find out those groups whose members are close to each other and maintained close ties with each other, and they have similar contact to the members of other groups from trajectory dataset. And this can help us a lot to deal with such as disease spreading and controlling, power loss distribution found, targeted advertising pushing, and so on. Taxi GPS trajectory dataset of New York(11GB, about 200 million records) is used to test the new algorithm. Experiment shows that meaningful groups/community can be divided accurately by the new algorithm.