Mining the Most Influential -Location Set from Massive Trajectories
Yuhong Li, Jie Bao, Yanhua Li, Yingcai Wu, Zhiguo Gong, Yu Zheng · IEEE Transactions on Big Data · 2017
Mining the most influential location set finds$k$locations, traversed by the maximum number of unique trajectories, in a given spatial region. These influential locations are valuable for resource allocation applications, such as selecting charging stations for electric automobiles and suggesting locations for placing billboards. This problem is NP-hard and usually calls for an interactive mining processes involving a user's input, e.g., changing the spatial region and$k$, or removing some locations (from the results in the previous round) that are not eligible for an application according to the domain knowledge. Efficiency is the major concern in conducting this human-in-the-loop mining. To this end, we propose a complete mining framework, which includes an optimal method for the light setting (i.e., small region and$k$) and an approximate method for the heavy setting (i.e., large region and$k$). The optimal method leveragesvertex groupingandbest-first pruningtechniques to expedite the mining process. The approximate method can provide the performance guarantee by utilizing the greedy heuristic, and it is comprised ofefficient updating strategy,index partitionandworkload-based optimizationtechniques. We evaluate the efficiency and effectiveness of our methods based on two taxi datasets from China, and one check-in dataset from New York.