# Following but not intersecting time segments to detect multiple accounts

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 !

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.)
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.