The last month

Hopefully my employer doesn't have my blog in his RSS feed :)

Over the last month I have interviewed with a number of great companies. I have had a blast going and visiting with the brilliant people that inhabit the halls of Google, Yahoo!, Amazon, and Microsoft. I have, or am receiving, offers from three of the four. It is definitely an exciting time as I rush to look at places to live, schools for the children and compare things like benefits, stock prices, growth potential, and perks.

It will be sad to leave my family and friends; adjustments will be necessary all the way around. However, I am very excited about the opportunities that lay ahead.

I won't describe the interview process or questions. However, I will say that all of the questions were very intelligent and relevant. It helps to know core algorithms and data structures such as lists, queues, and trees. Graph algorithms and advanced data structures like heaps and splay trees are also good to know. More generally, you just need to be able to tear a problem apart and reduce it to its essence. They want to see that you can analyze a problem and coming up with the right solution immediately is not as valuable as coming up with many solutions and being able to weigh them.

All of the companies had extraordinary employees, a great culture, and innovative systems. They all operate at "web scale" which means their problems are MASSIVE. No matter which company I choose, it will be a great choice.

I'm looking forward to the journey and I'll keep you all updated.

ArsDigita University

There are a lot of great free videos from Ars Digita University. Check them out!

Researching in a Search 2.0 world

A lot of my time is spent researching. A LOT of my time is spent researching. I research things around record linkage. I also research clustering, classification, natural language processing, and machine learning, in general. Quite a few times, I have to get up to speed. I need to understand what Felligi and Sunter did in the 1960s before I can understand what Winkler added to it in the 90s and what the general entity resolution research is all about now. Or, perhaps I just want to be a better programmer. Perhaps move from a O(N) to O(log N) on the Programmer Competency Matrix.

For Search 2.0, much of the hullabaloo has been about Natural Language Processing (NLP). Companies such as Powerset have touted their products as being able to understand a human query. For instance, the powerset engineers have given demos where they ask their engine "Which politicians died of disease?" and it gives back a list. This approach is great if I'm after general information, or if I'm helping my kid with her homework. However, it doesn't give me perspective about research. Why am I asking about politicians and disease anyway? Am I trying to get a statistical view of politicians that die of disease vs the health of the rest of the populace? Am I trying to understand the effects of an ill politician on the society? I might wish to see the sites that others also searched for, much like the Amazon feature. Or, maybe I want additional statistics about that country during the time period. In other words, I need more than just the answer to my question. I need a path that others have followed that I can follow as well. Eventually, I'll have to get off the path, but I want to stay on it as long as possible.

In addition, I want to quickly understand an author's position. I want to know, with my search results, whether this author is an expert or a novice in the field. I want to know where his or her funding comes from. I want to know, based on statistical analysis of their previous posts, if they are conservative or liberal. Have they published papers? If so, in what journals? Are they top journals? It is this context that will make search valuable. Whether or not I can ask a specific question is irrelevant to me. I'll figure out a way to ask the question; however, I want more information back in an easy to understand manner. I want the site's PageRank, I want a general view of how other sites have posted about the site in question (positive or negative), I want to see complaints or complements if it is a potential employer. I want CONTEXT. It seems to me that people get on the internet a lot for research. You research a good book to buy or what digital camera to get or where to go on vacation. All of these things could be enhanced by adding more context, more data mining, and better presentation of the information.

That will be search 2.0.

Where is the software that enables the long tail?

For a product to reach the long tail, it has to have three things.
First, it has to have a low barrier of entry. Anyone needs to be able to create content and publish it. Second, it has to be easy to access. This means it must be searchable. Finally, it has to allow others to review and comment. That's it. It's not rocket science.

Unfortunately, I'm having tremendous trouble finding software to enable the long tail. I really don't have overly strict requirements. In application 1, I want to be able to allow people to post Java jar files. I might want to check things on post, such as does it have a MANIFEST? In application 2, I have a site where I am putting up papers about record linkage. I want others to be able to post links and have the software verify that the links exist. In each application, I'd like to also allow them to associate a title with either the jar file or the link.

For search, I want application 1 to be able to search the javadocs that I generate from the source in the jar files. In application 2, I would love to have the content of the links searchable (so that people can find which PDFs contain information about blocking), but I'd settle for just being able to search the title that was given to the link.

For ratings/reviews I would like to have a 5-star rating system and comments. However, I'd settle for just the comments. I want people to say which papers they found readable or which jar files they found useful.

There are a lot of features you could add such as an RSS feed, etc..., but I'm willing to ignore all of that for right now. I just need the basics.

Am I asking for too much? Why doesn't this already exist? In the world of CPAN, reddit, etc... why doesn't a generic version of long tail software exist? Perhaps I'm just overlooking it. If not, I guess I'll just have to write it, but I'd much rather use something already written.

Let me know if I missed something!

19th Century Reading Habits in Australia

Here is a blog post describing data mining of 19th Century reading habits in Australia.

It is a fascinating application of PCA and clustering.

I don't think it will be long before commercial databases include standard data mining abilities such as feature selection, PCA, LSA, regressions, k-means, SVM, etc... The blog poster above had to use a combination of things, including the great R, to prep his data for the analysis; this should all be done inside a database. Perhaps this is the straw that broke SQL's back? Perhaps that is where a language such as Pig is needed? Pig's niche could very well be in prepping data for data mining tasks and streaming them through a map-reduce library such as mahout.

Regardless, business users are already there: companies like Harrah's, CitiBank, and Nationwide live and die by their analysis. Now, we just have to build the tools to let them bring new products up quickly and effortlessly. We are on the forefront of a huge explosion in statistical tools, modeling techniques, and machine learning. As much as the internet helped in providing ubiquitous access to data, these tools and techniques will help computers learn and understand us and our preferences. The internet revolution will appear to be a tiny blip on the screen compared to the wonders that are to come.

The Future of Enterprise

What is the future of enterprise software? Is it JRuby on Rails? What about Scala? Maybe a .NET stack? What is the next big shift?

In my opinion, the next big shift is to grid computing. Things like EC2, Hadoop, and HBase will become more and more popular. Commercial versions and vendors will spring up over the next few years. Enterprises will start pushing more and more of their computation into batch grid work. Column store databases will replace traditional RDBMS's for data warehousing (this is already happening with Teradata). Transactional applications will work on cached stores that are pulled from a large grid where they were processed and analyzed. Marketing will be on demand, but pre-computed.

In the rush to understand and market to the consumer, more and more companies have been moving to real-time analytics. However, the faster you need a decision, the less time you have to think about it. That is why grid computing will be so important. Your think time has to be done in advance. Transactional queries will be relegated to closing deals or finding a pre-computed offer.

The main challenge, as I see it, will be to find and use data structures that can be refreshed quickly. Google is in a fortunate position. They can refresh boxes asynchronously. If customer A enters query Q1 and then enters query Q2 it is ok if those two queries hit different data sets and return different results. However, if we're not dealing with a search application but instead something akin to a customer recognition or record linkage application, then the same person should always receive the same link. This is why versioning will become so important in the future. The customer will get a certain version of the data sets and will continue to use that version until their application finishes at which point they can be upgraded. This requires more server side storage, but allows the client the ability to use a consistent data set. This type of versioning and auto-update software will be necessary in a commercial form. In addition, quick nearest-neighbor searches will need to be commercialized. Clients will want to know quickly which market segment a client falls into. Nearest neighbor searches are the key to understanding that and they will need to be generalized and distributed over the next few years.

So, the enterprise is changing. The relational database will move from its position of dominance to just another tool. The grid will take its place as a hammer looking for nails, and applications that can process terabytes of data quickly will be deemed must haves for enterprise data centers across the world. The Enterprise Service Bus (ESB) will continue to shuffle transactional data around, but the backend will now be distributed data stores that will be versioned and querable by categorized nearest neighbor searches. Who will be the vendor of these tools? I have no idea. Many, like Hadoop, will be open source. Some, like Teradata, already exist. Others will be proprietary and don't even exist currently. Regardless, it will be a lot of fun and I'm looking forward to the ride.

Including other jars in your hadoop job jar

I learned that you can include other jars in your hadoop job jar by placing them in the lib/ directory under your job jar. Very nice and convenient!

Now, if I can only make the DistributedCache work. Right now, it just isn't.

ICWSM '08 Lectures online

I've not seen videolectures.net, but I got tipped off that they have the presentations from the 2008 International Conference of Weblogs and Social Media from The data mining blog.

Record Linkage Papers

I have created a site where I am putting up links to record linkage papers. I hope to include comments on them soon. If you have a paper you'd like put on the site, just leave me a comment.

Min-Hash signature for bigrams

I don't believe there is a decent description of how to create a min-hash signature for bigrams on the web, so I'm going to try and provide one. Of course, my description will probably be flawed, but I hope that it will be better than what is out there currently.

First, what is a min-hash signature?

The idea is that, given two records, you can provide signatures such that the similarity of the signatures is approximately equal to the similarity of the records.

Here is a slide show based around using min-hash signature to provide keys for indexing into a database. Here is the relevant paper.

So, basically it is a way of generating a fuzzy key such that if the two keys match there is a high probability that the two records will match.

We're going to examine a way of doing this using bigrams.

Let's assume we have the local part of an email address. In our base file, we have the following entries:

tgibbs
tanton_gibbs
bbarker
tkieth
bspears

If we look at the bigrams generated for each local part, we have the following:
tgibbs = { tg, gi, ib, bb, bs }
tanton_gibbs = {ta, an, nt, to, on, n_, _g, gi, ib, bb, bs}
gbarker = {gb, ba, ar, rk, ke, er}
tkisth = {tk, ki, is, et, th}
bspears = {bs, sp, pe, ea, ar, rs}

If we order all the bigrams alphabetically, then we have the following universe of bigrams: {an, ba, bb, bs, ... th}

Now, a min hash signature requires an input f that tells how many hash functions to use. Let's set f to 3. That means we'll hash each record in 3 different ways.

To generate a hash function, we randomly permute the bigram universe.

So, our first permutation may look like:

{tk, ib, an, pe, ... rs}

our second permutation may look like:

{rk, gi, bs, th, ... pe}

and our third permutation may look like:

{bb, ba, er, ke, ... an}

Now, the next thing we need is a similarity threshold, t. Let's assume t is 0.8.
So, for each record, we will use 80% of the bigrams to produce the hash.

So, if our input record is tgbbis, then we have the following bigrams to choose from
{tg, gb, bb, bi, is} We would choose 3 or 4 bigrams (probably both) to produce the hash. But, which 3 or 4 do we choose?

For each permutation of our bigram universe that we produced above, we will pick the bigrams that appear the earliest. So, for permutation 1, we might end up choosing {gb, bi, is}. For permutation 2, we might end up with {bi, tg, bb}. For permutation 3, we might have {bb, is, gb}. We would do the same thing for combinations of 4 bigrams.

Now, we can create a string from the bigrams {gbbiis, bitgbb, bbisgb}. These strings become our prospecting keys. We perform the same key generation routine on the base records. Then we can join our input keys to our base record keys to find our match candidates.

If we want a more approximate min-hash signature, we could sort the bigrams before creating the key so that we would have the keys {bigbis, bbbitg, bbgbis}. Obviously, the duplicate key could be thrown away. This has the effect of handling more transpositions in the input at the cost of bringing back more candidates.

Hopefully this illuminates min-hash signatures a bit more so that the references above make sense.

pig.properties

If you are going to set up pig, you need to be aware of the pig.properties file.

It has things like the cluster setting, which is important to set correctly. It also has things like whether or not to run it locally or remotely.

See this thread on the Pig mailing list for how to set the cluster setting:

Pig redux

I rewrote my original pig script to use a local foreach block.

It now looks like:

A = load 'myInputFile' using PigStorage(',') as (seqid, cl, local, domain, fn, ln, zip, email);
B = foreach A generate flatten(SortChars(local)) as sorted_local, cl;
C = GROUP B by sorted_local PARALLEL 10;
D = FOREACH C {
CLS = B.cl;
DCLS = DISTINCT CLS;
GENERATE group, COUNT(DCLS) as clCount;
}
E = FILTER D by clCount > 1;
F = FOREACH E GENERATE group;
store F into 'myDir' using PigStorage();

A, B, and C are the same as before. However, we now push the distinct into the FOREACH loop for D. This allows Pig to use a DistinctBag to dedup the CLs for a sorted_local part. Before, the DISTINCT had to use a separate map-reduce step; however, now it can do it all in only one map-reduce job. This effectively halves the time the script takes.

For more on how things get executed, you can use the explain option. For instance, explain F; will show how F gets executed. More information can also be found on the pig wiki.

Pig continued

Now that I have the sorted local parts of an email address, I want to know which emails are identified by those sorted local parts. So, I know that bbgist has more than one CL associated with it. Now, I want to know that tgibbs and tgbbis both go to bbgist. Also, I only want those emails with more than one CL, so I don't want tgobbs because it (let's pretend) only associated with one CL.

Here is the pig script to do that:

register /home/tgibbs/pig/pig/myPigFunctions.jar
A = load 'myFile' using PigStorage(',') as (seqid, cl, local, domain, fn, ln, email);
B = load 'mySortedLocalFile' using PigStorage() as (sorted_local);
C = foreach A generate local;
D = DISTINCT C PARALLEL 10;
E = FOREACH D generate local, flatten(SortChars(local)) as sorted_local;
F = JOIN E by sorted_local, B by sorted_local PARALLEL 10;
G = FOREACH F generate local;
store G into '/user/tgibbs/eproducts-local-merged-out' using PigStorage();

On line 1, once again, I register my SortChars function that is in my jar file.
Line 2 loads the original email file.
Line 3 loads the file of sorted local parts that I created last blog entry.
Line 4 reduces the original email file down to just the local part.
Line 5 (the D line) gets rid of any duplicate local parts, since I don't care that tgibbs appears 10 times and it reduces the amount of data I have to deal with later.
Line 6 (the E line) generates the sorted version of the local part and keeps the original local part as well.
Line 7 (F) joins the two files by the sorted local portion. It's schema looks something like (E::local, sorted_local, sorted_local).
As an example, it would have (tgibbs, bbgist, bbgist) and (tgbbis, bbgist, bbgist).
Line 8 (G) just gets the local part, which is what I want to store and the last line stores it.

Next up, I plan to try out the Illustrate command which should display the execution plan.

Mahout

Just a quick post to point out Mahout. Mahout is a machine learning library built on top of Hadoop. They are still fairly pre-alpha, but they already have some interesting algorithms developed. I plan on trying out their canopy clustering algorithm relatively soon.

On a second note, I've gotten Pig up and running and have successfully run some large jobs. Woot!

Here is a pig script to count the number of AbiliTec Consumer Links associated with the sorted local part of an email address.

In other words, if there were two emails tgibbs@blah.com and tgbbis@blah.com, the sorted local part of both would be bbgist. If they were each associated with a different consumer link, then the following pig script would output bbgist. Otherwise, it would not.

register /home/tgibbs/pig/pig/myPigFunctions.jar
A = LOAD '/user/tgibbs/eproducts' USING PigStorage(',') AS (seqid, cl, local, domain, fn, ln, zip, email);
B = FOREACH A GENERATE FLATTEN(SortChars(local)) as sorted_local, cl;
BDIST = DISTINCT B PARALLEL 10;
C = GROUP BDIST BY sorted_local PARALLEL 10;
D = FILTER C BY COUNT(BDIST.cl) > 1;
E = FOREACH D GENERATE group;
STORE E INTO '/user/tgibbs/eproducts-sorted-local-out' USING PigStorage();

The register line loads a custom jar file so that I can call my custom functions. More on that later.

The next line, the assignment of A, just reads a comma delimited file into A. It also associates a name with each of the comma delimited fields. So, field 0 is seqid, field 1 is cl, etc...

The third line loops through each record in A (that's the FOREACH) and sorts the characters in the local part. I wrote the SortChars class and will post that at the end of this entry. The FLATTEN is needed because SortChars returns a tuple and since I only have one element going in, there is only one element coming out and I want to treat that one element as an atomic data item instead of as a tuple . The 'as sorted_local' portion renames the data item.

The type of B is now a tuple (sorted_local, cl).

The next line eliminates duplicates. So, if two records have the same sorted local part AND cl, then we can safely erase the duplicate because it will not affect our final count. In fact, we'll need to eliminate it for the rest of our logic to work. The PARALLEL keyword ups the number of reduces. This means we'll end up with 10 output files instead of 1, but that's ok because we'll process them all later, anyway.

In the end BDIST has the same type as B (sorted_local, cl).

The line that aliases C groups BDIST by its sorted_local part. This basically creates one record for each distinct sorted_local part. The value is a data bag that contains one BDIST record for each distinct sorted local part.

So, C now has the type (group, BDIST:{sorted_local, cl}).

The D line gets rid of any groups that have only one cl. D has the same type as C.

The E line gets only the groups, ignoring the actual values. And the store line writes those groups out. So, now I have one group for every sorted local part that has more than one CL. How cool is that!

Here is my PigFunction for sorting the characters:

import org.apache.pig.data.Tuple;
import org.apache.pig.data.DataBag;
import org.apache.pig.EvalFunc;
import java.util.Arrays;
import java.io.IOException;

public class SortChars extends EvalFunc {
@Override
public void exec(Tuple input, Tuple output) throws IOException {
String str = input.getAtomField(0).strval();
byte[] bytes = str.getBytes();
Arrays.sort(bytes);
str = new String(bytes);
Tuple newOut = new Tuple(str);
output.copyFrom(newOut);
}
}

Pig

Pig is Yahoo!'s data flow language that is designed to run atop hadoop. I've spent a few hours today getting it set up and running. One thing I would like to point out is that you can't run the pig script in the bin directory (or at least not and connect to the hadoop cluster).

I had to manually run:
java -cp pig.jar:$HADOOPSITECONFIG org.apache.pig.Main

Also, if you dump a variable, it has to run the map phases to get to it. I thought it would just tell the schema, but no....

Hadoop Streaming

Hadoop Streaming appears to be a way to write quick hadoop jobs. I've recently been playing with it and have finally gotten it to work for me.

The main parameter that I had to add was -jobconf stream.shipped.hadoopstreaming=$HADOOP_HOME/contrib/streaming

It was somehow getting set to /tmp which was causing everything in my /tmp directory to get added to the job jar it generates.

Another good thing to keep in mind is the -verbose flag. It can help figure out what is going on under the hood.

Multi-User Hadoop

I've been setting up hadoop on a few (6) boxes and have been attempting to make it work for multiple users. It is not as easy as it sounds because the docs are a bit spread out.

Nevertheless, if everyone is in the same group, then you need to set your default group to represent that.


dfs.permissions.supergroup
groupname


You'll also need to change the group of any files you've already created.
hadoop dfs chgrp -R groupname /

Next, to allow multiple users to run mapreduce jobs, you'll need to set your configuration directory to be a place that is accessible to ALL the boxes. I'm using an nfs mount, but you could use hdfs just as easily.


mapred.system.dir
/mnt/myNFSMount/hadoop/mapred/system


Make sure that directory exists and is writable by the group mentioned above (or at least that all your mapreduce users can write to it).

At this point, that is all that I know needs to be changed. I have two people (including myself) using our hadoop cluster. So, I'll let you know as we run into more problems.

Linear Algebra

A great undergraduate linear algebra class from MIT's Open Courseware program can be found here.

Other MIT Open Courseware courses with heavy video/audio content can be found here.

You Tube Videos

Google Tech Talks has a number of great video lectures on You Tube. I thought I would share some that I found interesting.

First, there is a 13 part series on statistical aspects of data mining. The presenter is giving the class at Stanford and decides to also give the class for fellow Googlers. He is a very good instructor and takes people through an introduction of how to use statistics in data mining. This is definitely required watching.

Second, Andrew McCallum has a lecture on enabling object search instead of page search. Basically, his work is in entity resolution and graph approaches.

More to come...

Toyota

I couldn't agree more

Don't measure against rivals.

It seems like companies, when they develop a new product, just try to emulate what is already available in the market. Unfortunately, it takes 3 to 5 years to create a mature product. What is currently available is somewhere in that 3 to 5 year span. If you attempt to emulate that, you will also take 3 to 5 years. However, by that time, the market will have moved on. You will always be reactionary and you will always be behind the competition.