Working With Large Data Sets

R

Robizzle01

Limp Gawd
Joined
Sep 30, 2005
Messages
159
I'm looking to get started with the netflix competition (http://www.netflixprize.com) but the size of the data set is scaring me a little. I have several questions that came up while brainstorming about the problem.

First let me state that I am not planning on winning or even "doing well" in the netflix competition. I see it as a fun problem for me to play with over winter break and a good learning experience, so no flames please.

The set:
The data set is around 17,000 files totaling nearly 2gb. Each user and movie has been assigned a unique interger id. Ratings are provided such that we know the user's id, the movie's id, an integer value from 1-5 inclusive (the rating) and a timestamp for when that rating was given. I also plan to gather information from imdb about which categories each movie belongs to (action, adventure, drama, etc)

I have not parsed the data yet but from what I have read, the average user has provided less than 200 ratings which makes this a very sparse data set.

And now for my questions...
1) The algorithms that I am planning to implement will require me to be able to quickly pull information such as average user rating (across all movies), average rating for a movie
(across all users), and average movie rating for a movie type (ie action.)

I also have all sorts of statistics that I would like to run on the data such as "how many users have supplied 0 ratings, less than 5, less than 100?", "what is the average of all ratings supplied in a given month, year, or whatever time span I want?". These are just a few of the questions I would like to look into before even thinking about writting a movie recommender system. As such, I will need a quick way to play with the data -- I'm guessing you will all recommend using a database but I wanted to check before I spend time on it.

Since I only have experience with databases used by simple php and coldfusion websites (not by computation heavy applications) I would prefer to not use a database but I fear this is not going to be an option if I want the program to finish running any time this year. Is this the case? If so, i'd like to ask how some of you might lay out the database's tables.

I have never been formally taught about databases but it was my understanding that you should never have redundant data nor store values that can be easily calculated (such as an average or the number of times a user has given the rating "1" to a movie. However, for the sake of creating a program that runs quickly, wouldn't it be better if I calculated these values once (when I populate the database) and then my program would only have to run simple queries. The idea being that it is easier for me to do the calculations once and store them than it is to do the calculations at run time every time.

I had some more questions but this is more than a hefty post already and I wont bother with more questions unless I get some interest in the thread. Thanks in advance for any help you may give.
 
Not to be pissy, but two gigs isn't really a "large data set". You shouldn't worry about "large" until you're into several terabytes. Funny thing is that drives keep getting bigger, but they're not much faster. With a good RAID0 setup (See? There really is a valid use for RAID0!) you should be able to read about 100 megs/second. That gets you through your 2 gigs in 20 seconds. The trick is writing code that can keep up with the drive!

You should be using a machine that has at least two gigs of memory; four would be great. And again, this is counter to other advice you'll find on the forum. But being able to get at data within a couple hundred clock cycles is far better than getting at it in a dozen milliseconds.

The questions you're asking are just aggregations of the data in the set. You can write programs to rip through the data and find those values pretty readily. C++ or Perl or whatever you'd like. You'll find that such a program runs slowly because it's doing a ton of I/O, but if you load the data into a database, you'll be doing I/O to write the data, perhaps building an index or two ... and then doing I/O to read the data again so that you can start doing the stats.

A database will come when you start looking at subsets. Say your aggregate data suggests there's a large number of customers who rate all the movies they watch 5-stars. Which customers are those? It's easy to write a SQL query to find them; writing another program to get the data you want is going to be annoying.

If your interest is to just answer a few statistical questions, you might find it best to just write some code to do it. If you have lots of questions, or want to go exploring (that is, you don't knwo what all your questions are just yet) you'll probably be more interested in a database loaded with the data.

Some of the data you say you want is relatively static. Since it is expensive to compute, you might want to write a program that looks at the database, finds the answers, then inserts the computed values into the database. Many people think storing computed values in a database is very bad, but it's actually quite common and very necessary in the data warehousing world. So, indeed, you'd rather calculate things that are difficult to calculate and store the result once than recalculate it every time it is needed. For this project, I think you can do it once and leave it. In a real system, you'd want some mechanism to invalidate the chaced results and replace it with a real, fresh result when some condition is met.

As a shameless plug, the most recent public project I worked on at Microsoft was architecting and implementing SQL Server Integration Services. It is a very flexible tool, and maeks performing loads and in-flight aggregations of large data sets a snap.

You'll also find that Analysis Services is a useful tool for pulling correlations out of large data sets.

Barring those tools, indeed, you'll end up writing this stuff yourself.

If you're going to play with the data in a flexible way while studying it and looking for hints at correlations, I expect you'd rather use a database and write queries instead of writing little programs for each aggregation you want. You might find that some complicated work can't be done in SQL, and you'll need to write programs that do SQL Queries, then do their own more advanced work against the data.

Database modelling is a soft science. You probably should get a book or two on it; since you haven't asked a specific question, I can't provide much details without writing a book about it in response! Some of the table layouts are going to be very much like the format of the files. You should have a Movies reference table, for instance, with the movie ID, the year of release, and the title. You might have customer ID reference tables, and then you'll also have rating tables which relate a movie to a customer to their rating.

Since there's many ways to slice up the data, you'll have to think about what stats you're building for yourself and find a way to store them. Maybe you need a new rating table for each statistic you work up; maybe you need a list of customers who are shitty at giving reviews (once you discover a way to detect a shitty reviewer programatically). Maybe you'll modify the movies table to include average ratings, counts of raters, counts of distinct rating events, and so on.

The model of your database is influenced by the data you'll store and the query you'll write. Since we don't know what you'll be doing in your approach to the problem, we can't responsibly give perscriptive advice.

Another challenge seems minor, but it's profoundly important: that's getting over the data. It looks like Miss Congeniality is the most reviewed movie in the sample data set. That's saddening, but yet you must carry on with your analysis.

Hope that helps. If you have more specific questions, please do let me know and I'll see if I can assist you. (Meanwhile, I'm going to go play with the data my own bad self.)
 
Amazingly, there's a single customer who's reviewed 17653 of the 17770 movies in the sample data.
 
mikeblas said:
Amazingly, there's a single customer who's reviewed 17653 of the 17770 movies in the sample data.
Click to expand...

Yeah, that's me. I didn't have time to watch the other 117. Sorry to disappoint.
 
But you have time to screw around in the forum?

If you figure each movie is two hours, that's just over four soild years of watching movies. Watching four movies a day (for an eight hour day), that's twelve years ... without taking weekends off.

That customer's review scores break down like this:

1 star: 9523
2 stars: 3037
3 stars: 2990
4 stars: 1397
5 stars: 706
 
mikeblas said:
But you have time to screw around in the forum?

If you figure each movie is two hours, that's just over four soild years of watching movies. Watching four movies a day (for an eight hour day), that's twelve years ... without taking weekends off.

That customer's review scores break down like this:

1 star: 9523
2 stars: 3037
3 stars: 2990
4 stars: 1397
5 stars: 706
Click to expand...

What can I say? It's a tough job, but somebody's gotta do it.
 
Well damn, I've only 1gb (2x512) and inserting everything into the database is taking forever. I'm using scripts I found on a blog here: http://www.igvita.com/blog/2006/12/01/loading-netflix-dataset-into-sql/ . However, I have been running the load script for about 8 hours and it has only inserted 19,000 ratings into the database. It got up to 10,000 in about 5 minutes but has been working its way to a crawl since. The cpu is nearly idle and all but 10,000k of my 1gb of ram is in use. I couldn't figure out where the slow down could be coming from since the scripts provided on the blog above produced 17,770 files and the script that inserts them into the database inserts one file at a time. Then I noticed that the script from that blog generates ten files that are each over 900mb. I imagine inserting these into the database is causing an issue.

I'm planning on letting this script run for a few days if I need to but this is making me rethink how I will handle this data in the algorithm I eventually implement. Actually, I have an algorithm that I created for my information retrieval class this semester that I'd like to try out just to see what it does on a larger data set. The problem being that I don't know what to do with all this data unless I can either find a way to store it all in under about 800mb of ram or if I find out that constantly accessing files on drive is anywhere close to feasable (I doubt it.)

I checked out the current prices of ram on newegg and it looks like either I put it on my Christmas list or I need to rethink my strategies. (About $180 for two 1gb pc3200)

Also, sorry if I don't reply very quickly. This upcoming week is finals week and I should probably try to do a little studying.
 
Robizzle01 said:
However, I have been running the load script for about 8 hours and it has only inserted 19,000 ratings into the database.
Click to expand...
That's hopeless! There's more than 100 million reviews, so you're going to be waiting 1754 days, if things are linear for you. See you in four years!

I still don't know w hat DBMS you're using, but SQL server on my 3.0 MHz Petium laptop can sustain about 25,000 inserts per second on this data. My laptop is the slowest machine in my house.
 
My (big) mistake, I meant 19 million, not thousand. Its at 41 million now after 24 hours of running. This is with mySQL using the MyISAM storage engine. So at this rate I should be done in a few more days. My major concern isn't getting this into the database, but instead, how long the queries will take.

If this database is unusable because of my lack of ram do I have any hope of working on the netflix set?
 
That's much better, but that's still only 475 rows per second. If you have 32 bytes per row (which seems like a decent guess), you're only getting 15100 bytes per second throughput, which is really bad. You might want to see what's wrong with your server.

What are the specs of your server?

The C++ code I've written to parse and summarize the data set runs in about 90 seconds, which means I'm processing about 30 million bytes per second (over the 2.7 gig total size of all the review files). This is on a 3.2 GHz Pentium Socket 775 machine with 3 gigs of memory. The data is on a RAID0 array of two Hitachi 300 gig drives.

I can't predict how performance will be since I'm not a MySQL user (for obvious reasons!). Memory will help with caching in your database server, so I think it's a must: it's cheap and is likely to help other applications that you're using. But because of the nature of this work, I think you'll find that caching isn't very important, though. When you run a query to do an aggreation statistic, you'll find that you're scanning the whole table sequentially. That means I/O is more interesting than caching, since you're just going read the whole table once and the whole table won't fit into memory anyway.

For me, the next step is coming up with a plausible algorithm that finds similar reviewers to a given customer.
 
My server is a AMD64 3000+ with 2x512mb of 3200 ddr ram. For storage i'm using two 300gb drives (not in any kind of raid.) Its running Gentoo Linux and for the most part sits around doing nothing (it is running apache, samba and an iTunes music share but those are only ever used for personal use.)

I realize that something is seriously wrong with it importing the data this slowly. All it should have to do is read in 2.5gb worth of native sql import files which should be bottlenecked by I/O ... not ram.

About your code: I'm assuming you read in all the data from file and then start making calculations without ever having to do I/O. How much memory does all that data take up the way you coded it?

I'm thinking that since I cant store everything in my 1gb of ram that I should reorganize the data to take up lots of disc space but provide quick look-up. Something along the lines of having two sets of the data. One set being a file for each user that contains a movie id, timestamp and rating (sorted by ascending movie id) and a second set being a file for each movie containing a user id, timestamp and rating (sorted by ascending user id).

On an unrelated note: how important do you think it is to have timestamps available for when each rating was made. I have a feeling that considering times won't give much better results than ignoring them.
 
I don't have the reviews in memory yet. That'll have to wait until I decide on an algorithm to get 'em loaded. The file of all the reviews is 2.7 gigs, but there's redundant data in it so I'm hoping I can use around 2.0 gigs of storage. The algorithm I'm thinking of using to find matching reviewers is not going to need all of the data in memory at once, anyway.
 
You must log in or register to reply here.
Back
Top