An indoor trajectory frequent pattern mining algorithm based on vague grid sequence

摘要

Trajectory frequent pattern mining is an important branch of data mining. The constraint of indoor space is between Euclid space and road network space, which makes it difficult to represent the approximate positions. Grid partition method is a feasible way to solve this problem, but it will lead to a sharp problem of grid boundary. Considering the indoor trajectory frequent pattern mining, this paper proposes a grid partition method based on vertical projection distance (VGS) and a trajectory frequent pattern mining algorithm based on vague grid sequence (VGS-PrefixSpan). At first, each grid is divided into explicit zones and vague zones according to vertical projection distance. Then the trajectories are transformed into vague grid sequences. At last, VGS-PrefixSpan is a PrefixSpan-like algorithm to mine trajectory frequent patterns from vague grid sequences. Experimental results show that VGS-PrefixSpan has better performance than VSP-PrefixSpan under the same area ratio of explicit zones and covered zones, and has better mining results than VSP-PrefixSpan and GS-PrefixSpan under any value of Min_Support. In terms of mining efficiency, the total time of VGS-PrefixSpan is close to GS-PrefixSpan and less than VSP-PrefixSpan about two orders of magnitude. Therefore, VGS-PrefixSpan is an effective and efficient algorithm in mining frequent patterns of indoor trajectories. As a research hotspot in Location Based Services (LBS), mining frequent patterns of indoor trajectories can protect the trajectory privacy of users from being leaked or mitigating the risk of leakage. Therefore, the study of trajectory frequent patterns is of great significance to public security and personal information protection.