Assigned: Wednesday, Apr 6, 2016
Due: Friday, Apr 22, 2016 at 10:30pm
Collaboration: Work with your assigned partner for this lab. You may use your classmates and their code as a resource, but please cite them. Sharing of complete or nearly-complete answers is not permitted.
Twitter makes a stream of live tweets available for free online, and we’ll be using GPUs to analyze this stream to figure out what is happening on twitter in real time. There are a few key pieces to this project:
The idea is that this process will run repeatedly; your program will collect tweets, cluster them, print the results, then repeat the process for a new batch of tweets. This will give you a view of topics on twitter as they evolve over time.
The following sections describe each of the key pieces of the project.
While you’ll have to pay twitter a lot of money to access the full stream of tweets in real time, twitter has a free sampled stream that gives you access to 1% of live tweets.
To access this stream, you won’t have to write any code;
we’ll use a simple shell utility called curl that can transfer data over the network.
You will need to set up a developer account with twitter to access the stream, but there is a file that contains about 10 minutes of tweets in /home/curtsinger/data/tweets.json that you can use for the project instead of relying on a network connection.
Disclaimer: The pre-collected twitter data and any live data from twitter will likely contain objectionable content. I do not endorse and of the stupid things people write on the internet, and you probably shouldn’t either. Instructions for collecting a filtered stream are included in italics below.
When you have your entire system working and you want to access the real twitter stream, you will need to follow these steps:
language=en to the “Request Query” field at the bottom of the form.curl command you can use to access the twitter stream. Copy this command, paste it into a terminal, and hit enter. You should see a few messages about certificates followed by a stream of tweets.If you would prefer to have a filtered stream of tweets, you can set the Request Query field to language=en&filter_level=medium. The stream will still almost certainly contain objectionable content, but there will probably be less of it.
This process gives you access to the stream, but your access will not last forever;
if you don’t use the curl command for a while, you will need to refresh the form page and re-submit to get a new set of credentials before you can access the stream.
Since we’re using curl to access the stream, we can just use shell pipes to send this as to our analysis program.
For example, the command curl ... | ./my-program runs the curl command and provides its output as standard input to the my-program executable in the current directory.
To use the pre-collected twitter stream data, use the command cat /home/curtsinger/data/tweets.json | ./my-program.
This accomplishes the same thing, but uses the stored data rather than getting new tweets over the network.
The twitter stream is in a format called JSON. This is actually a subset of JavaScript that allows you to write down objects. You can think of JavaScript objects as a dictionary or hash table, with keys (which are strings) and values. Each tweet is a single JavaScript object, and is on its own line of standard input. There are quite a few fields in each tweet object, but we’re interested in the “text” field, which holds the actual text in the tweet.
We’ll use the jansson library to read JSON data rather than writing a custom input parser. The starter code for this lab already reads a line of input at a time, parses this line with jansson, and prints out the tweet text. You should not need to deal with JSON or use jansson outside of the provided code.
Your code should read in tweets, cluster them, and then repeat with the remaining input. Make sure it is easy to change so you can adjust it up or down to keep pace with the live twitter stream once you have the whole process working; a higher value of will give you more meaningful clusters, but it will be more expensive to compute.
Compressed representations are good for reducing the size of data, changing the format of data to make them suitable for a particular kind of processing, and for reducing duplicated work. The choice of a compressed representation depends on what you’ll be doing with that compressed representation.
We’ll be using a simple model of text similarity to compare two tweets, looking just at the number of words that appear in both tweets. This model treats tweets as a “bag of words,” or simply a set of all the words in a tweet. The similarity of two tweets is simply the number of shared words divided by the total number of words; this measure of similarity is known as the Jaccard index. For example, consider the following tweets:
I really really like Computer Science.
8am is really early for a computer science class.
Of the six words in the first tweet, three appear in the second: really (only the first one), computer, and science.
Between the two tweets, there are six unshared words of at least three characters (the second really, like, 8am, early, for, and class).
The similarity of these two tweets is .
Your text similarity computation should ignore both punctuation and case when comparing words.
GPUs aren’t particularly good at dealing with strings, and our similarity computation doesn’t actually depend on the words themselves; we just need to be able to check whether two words are identical or not. We also know that tweets have a bounded length of 140 characters. We’ll assume for the purposes of this lab that we aren’t interested in any words that are less than 3 characters long, and that there will only be 32 words in each tweet (we’ll just ignore the last few if there happen to be more). Instead of storing words, we could instead use an array of 32 integers to represent a tweet, where each integer corresponds to one of the words in the tweet. For example, here is a potential representation for our example tweets:
const char* tweet1 = "I really really like Computer Science."
int tweet1_compressed[] = {8, 8, 49, 135, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
const char* tweet2 = "8am is really early for a computer science class."
int tweet2_compressed[] = {17, 8, 7, 99, 135, 2, 91, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
For the example representations above, notice that words of less than three characters are excluded.
Identical words have the same integer values, regardless of case and punctuation.
Any extra spaces in the array are filled in with zeros to indicate that there are no additional words.
This representation is much more GPU-friendly because it uses a short array of four byte integers rather than an array of bytes that need to be examined to group together characters that are part of the same word.
We can still use this representation to compute tweet similarity: there are 15 non-zero entries, and four of the entries in tweet1_compressed also appear in tweet2_compressed.
Hopefully this representation makes more sense, but we haven’t said how we’ll choose the actual integer values for words. We could assign each word an ID the first time we see it, then look up that ID on all successive instances. While this would work, it would be quite slow; looking up the ID would require accessing a data structure that contains all of the unique words being used on twitter. Even with a very efficient data structure this is likely impractical.
Instead, we can opt for a solution that is good enough; just use a hash function. By using a hash function, we are allowing the possibility that two different words will have the same integer representation. However, there are approximately four billion unique values for a 32 bit integer, so spurious hash collisions are quite unlikely. A few words that are mis-identified as identical won’t throw our results off too much, so this simpler solution should be fine.
Implement your conversion to a compressed representation on the CPU. I recommend you use the Jenkins Hash to compute hash values for words after converting them to lowercase and removing any punctuation.
Clustering is the basic problem of grouping a large set of values into sub-groups based on their similarity. The typical approach is to maximize the degree of similarity within each cluster (or minimize the distance). For this lab, we will be using the k-mediods clustering algorith with Voroni iteration. While this may sound scary, the idea is pretty simple:
The largest cost in running the algorithm above is in computing the similarity of all pairs of tweets. Instead of performing this comparison repeatedly, you should build a similarity matrix. For a batch of tweets, you should have an similarity matrix, which I will call . The cell stores the similarity of tweets and . If you pre-compute this matrix you can assign tweets to clusters and identify new cluster centers without re-computing any tweet similarities. You should build the similarity matrix on the GPU as well.
We haven’t worked with two-dimensional arrays on the GPU, but this post should be helpful. Most of the mechanics are the same, there are just some small changes when launching kernels and computing indices into the array.
Follow the usual process to clone the starter code at github.com/grinnell-cs/213-twitter.
This starter code uses a simpler Makefile setup than the other labs, but it should still be helpful.
Type make to build the program, or make run to run it with the sample data.
If you want to run the program without make you will need to add the line LD_LIBRARY_PATH=/home/curtsinger/lib so the program can find the jansson library, which is not installed globally.
As usual, save and commit frequently, and make sure you write detailed comments.
Your final program should meet the following requirements:
Once you have the entire system running, test it with the live twitter stream. You should adjust up as high as possible without falling behind on clustering; if it takes ten seconds to process 4000 tweets but you are receiving 5000 tweets in that time, your program will fall behind. This tuning will depend on your machine, the efficiency of your implementation, and the volume of tweets at the moment you are testing, so it will vary from group to group.