Matching User Accounts across Large-scale Social Networks based on Locality-sensitive Hashing

Cross-site user identification has recently attracted considerable attention from academia. Most existing methods mainly focus on measuring the similarity between two cross-site accounts, and few methods focus on matching the accounts of all users to the greatest extent possible, which may be due to the massive calculation problem of the latter case. As the first work to address this issue, we present a locality-sensitive hashing-based user identification (LoSHui), which mainly consists of four components. 1) We construct locality-sensitive hash function families that are suitable for determining the user trajectory. 2) After that, we present a method for projecting the users into buckets, which guarantees that two users with similar trajectories are placed in the same bucket with high probability. 3) Then, we construct the candidate user pairs in each hash bucket. 4) Finally, we propose a trajectory-based user identification on the chosen candidate pairs. Experiments on three ground-truth datasets show that LoSHui achieves excellent performance with the ratio of reduced running time reaching 82.81%, 70.77%, and 77.44%, which demonstrates that LoSHui can substantially reduce the number of calculations in user identification.