Count unique visitors by group of visited places

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
]
``````

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?

• For each member of a group, you would create a temporary visit record. Then you can do the quite easy number of unique visitors. Jun 12, 2014 at 16:15
• Thank you @JeffO, but as I said, there are many places, so the number of possible groups is quite huge. In my case, I have approximately 60 places, which leads to something like 1.15E+18 possible groups. So I don't think it would be feasible to store information about so much data. Jun 13, 2014 at 7:26
• @Mathieu with that many permutations, you're going to have worse trouble than just storing the data. Any way of iteration over it is going to have severe performance penalties. Jun 13, 2014 at 9:44
• I don't see why you have to store anything to disk. Create the data in memory a group at a time and do your calcs there. Jun 17, 2014 at 11:54
• Is it neccecary to store the counts of unique visitors? can you not just store the (visitor, place) pairs, and calculate the counts for a place or group when needed? Sep 15, 2014 at 13:11

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.

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.

• Indeed, I have finite visitors and finite 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). I'll edit my question to add this information. What I will have to do with this solution is to count the number of unique visitor identifiers among the lists of visitors of every place. Is that correct? Will it be efficient with so much visitors? Jun 13, 2014 at 7:41

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.

• Thank you @jwenting, I think you are right when you say that I'm going to have to store big amounts of data. It's a good idea to use hashes to only store what I need without storing every possibility. If I understand correctly, for a visitor that has visited the places [x,y,z], I would increment the counters of h(x), h(x,y), h(x,y,z) and h(x,z). With that information about all the visitors, how can I get the number of visitors of [x,y]? Jun 13, 2014 at 12:33
• @Mathieu you'd just retrieve the counter for h(x,y) to retrieve the number of people who've visited both of those locations... Jun 13, 2014 at 12:46
• In that case I would only have the number of visitors that visited x AND y, but I'd like to have the number of visitors that visited x OR y. So I'd have to retrieve the counter of h(x,y) and add the visitors that visited only x and only y. The problem being that I can't just add the counters of h(x) and h(y) because the visitors that visited x and y are already counted there too. Jun 13, 2014 at 12:52
• @Mathieu without storing per unique visitor every location they visit (and how often), that's going to be a tough call. Can do it easily enough, but again you're going to run into data volume problems. Jun 13, 2014 at 14:24