Flagging possible identical users in an account management system

Question

Hi,

I am working on a possible architecture for an abuse detection mechanism on an account management system. What I want is to detect possible duplicate users based on certain correlating fields within a table. To make the problem simplistic, lets say I have a USER table with the following fields:

Name
Nationality
Current Address
Login
Interests

It is quite possible that one user has created multiple records within this table. There might be a certain pattern in which this user has created his/her accounts. What would it take to mine this table to flag records that may be possible duplicates. Another concern is scale. If we have lets say a million users, taking one user and matching it against the remaining users is unrealistic computationally. What if these records are distributed across various machines in various geographic locations?

What are some of the techniques, that I can use, to solve this problem? I have tried to pose this question in a technologically agnostic manner with the hopes that people can provide me with multiple perspectives.

Thanks

Answer 1

The answer really depends upon how you model your users and what constitutes a duplicate.

There could be a user that uses names from all harry potter characters. Good luck finding that pattern :)

If you are looking for records that are approximately similar try this simple approach: Hash each word in the doc and pick the min shingle. Do this for k different hash functions. Concatenate these min hashes. What you have is a near duplicate.

To be clear, lets say a record has words w1....wn. Lets say your hash functions are h1...hk.

let m_i = min_j (h_i(w_j)

and the signature is S = m1.m2.m3....mk

The cool thing with this signature is that if two documents contain 90% same words then there is a good 90% chance that good chance that the signatures would be the same for the two documents. Hence, instead of looking for near duplicates, you look for exact duplicates in the signatures. If you want to increase the number of matches then you decrease the value of k, if you are getting too many false positives then you increase the number of k.

Of course there is the approach of implicit features of users such as thier IP addresses and cookie etc.