Following but not intersecting time segments to detect multiple accounts

Question

In some code I'm currently writing, I'm stuck on the following algorithm to implement. The goal is to find real world users using multiple different accounts.

I've a List of UserData. This list is pretty big (> 10M entries)

A UserData is defined as: { userId, List<TimeSegments> }. A TimeSegment is {connectionDate, disconnectionDate}. We can assume here that the average size of the list of timeSegments is 100.

I want do find groups of users such as:

• for each group of users, all timeSegments are non overlapping (we assume here that a user cannot be connected with multiple accounts at the same time)
• for each user U1 in a group of users, there is a user U2 in the same group such as at least one, U1 disconnected and then U2 connected in the following 15 minutes (or the opposite) (we assume here that at least once, a user will disconnect from an account and with another one immediately after)

Of course, the brute force O(n²) solution (find couples of users and then merge those couples) is not good enough due to the size of data

Any idea of how to start this ?

Thanks !

Answer 1

I would sort all events (logins, logouts) in increasing order by time, then walk through the list. For each logout event from user $u$ starting at time $t$ encountered during this walk, scan forward from that point until hitting time $t+15$, incrementing a counter for the pair $(\min(u, v), \max(u, v))$ in a hashtable whenever a login event for user $v$ occurs. (You could alternatively increment two counters, $(u, v)$ and $(v, u)$, but this uses twice the memory and gains nothing.)

Afterwards, every large count in your hashtable corresponds to a "candidate pair" of users. Walk through the hashtable, and for each counter above a threshold of your choosing, check whether the logged in intervals for this pair of users intersect. If they don't, flag the pair as likely operated by the same human.

(BTW, I'm not confident that mutually exclusivity of login intervals will apply in practice: Users might run their two accounts simultaneously in different browsers, one in a phone, or one in a private window, etc. Depending on your application, maybe a better criterion would be to check whether the two users actually interfere with each other to any significant extent -- e.g., for SO, whether the same questions and answers tend to be upvoted/downvoted.)

There will probably be large numbers of pairs in the hashtable with low counts, due simply to chance. If you find that singleton counts are bloating the hashtable, you could reduce memory usage (at the cost of introducing a very small amount of inaccuracy) by using a Bloom filter to store all "first" encounters of any $(u, v)$ pair, and only creating counts in the main hashtable for a pair $(u, v)$ when $(u, v)$ is already in the Bloom filter.