We live in an era where we leave traces of our personal data using the world wide web. Companies that store and analyze such data are facing the challenges of computational and spatial complexity due to their large quantity. In our master's thesis, we tried to solve one of these challenges by identifying linked accounts in large data sets. We analyzed time complexity and computational efficiency of methods used for searching pairs of highly similar accounts. The experiments were carried out on two data sets. In this paper, we presented data transformation and their presentation in a sparse matrix. Next, we searched for pairs of accounts with the cosine similarity above the threshold with the exact All Pairs method, the Locality-Sensitive Hashing, and Bisecting K-Means. Our goal was to evaluate which of these methods yield the best performance with acceptable processing time. To conclude, we found that the All Pairs method is inadequate for practical use due to its time inefficiency. Performance of approximation methods depends on the choice of parameters. It turned out that the LSH method finds pairs with similarity over 80% in the shortest time, but in case of time complexity Bisecting K-Means is more efficient for the lower limits of the similarity.
|
