Efficiently counting co-occurrences in a large dataset

Came across this interview programming test recently:

• You're given a list of top 50 favorite artists for 1000 users (from last.fm)
• Generate a list of all artist pairs that appear together at least 50 times.
• The solution can't store in memory, or evaluate all possible pairs.
• The solution should be scalable to larger datasets.
• The 开发者_运维问答solution doesn't have to be exact, ie you can report pairs with a high probability of meeting the cutoff.

I feel I have a pretty workable solution, but I'm wondering if they were looking for something specific that I missed.

(In case it makes a difference - this isn't from my own interviewing, so I'm not trying to cheat any prospective employers)

Here are my assumptions:

• There's a finite maximum number of artists (622K according to MusicBrainz), while there is no limit on the number of users (well, not more than ~7 billion, I guess).
• Artists follow a "long tail" distribution: a few are popular, but most are favorited by a very small number of users.
• The cutoff, is chosen to select a certain percentage of artists (around 1% with 50 and the given data) so it will increase as the number of users increases.

The third requirement is a little vague - technically, if you have any exact solution you've "evaluated all possible pairs".

Practical Solution

1. first pass: convert artist names to numeric ids; store converted favorite data in a temp file; keep count of user favorites for each artist.

   Requires a string->int map to keep track of assigned ids; can use a Patricia tree if space is more important than speed (needed 1/5th the space and twice the time in my, admittedly not very rigorous, tests).

2. second pass: iterate over the temp file; throw out artists which didn't, individually, meet the cutoff; keep counts of pairs in a 2d matrix.

   Will require n(n-1)/2 bytes (or shorts, or ints, depending on the data size) plus the array reference overhead. Shouldn't be a problem since n is, at most, 0.01-0.05 of 622K.

This seems like it can process any sized real-world dataset using less than 100MB of memory.

Alternate Solution

If you can't do multiple passes (for whatever contrived reason), use an array of Bloom filters to keep the pair counts: for each pair you encounter, find the highest filter it's (probably) in, and add to the next highest one. So, first time it's added to bf[0], second time bf[1], and so on until bf[49]. Or can revert to keeping actual counts after a certain point.

I haven't run the numbers, but the lowest few filters will be quite sizable - it's not my favorite solution, but it could work.

Any other ideas?

You should consider one of the existing approaches for mining association rules. This is a well-researched problem, and it is unlikely that a home-grown solution would be much faster. Some references:

1. Wikipedia has a non-terrible list of implementations http://en.wikipedia.org/wiki/Association_rule_learning .

2. Citing a previous answer of mine: What is the most efficient way to access particular elements in a SortedSet? .

There is a repository of existing implementations here: http://fimi.ua.ac.be/src/ . These are tools that participated in a performance competition a few years back; many of them come with indicative papers to explain how/when/why they are faster than other algorithms.

With two points of the requirement being about inexact solution, I'm guessing they're looking for a fast shortcut approximation instead of an exhaustive search. So here's my idea:

Suppose that there is absolutely no correlation between a fan's choices for favorite artists. This is, of course, surely false. Someone who likes Rembrandt is far more likely to also like Rubens then he is to also like Pollock. (You did say we were picking favorite artists, right?) I'll get back to this in a moment.

Then make a pass through the data, counting the number of distinct artists, the number of fans, and how often each artist shows up as a favorite. When we're done making this pass: (1) Eliminate any artists who don't individually show up the required number of "pair times". If an arist only shows up 40 times, he can't possibly be included in more than 40 pairs. (2) For the remaining artists, convert each "like count" to a percentage, i.e. this artist was liked by, say, 10% of the fans. Then for each pair of artists, multiple their like percentages together and then multiply by the total number of fans. This is the estimated number of times they'd show up as a pair.

For example, suppose of 1000 fans, 200 say they like Rembrandt and 100 say they like Michaelangelo. That means 20% for Rembrandt and 10% for Michaelangelo. So if there's no correlation, we'd estimate that 20% * 10% * 1000 = 20 like both. This is below the threshold so we wouldn't include this pair.

The catch to this is that there almost surely is a correlation between "likes". My first thought would be to study some real data and see how much of a correlation there is, that is, how the real pair counts differs from the estimate. If we find that, say, the real count is rarely more than twice the estimated count, then we could just say that any pair that gives an estimate over 1/2 of the threshold we declare a "candidate". Then we do an exhaustive count on the candidates to see how many really meet the condition. This would allow us to eliminate all the pairs that fall well below the threshold as "unlikely" and thus not worth the cost of investigating.

This could miss pairs when the artists almost always occur together. If, say, 100 fans like Picasso, 60 like Van Gogh, and of the 60 who like Van Gogh 50 also like Picasso, their estimate will be MUCH lower than their actual. If this happens rarely enough it may fall into the acceptable "exact answer not required" category. If it happens all the time this approach won't work.