Count unique visitors by group of visited places

Question

I'm facing the problem of counting the unique visitors of groups of places.

Here is the situation:

I have visitors that can visit places. For example, that can be internet users visiting web pages, or customers going to restaurants. A visitor can visit as much places as he wishes, and a place can be visited by several visitors. A visitor can come to the same place several times.

The places belong to groups. A group can obviously contain several places, and places can belong to several groups.

Given that, for each visitor, we can have a list of visited places, how can I have the number of unique visitors per group of places?

Example: I have visitors A, B, C and D; and I have places x, y and z.

I have these visiting lists:

[
 A -> [x,x,y,x],
 B -> [],
 C -> [z,z],
 D -> [y,x,x,z]
]

Having these number of unique visitors per place is quite easy:

[
 x -> 2, // A and D visited x
 y -> 2, // A and D visited y
 z -> 2  // C and D visited z
]

But if I have these groups:

[
 G1 -> [x,y,z],
 G2 -> [x,z],
 G3 -> [x,y]
]

How can I have this information?

[
 G1 -> 3, // A, C and D visited x or y or z
 G2 -> 3, // A, C and D visited x or z
 G3 -> 2  // A and D visited x or y
]

Additional notes :

1. There are so many places that it is not possible to store information about every possible group;
2. It's not a problem if approximation are made. I don't need 100% precision. Having a fast algorithm that tells me that there were 12345 visits in a group instead of 12543 is better than a slow algorithm telling the exact number. Let's say there can be ~5% deviation.
3. I have a finite number of visitors and a finite number of places. I don't have so much places (approximately 60 for now, but it can grow to 200) but I have quite many visitors (estimated to 50 millions and this number could grow to 200 millions in the next months).

Is there an algorithm or class of algorithms that addresses this type of problem?

Answer 1

I'm answering my own question because I think I have found a way to avoid storing huge quantities of data. Of course it implies an approximation but, as I said, that is not important to have the exact number of unique visitors.

What I need is a table that maps, for each place, the total number of visits. So, following the example I gave in the question, I would have this:

[
 x -> 5,
 y -> 2,
 z -> 3
]

Then, I store a counter of the total number of unique visitors, which is 3 (and not 4 because B didn't visit anything).

I also store the total number of visits: 10.

To know the (approximate) number of unique visitors, I do a cross-multiplication. I sum their total number of visits and divide that number by the total number of visits. I multiply that result by the total number of unique visitors.

It is equivalent to say: "If a group makes a proportion p of the visits, I suppose it also holds the same proportion p of the unique visitors".

Let's take the groups from the question:

[
 G1 -> [x,y,z],
 G2 -> [x,z],
 G3 -> [x,y]
]

We can get their (approximative) number of unique visitors like this:

[
 G1 -> ((5+2+3)/10) * 3 = 3
 G2 -> ((5+3)/10) * 3 = 2.4
 G3 -> ((5+2)/10) * 3 = 2.1
]

The numbers [3, 2.4, 2.1] are not very far from the real result [3, 3, 2].

What we can say is that:

1. For the special case of the group that holds all the places, the returned result is not an approximation, it is exact.
2. For other cases, it works well if all the visitors have the same visit comportment. For example, having some visitors that visit many places only once and some visitors that visit only one place many times won't yield to good results.
3. The worst case would be that, in a first group all the places have very few different visitors that come many times and, in a second group, there would be many different visitors that only come one time. The number of unique visitors of the first group would be overrated while it would be underrated for the second group.

Answer 2

Appears you have finite visitors and finite places to visit just in multiple combinations. If so, then you can know who visited. How? I recommend using a queue for each place to be visited.

When visitors visit, enqueue them (place them into the queue). If visitors visit multiple times, they will be in the queue multiple times.

Since you are only interested in knowing whether visitors have visited, perform a dequeue (remove them from the queue) and record who visited.

With this method, you should be able to accurately record who visited what, how many times, and in what order.

Answer 3

As you point out, storing the number of visitors for each possible permutation would be a massive amount of data, or at least a table in your database with a massive number of records.
There's however really no way around it, you're going to have to store it, else how can you remember what the previous count was in order to increase it?
So what you do is you store only those permutations and their count where there actually have been visitors (My guess would be that that would be a lot less than the total possible number of permutations, for example if you're counting visitors to your store locations around the world, a lot of people will visit the few stores in their general area but never those on the other side of the world).

Find some way to encode the actual set uniquely (say as a hash of sorts), then use that as a key into a database table.
When you've determined the hash for a person, look up that hash in the visitor count table. If it exists, increase the count. If it doesn't exist, insert a new record with count = 1.
Another table can then hold that hash in relation to your locations, so you can retrieve the locations belonging to each hash for reporting purposes. Say a simple table [location_id, hash] where the combination is the primary key, both being themselves foreign keys into your locations table and counts table respectively. (and those records too ony inserted at the time you insert a new record into the counts table)

That means initial inserts are relatively slow, updates are as fast as they're going to get, and so is retrieval. Which, for a large potential set of data from which you're only going to be using a relatively small subset is the best you can hope for.