Thoughts of Me

A new language

2010-03-28T23:25:00.000-07:00

Why, oh why, would I curse the world with another programming language? The answer is my typical, "Why not?". More seriously, there are minor deficiencies that I would like to address in the modern mainstream languages. The language I will design will be an incremental improvement over what we currently have. I don't expect it to gain much traction, but it should be enjoyable to program in and it will make for a nice side project.

Here are the major things I wish to have in my language
1. Type inferencing
2. Mutable/Immutable variables - you should be able to specify if a variable is mutable or immutable. By default, local variables are mutable. Non local variables (member variables and static variables) are by default immutable.
3. Non-nullable types - By default all types are non-nullable. You can wrap the type in a Nullable<T> and use the Nullable<T>.Null object to represent null.
4. Generic types - types can be generic.
5. "Duck" interfaces - types can be cast to an interface that they don't implement so long as they implement the correct functions. It must be an explicit cast (unless the interface is unnamed), but the cast will succeed.
6. Unnamed interfaces - When defining a generic function, you can specify an interface that the parameter must implement. The incoming object will be implicitly cast to this unnamed interface.
For example:
int f<T implements { void foo(); }>(T incoming)
{
incoming.foo();
}
7. immutable methods - methods are, by default, immutable. They can not change any of the mutable or immutable members. A method may be specified as mutable, but mutable methods may not be called on immutable objects.
8. Metaprogramming support - Compile time support for metaprogramming should come from a few different sources. First, a standard AST will be provided that can be manipulated through annotation. Basically, an annotation is like a macro that takes a statement and transforms the AST into a different statement. For example, you could write a "memoize" functional annotation that accepts a function declaration and replaces it with a different declaration that is memoized. In addition, metaprogramming can come through compiler event hooks such as "onInheritance", "onCast", "onDeclaration", etc...
9. Unit test support - I'm not yet sure what this will end up looking like, but I do plan on having the ability to write short, inline unit tests at the point of method declaration. It will act as both a user guide as well as a documented test.
10. No "new" keyword - I have never understood the point of the "new" keyword in Java and C#. Therefore, it is gone.
11. No more try - I really hate the try/catch thing. In The Design and Evolution of C++, Bjarne writes about how he had a version without try, but it was confusing. I think it is time to resurrect his experiments. I'm not yet sure of the final form, but I'm sure it will be tryless.
12. Inheritance is deprecated - Other than interfacing with other languages, there should be no need or desire for inheritance. Much of what it was designed to accomplish can be done better through syntax macros and composition. Inheritance will be kept for compatibility with Java/C#/etc..., but its use in native libraries will be deprecated.

Ok, that's 12 things that I see for my language. I don't have a name for it yet, but will accept any suggestions :) I plan to target the .net runtime at first, but the JVM should be a target as well. Comments are welcome.

Passing the Microsoft Interview

2010-03-19T03:05:00.000-07:00

As you know, I work for Microsoft - specifically on the bing.com team, more specifically on the core core relevance team (yes, that's two cores...don't ask). Even more specifically on the anchor team in the core core relevance team of bing.com in Microsoft. Wow, that's a mouthful.

Anyway, bing is hiring and that means I'm interviewing a lot these days. I'm doing at least one interview every other week, sometimes more. In addition, not many people are passing. So, to help everyone out, I thought I would put together a list of tips to help you pass the Microsoft Interview.

Tip #1: Know your stuff

Yeah, easier said than done. However, there are a number of resources out there that can help you. I've listed them in a previous blog post, so study up and have a good understanding of data structures, algorithms, and Big O notation before getting here.

Tip #2: Understand the problem

A lot of people encourage you to ask lots of clarifying questions. I think that is good practice and would also encourage you to do it. In addition, I think you should also spend quite a bit of time at the beginning to list out examples, both positive and negative.
Let's use a concrete example. One question that I see posted all over the web is to write a function to take a string as input and reverse the order of the words in the string. So, for example, "Hello World" would get reversed to "World Hello".
The first thing you should do is ask clarifying questions. Here are some examples:
1) Should I reverse the string in place, or create a new string?
2) What is the return value for the empty string?
3) How should a null pointer be handled?
4) What constitutes a word separator?
5) ASCII or Unicode?
6) How should punctuation at the end of the string be handled?
7) What about capitalization?
8) Is it a c style string or are embedded nulls allowed?

Now that you have fleshed out the problem, the next thing to do is think of some example inputs and see what the outputs would be. I would think of this in a tabular format with input on the left and output on the right

input	output
null	assertion failure
""	""
"Hello"	"Hello"
"Hello world"	"world Hello"
"Hello from Microsoft"	"Microsoft from Hello"

There may be more examples depending on the answer to the clarifying questions, but these would be the minimum examples necessary. Go through each example with your interviewer and make sure he or she agrees with your mapping function.

Tip #3: Describe the algorithm

After you have created your examples, but before you start to code, describe, in English, the algorithm you have devised. First, this helps you to think about the algorithm before you code it and second it gives your interviewer a chance to hint at the right solution if you missed it. If, instead, you immediately start coding a poorly performing algorithm, you give your interviewer no choice but to sit idly by while you waste his time coding something he knows won't work. If you, instead, discuss the algorithm with the interviewer, it gives him or her the chance to point you in the right direction and lets you write code that the interviewer wants to see.

In our word reversal example, you might start by describing an algorithm whereby you find the first space and the last space and then swap the words and repeat until the spaces are the same. The interviewer might ask you about the complexity of this approach and then ask if there is a less expensive algorithm. Doing things in this order makes sure that you are coding the algorithm the interviewer wants to see.

Tip #4: Don't mention a naive algorithm to fill time

The interviewer has asked you a difficult question. You're not sure of the correct way to solve it. Don't just mention the first, most naive, solution that pops into your head. If you think your first solution is a good one, then by all means mention it, but if you know it sucks and is O(n!) or some such nonsense, then stop, think, and come up with something better. By giving a poor solution to begin with you are just giving the interviewer a reason to reject you. You don't have to get the right solution to begin with, just make sure it's not horrible.

Tip #5: When coding, make sure you check your boundary conditions

Nothing sets me off more than when someone forgets a null check or a boundary condition check. This is just Engineering 101 and is critical for a system such as bing. If you can't be bothered to check for null in all the right situations, then don't even apply. Sure, everyone makes mistakes, but in the interview keep null checks on the top of your mind.

Tip #6: After coding, run through your examples and make sure your code works

I've seen too many people write code on the whiteboard, spend 5 seconds looking at it, and then say "Yes, that looks good." There is NO way you have tested it in your head after 5 seconds. Even if it is correct, how do you know? The best thing to do is to use your examples that you generated to walk through your code. You might discover, for instance, that you assumed there would always be a space, when there might not. This gives you a chance to correct your own mistakes without forcing the interviewer to intervene.

Tip #7: Ask questions about the interviewer

This is just good psychology. Make the interviewer feel important by spending a few minutes at the end asking about the interviewer's team and work. The benefit to you is that you get to hear about the day to day activities and make sure they sound interesting. The benefit to the interviewer is that he or she gets to talk about his or her exciting projects. This leaves the interviewer with a good feeling leaving the interview, which is always a good thing. So, the next time you are stuck without a question, ask the interviewer to tell you about a recent project - and hopefully it excites you both!

There you have it, 7 tips on getting through a Microsoft interview. Of course, I honed in on coding, but many of the same ideas apply to the design based interview questions, as well. Regardless, be prepared, be confident, and most of all, have fun!

What have we programmers learned?

2010-02-12T00:32:00.000-08:00

Remember when everyone wrote spaghetti code littered with gotos? Ok, I don't, and I doubt there was such a time. The really great people never wrote spaghetti code littered with gotos. They used gotos because they were all that was available, but they wrote structured code before structured code was cool. It took time, and language advances, but eventually the average joe programmer like me caught on to the practice. This led to much rejoicing and greatly improved software. Of course, by that time, the great programmers were already moving on to things like object-oriented programming and generic programming. There is always a downdraft from the great programmers exploring and pioneering to the average joe learning and improving the mean.

The questions were are here to ask (and answer) are
1) What has the average joe programmer learned over the last 10 years?
and
2) What are the great programmers exploring and pioneering today?

It is interesting to note that most of the things I'm going to discuss were practiced since the beginning of the computer era. They are not new ideas or inventions, it is just that it has taken this long for the rest of us to catch up and realize their significance and importance.

In this post, I'll list out what I believe we have learned and are learning and in future posts, we'll go into each in more depth.

What have we learned over the last 10 years?

1) Automated unit testing - Note, this doesn't necessarily mean TDD, BDD or any other methodology, just that we should have unit tests and they should be run automatically.
2) Refactoring
3) Small methods
4) Value Semantics - How can I say this when most VMs use references? Think immutable reference types!
5) Functional extensions to procedural languages
6) VMs are good
7) OO is not a silver bullet
8) ORM is hard
9) IDEs are vital
10) XML was a cruel joke

What are we learning?

In most of these cases, we know the concept is important, but we're still quite unsure of how to quite integrate it into our everyday lives. There are still many fledgling attempts, but nothing has quite been standardized. In some cases, it could be that web search has clouded my view of what is importat.

1) Non-nullable types
2) DSLs
3) Metaprogramming is important
4) MapReduce [or parallelism is all about the programming model]
5) Statistics
6) Column-Store DBs have a place, but so do RDBMS's
7) Convention vs Specification
8) Patterns are not a silver bullet, nor are functional languages
9) Type inferencing is a benefit
10) XML was a cruel joke (yes, it goes in both)

Please feel free to comment if you disagree or want to add.

My new browser

2010-01-06T08:15:00.000-08:00

For years I have been a faithful IE user. I say faithful and not loyal because I have only used it because it suited my needs and other browsers were too cumbersome or clumsy to hold my attention for long.

FireFox is infinitely customizable, but it never felt like a well designed app - it felt clumsy to me. Plus, it always had problems rendering tables in an appropriate manner.

Chrome is sleek, fast and elegant, but in many cases it just doesn't work. I'm always finding some site that it doesn't render quite right, a video that it won't play, or a simple customization that doesn't exist.

I've also tried Safari from time to time, but never long enough because I never saw any advantages over IE.

However, a new version of an old browser has impressed me so much that I have switched for what I hope is good. Opera version 10.10 is an amazing piece of art. It renders fast and correctly, plays all the video sites I need (though I did have to "Mask as FireFox" for Netflix!), and has the simple customizations I want. For instance, I can use the address bar to search on various search engines (I'm not limited to Google like I am with Chrome.) If I want to search Bing, then I just type "b " followed by the search string into the address bar and viola! it goes to Bing and searches (I did have to manually set this up, but it was quick and easy). Other niceties include movable tabs for web pages with hover preview and a "speed dial" page that is much nicer and more customizable than Chrome's.

My requirements are simple. I want a browser that is easy to use, works on the sites I frequent, and has simple customizations. I don't want to spend a lifetime studying all the intricacies and hunting down new plug ins. I just want a browser that works. Opera satisfies those needs and left me happier than I was before. Give it a try and let me know if you feel the same way!

C# Timings

2009-09-05T21:19:00.000-07:00

Recently, I was adding a bit of debug code to measure how long it took to run various parts of my program (yes, I know a profiler would be more accurate, but I just needed a rough estimate). So, I had 3 or 4 areas in my code where I did something akin to


TimeSpan timer = new TimeSpan();
DateTime startTime = DateTime.Now;
Type1 rval = DoIt(a, b);
timer += DateTime.Now - startTime;

Firstly, this code is ugly. I'm obviously doing many different things here: timing code, calling a function, storing it's result, etc.... It would be much better if I could wrap the timing code into its own function. So, I esentially want something like:


TimeSpam timer = TimeIt( () => DoIt(a, b) );

The code for TimeIt is simple to write


TimeSpan TimeIt(Action a)
{
  DateTime startTime = DateTime.Now;
  a.Invoke();
  return DateTime.Now - startTime;
}

However, that doesn't save the return value of DoIt, so that is useless for my purposes. I need TimeIt to return the value from DoIt. To do this, I make TimeIt a generic method and have it accept a function instead of an action. I pass the TimeSpan in as a reference argument. The calling code looks like


TimeSpan timeSpan = new TimeSpan();
Type1 rValue = TimeIt(() => DoIt(a, b), ref timeSpan);

The TimeIt function looks like


public static T TimeIt(Func f, ref TimeSpan timeSpan)
{
  DateTime startTime = DateTime.Now;
  T rVal = f.Invoke();
  timeSpan += DateTime.Now - startTime;
}

There, now we have a simple and generic way to time a single method that returns a value. If you wanted to go further, you could create a class that held the TimeSpan value so that you wouldn't have to pass it in as a ref, but this worked for my needs and was clean enough so I stopped here. If I need this code again, I'll refactor it into another library and perhaps into its own class. Until then, I'll enjoy the cleanliness and conciseness.

A letter to my representative

2009-07-20T19:09:00.000-07:00

I sent a letter to my representative regarding the health care bill and would like to repost it here for others to comment.

Hello Representative Inslee,

I wanted to write a quick letter in opposition to the upcoming health care reform. Believe it or not, health care is undergoing a major revolution today. The problem is that the traditional "insurance" programs of the past are becoming harder to use because people have confused "insurance" with "comprehensive coverage". Allergy medicine, maintenance meds, etc... are not part of any insurance program. Insurance is responsible for covering major and unexpected medical issues. Over the last 5 years, more insurance companies are coming to terms with this and are inventing things like Health Savings Accounts, which, though unpalatble to many consumers, are a cost effective means of giving consumers choice over how to best spend thier medical allowance. Unfortunately, the private sector has not sorted everything out yet, so now is a very inopportune time for the government to intervene. The government is not innovative nor is it cost effective. Instead, it simply throws constiutents money at a problem with little effect until they stop complaining about it. I do recognize the importance of helping our elderly and needy, but I also recognize the precarious position of the american economy and the health care industry. Despite Obama's claim, now is NOT the time to act. Now is the time to rely on capitalism and market forces to sort out what the future should hold and then fit our current medicare and medicaid plans into that future. The economy, the health care industry, and your constituents need you, Representative Inslee, to be a pillar of salt in today's wax and wane congress. You have been in the past and I trust you will be again.

Thanks for your time,
Tanton Gibbs
Redmond, WA

What should Yahoo! do?

2009-06-28T02:04:00.000-07:00

Yahoo!'s CEO, Carol Bartz, has stated firmly that Yahoo! is not a search company. In fact, Yahoo!, she states, is much closer to a portal. The goal is not search, but editorial comments and a local feel. A portal, if you will, from a major media/technology firm. Unfortunately, in the coming years, portals will be less and less necessary as people will get their news from a swath of algorithmically mined sources across the social media landscape. I'm afraid the era of Yahoo! dominance has ended and will not return.

Like IBM in the 90's, Yahoo! must redefine itself. Yahoo! must sell the mills.

Again, like IBM, who has become a major integrator, and Kimberly-Clark, who has become a consumer goods powerhouse, Yahoo! must set out on the next phase of it's life - it must enter and dominate a new area or be relegated to a technological side show until it dies. But what should it pursue? To answer that question, we need to look at its strengths and products, especially those that are hard to mimic, such as those related to its core technology.

Yahoo! has world class data centers, meaning they can store and process data cheaper than anyone else (except, perhaps, google). Yahoo! also has a data processing platform that allows it to analyze web scale data quickly and efficiently. It's also beginning to build a dataflow language which allows developers to be productive. Finally, Yahoo! has a respected research organization which keeps it at the forefront of areas such as machine learning and information retrieval.

The question then becomes: "What business needs massive computational power, data storage and processing ability, and makes heavy use of machine learning and information retrieval?" The biggest one I can think of is data marketing. Analyzing billions of consumer and business records as quickly as possible and making decisions on the fly is what data marketing is all about.

Imagine a person walking into an electronics store. Currently, if the person buys something he may get a coupon to promote his buying something more, later. However, this is suboptimal for two reasons. The simplest reason is that the coupon may be unnecessary. The patron may have been planning to return even without the coupon and so the coupon represents wasted revenue. The second reason is that the coupon may be too late. It could be that if the patron would have been given the coupon on the way in then he might have bought more or upgraded or any other number of things that could have produced more revenue. It could even be that a customer doesn't buy anything at all, but would have purchased if a coupon was given beforehand. The holy grail of marketing is to sell an item to each person at an individualized cost. You want that person to pay as much as possible for the item. If person A will pay $100 for a camera and person B will pay $300 for the same camera then you want to issue the $200 off coupon to person A and no coupon to person B.

Now, imagine a system where a customer is recognized by an image recognition system the moment they walk in. Their data is retrieved instantly and a machine learning algorithm is run to determine what the person is shopping for and what the person is willing to pay. From their online profile and twitter account, the algorithm is able to determine that the person recently broke their camera and is looking to replace one. Using data from a company such as this one the algorithm can tell that they are struggling economically and will want to buy a cheaper camera. However, it also knows from statistics that a coupon for the higher priced camera has a good probability to make the consumer stretch his budget and go for the "prestige" item. A few more checks against the data center reveals that the current store location has excess inventory of the higher priced camera and therefore the algorithm decides to dispatch a bigger discount coupon for the better model. The sales attendant walks to the customer and presents the coupon, escorting the customer to the camera aisle. The sale is made and the computer gets an extra volt in its bedtime snack ;-)

More seriously, Yahoo! could perform those computations more efficiently and with better accuracy than an enterprise. Enterprise data centers are not going to reach the efficiency of Yahoo!'s data center. Moreover, enterprise IT programmers are not going to have the time or penchant to do the necessary IR and ML research. Yahoo! is uniquely positioned to do those things; furthermore, since it is dangling on the precipice of disaster now is a good time to bite the bullet and make the change. Not that I expect them to. Change is something that is hard to accept and Ms Bartz doesn't seem like the type to change their core business...if she ever figures out what that is. More than likely the model I express above will be adopted by a new comer...perhaps by these guys.

The Perils of Fanaticism

2009-05-24T13:01:00.000-07:00

I found this article on reddit the other day and was immediately struck by its stupidity. Now, usually I wouldn't use such a harsh word, but the ideas contained in it are so preposterous that it doesn't really deserve any better word.

I first want to say that I have no opinion about the book described or the author of the book. I have not read the book and I don't know the author. For all I know, After the Software Wars could be about bunny slippers. Instead, I want to be very clear that I'm arguing only with the points contained in the article.

The article describes how open source produces superior software to a closed source model and uses, as its first example, Wikipedia. It mentions that Wikipedia is not software, but uses it as an example anyway. Seriously. I can't deny that no closed source institution can provide the same quality of data as Wikipedia. However, Wikipedia deals with data, not code, and data entry can be done by anyone. It is very different from a program that requires someone know how to program before they change it.

Next, the article uses two examples to prove that open source software is better than closed source: FireFox and the Linux kernel (over IE and Windows). Wow, this is the height of arrogance and a circular argument. There is no demonstrable way to prove their superiority; I doubt even 4 out of 5 dentists would agree that one is better than the other.

The next part of the article that I find incredulous is that he believes that Google Docs will never catch on, while Linux and OpenOffice will. Yeah, sure. People are going to avoid using something that doesn't take any effort to change to, makes your data available everywhere, and is constantly updated versus something requiring a complete modification of your current computing environment, has to be shared separately, and is updated using magic incantations. While this may sound like I'm a Linux newbie, I'm not. I'm just pointing out the fact that, to most people, yum is something you say before dinner, not the way to update your programs.

The MOST ignorant thing, however, was the following: "If Microsoft, 20 years ago, built Windows in an open way, Linux wouldn't exist, and millions of programmers would be improving it rather than competing with it."

Yeah, right. We don't have various flavors of Linux. We don't have emacs and Xemacs. We don't have hundreds of open source projects that do the same thing in slightly different ways. Come ON! Competition is in our blood. Doing things "our way" is what makes programmers unique. You could have the most awesome open source project on the planet and someone would find a reason to fork and change it. That's just how we work. The idea that everyone will give up their belongings, join a commune, and hum "Linux is king" is not realistic. Just look how many open source programming languages there are. Look how many open source unix-like variants there are. Get a grip on reality and stop pontificating your idiotic ideals.

Ok, next quote. "The biggest difference between Windows and Linux is that free software contains thousands of applications, installable with one click, and managed as one set." First off, I'm not sure what that means. I have never seen a Linux application that was installable with one click. I definitely prefer the Windows model of installation to the Linux model. In addition, the Windows and Linux model of uninstallation is similar, IMO, so I'm not sure what it means to be "managed as one set", nor how that differs from Windows. As for thousands of applications, that is true, but Windows also has a number of free applications and that seems to be growing as the .NET platform usage increases.

The idea that software developers around the world will just give up the idea of profits and join together in harmony is ridiculous. Furthermore, proprietary software has benefits. You can judge the financial soundness of a company to see whether their software will be around in 10, 15, or 20 years. Just look at sourceforge to see the number of free software projects that are abandoned.

I believe strongly in the value of free software and open source software (and I even know the difference). However, I also believe strongly in the value of proprietary software. For a case study in what happens when you are the champion of free software, just look at Sun. Oh, you can't, it's been bought by Oracle, a closed source shop. Yeah, Microsoft should really follow in their footsteps. Sheesh.

Yahoo! Interview

2009-02-23T19:42:00.001-08:00

I realize this write up is a bit late, seeing that I already work for Microsoft, but I wanted my interview collection to be complete, so I want to add this one and the interview with Google. Realize, that it has been six or so months since I interviewed with Yahoo!, so my memory has faded a bit. However, I'll go over what I remember.

After my interview with Google, I didn't think I would interview with Yahoo! because it was in the same area of the country - an area I was not impressed with. However, a friend of mine, who works for Yahoo! talked me into interviewing. He said that he could show me around so that I would enjoy the area. I wasn't convinced of that, but at the least it was a free trip to see an old friend, so I decided to take him up on it. In hindsight, I'm very glad I did. First, because getting the Yahoo! offer allowed me to get other offers, but, more importantly, because my friend would passed away in December of last year and it was to be the last time I saw him.

My friend, Nathan, submitted my resume to two groups in Yahoo! The group that contacted me was the Pig group. This was fortunate, because I had just begun using Pig and Hadoop at work. I had also begun interacting with the Pig group through their mailing list. Therefore, I was familiar with the product and could talk about it in our very first call.

I was actually impressed with the phone screenings for Pig. We talked about things relevant to the product, such as how to handle large memory footprints with Java and various join algorithms for large data sets. We also discussed some more trivial things such as some of the differences between C++ and Java and what a virtual function is. I actually got confused at this point and described how compilers typically implemented a virtual function instead of what they did, but we eventually sorted things out.

After the first phone interview, I was fairly confident that things went well. This was mostly due to the fact that the interviewer told me that things went well :) She was the only phone screener to be that blunt. The next phone screener discussed process with me. We talked about TDD, documentation, program management and other things similar to that. It went well and they invited me to Silicon Valley to interview in person.

In retrospect, the best part about going to the Yahoo! interview was getting to see Nathan again. It was the last time I was to see him before the motorcycle accident that led to his death. He took me around the coast and we picked up some strawberries and cherries at a roadside stand. He also took me for a "backstage" view of the Yahoo! scene. It appeared rather normal, other than the guy who had a mini-bar in his cube.

Back to the interview. Like the Amazon interview, all of the Yahoo! interviews took place in the same room. The interviews varied in style, some were more puzzling (how do you find a loop in a linked list), some were more practical (tell everything you would do to design a highly available high throughput web server).

Throughout the interview, I felt I needed far too many hints. I think I did well on the design portions, but the algorithm sections were my weak point. I ended up getting the answers, but hints were necessary. Toward the end, I was just being self-deprecating. I remember one question they asked about how many people I had recommended for hiring (not many about 3) and how many I had interviewed (lots). I made the comment that for my previous company we didn't get Stanford grads and I qualified it by saying that not even I could be a Stanford grad, I just wasn't that good. This interview plus the Google interview plus Microsoft interviews from years before had beaten me down. I was now completely convinced I was useless.

In the end, though, I came away with the impression that the people were very intelligent and would have been great to work with. They talked about the "architect" path that I could take so that I didn't have to become a "people manager" (which sounded good). They seemed to have a great company and it would have been loads of fun. However, I didn't expect an offer.

Surprisingly, they called not too long after the interview with an offer. By this time, I had an interview scheduled with Amazon.com and so I asked to make my decision after that point.

As you know, I didn't choose to go to Yahoo!, but that interview and offer gave me the confidence going into the Amazon.com and Microsoft interviews. Had I not gone to the Yahoo! interview I don't know how I would have done in the other interviews. I know I would not have been as confident and that could have prevented me from getting the position I have now. For that, I'm thankful to both Yahoo! and Nathan.

Thanks Nathan, I'll miss you, prophet!

Short-sightedness

2009-01-27T21:29:00.000-08:00

A friend of mine sent me this blog post on why google web drive won't kill windows or anything else. To be honest, I'm surprised by the author's short-sightedness.

First, Scott mentions DropBox as a pre-existing replacement for GDrive. He then points out that Google plans to tie the GDrive in to Google Docs and that DropBox doesn't currently have that functionality. However, he doesn't see that as a game changer. What he doesn't comprehend is that Google has more than just Google Docs. Google has Gmail, Calendar, YouTube, Blogger, and an ever growing number of other sites. They also have an operating system (Android). So, you'll be able to turn on your netbook and have it sync your email, documents, favorite shows and blogs, etc... immediately from the cloud. Don't think that will happen? GMail is already offering an offline syncing mechanism through Gears through GMail Labs How much longer before they expand the syncing mechansim to work with other things like Google Docs, YouTube, etc... Google has consistently been able to deliver on big ideas and this one is one of the biggest.

Scott also mentions the trust issue. Who wants Google to store their most personal documents? I think this will become less of an issue over time. Already people are using services such as carbonite to back thier computer up online. How much different is it to trust an encrypted Google cloud? I think this issue will stay a hot topic for a few years, but in 4 or 5 years when everyone is using the cloud more and more it will become a non-issue except for the most sensitive documents. Google is already heavily advertising its security features.

Another issue is downtime. What happens when the cloud goes offline? Once again, I think this will be less of an issue over time as the cloud becomes more stable. Even now, how often does GMail go down? I think my internet provider goes down more often than GMail does. Moreover, I can't get much done without an internet connection anyway, so offline availability doesn't really help me out much. I think the more Google convinces people that the cloud technology is stable the more they will flock to it and use it. After all there are many benefits to cloud technology such as redundency, multi-computer availability, etc...

Scott is right in saying that there are currently alternatives in DropBox and Windows Live Sync, but only Windows Live Sync has the capability of rivaling GDrive. Microsoft has services in its hotmail mail service and its online office suite. They will have to continue to integrate those into the cloud to keep up with Google. Not only that, but if they could integrate their next XBox platform into the cloud so that you could store your games on the cloud (or just download them directly from the cloud) then that would be a big plus and something that Google can't currently rival. Having a home media system synced to Microsoft's cloud could promote using the Microsoft cloud for other things such as mail and documents.

I certainly believe in Microsoft's ability to beat back the Google threat, but I'm not narrow minded enough to think that GDrive is not a threat. It is the backbone of the internet operating system that Google is building to take on Microsoft.

The Google Threat

2009-01-26T23:47:00.001-08:00

Disclaimer: I work for Microsoft on their Live Search product. In no way is what I'm blogging about representative of the actual views of Microsoft. I'm much too low level to have any input or insight into Microsoft's thought process.

I see a lot of people on various message boards comment on how Microsoft should stop funding Live Search and Online Services. Many people say that Microsoft should just focus on what they do best (developer tools, operating systems, and office) and ignore this whole "Internet Thing (TM)". Microsoft loses millions of dollars a year competing with the Google Behemouth with very little to show for it in terms of market share. Why not just cut your losses, spin off the division, and let it die a horrible death?

I'll tell you why. Google is Microsoft's biggest threat. Google threatens Microsoft's operating system dominance, their developer tools dominance, and their office dominance. If this were the Civil War, Google would be the North. They are the ones competing on Microsoft's home turf. They are trying to burn Atlanta, and some would say they are succeeding. As a Microsoft employee, I am not at all scared of Apple. They will continue to tinker with their iPhone and Macs and a few hardcore Apple fans will always be there to keep them going. Don't get me wrong, I think the iPhone is a huge improvement. I own one. I like it (but don't love it). However, Apple isn't making inroads into Microsoft's core. Objective C is not the Visual Studio killer and OS X won't kill Windows. Apple wants to produce the "perfect system". And that's fine. They'll end up creating something very beautiful that will be mimiced by others, but it will take them years to do so and they'll do so single mindedly. They won't be diverse enough to kill the Microsoft behemouth. Google, on the other hand, is thinking big. They have a plan that goes after all of Microsoft's core competencies and they are taking the fight to MS.

Let's look at a few examples:

1. Office vs Google Apps for Business - Take a look at a number of business that are evaluating or have switched to Google Apps for Business. Now a few things have to be said. Many of these companies are using Google Aps in addition to MS Office. They are using Office for thier internal communications and confidential emails and Google Aps for less sensitive material. For now, that is the best they can do. In addition, many of the companies are switching from other systems such as sendmail, so that's not a direct gain against MS. Nevertheless, how long is it before Google provides encrypted email and a guarantee of privacy? How long before they win a big MS client and other companies start looking at the cheaper Gmail system with reduced administrative costs? This is an obvious attack and one that is gaining momentum.

2. Visual Studio vs Google Web Toolkit - This is a bit of a misclassification. Really, Google Web Toolkit is more of an attack on Microsoft's Azure Platform than on Visual Studio itself. However, Visual Studio is included in the assault. With Eclipse, Google Web Toolkit, and many libraries such as jUnit, Guice, etc... Google has teamed up with the Open Source community to take on MS. Google wants developers to develop on its "platform" just like Microsfot wants developers to develop on its "platform". That is why Microsoft developed Silverlight. Silverlight allows developers to take their .NET familiarity and transfer it to the browser. This keeps people in the Microsoft environment. Google takes the same approach. They want people to use its services, so they provide the Google Web Toolkit to keep people in their environment. It's also a good testing ground for larger conquests, providing computing power and frameworks for the enterprise. Once developers become comfortable with the Google environment, it will be an easy transition to open up their cloud to businesses and allow them to develop and deploy on it.

3. Windows vs Android - Shouldn't this be Windows Mobile vs Android? No, definitley not. Android is a direct attack on Windows and the desktop. Already many people are speculating that Android will be released on netbooks soon.

See Android notebook coming early next year?, Android netbooks? Wouldn't it be lovely, and Android netbook is a possibility. Google will use their operating system to keep your information and applications in the cloud and you will be able to access them from any computer, especially your Android netbook. You'll log in and immediately see your desktop with your applications that are stored on the cloud. When you click on an application, it will download and begin running immediately (though many applications will still work through the web, like GMail, blogger, etc...). Netbooks are already taking a chunk out of Microsoft's sales and having Google's name on it will only increase sales. Also see this article on how Netbooks sales are killing Microsoft.

I haven't tried to paint bleak picture on purpose. Instead, I was trying to show that Google is taking the battle to Microsoft and Microsoft must respond. Search, in particular Live Search is a key component to that. But, it is not the only component. Windows 7 and Azure are other key components. In the future, people's computers will live on the cloud. Search will go beyond finding web pages. Instead, you'll perform searches for applications that will fit with your current settings. You might even rebuild your OS components in the cloud specifically to fit your library versions. You'll search for a song and not only get an mp3, but also a list of movies that you own that have that song in them. You might, if your search options are set correctly, even get a list of similar songs, or songs you played before or after that song. Search is the backbone of the next generation computer and the next generation HCI. Google, I believe, backed into this and is now expanding it to its inevitable conclusion. Microsoft realized it after the fact and is rushing to catch up. Regardless, we need competition and I believe that Microsoft has the resources and the dedication to provide that competition.

Needless to say, the things I outlined above are not going to happen overnight, but Google is taking a long term view. So is Microsoft. Google is using their advertising revenue to subsidize their desktop pursuits. Microsoft is using their desktop revenue to subsidize thier advertising pursuits. Both are in it for the long haul. It will take years for Google to implement some of the things I discussed above. I expect 8-10 years will pass before all of our data and programs live in the cloud. I expect another 10 years will pass before most businesses data and programs live in the cloud. Both companies will be here after that time has passed, which company will be the dominant one? I have no idea, but it will be exciting to find out!

Browser Toolbars

2009-01-10T16:45:00.000-08:00

Recently, Microsoft announced a deal with Dell to distribute the MSN toolbar with new computer purchases. This comes after previous announcements with Sun and Lenovo. While I am excited about the traffic this will bring to Live Search, I have to say that I hate browser toolbars. Seriously, what good are they? Most browsers already have the functinality that the toolbar provides: search box, term highlighting, etc... The MSN Toolbar does provide a few interesting twists like automatically launching Live Messenger, but on the whole, who needs them? They just use up space and memory. My wife's computer has both the Yahoo! toolbar and the Google toolbar on it. I have to go take them both off now...

You know, what I'd really like is a browser that prohibits toolbars, that I could use. And while I'm on that topic, over Christmas I installed extra RAM in my father-in-laws computer because it was going slow (it only had 256 MB of RAM). I also noticed that he hadn't upgraded from IE 6 and had some Yahoo! toolbar that provided virtual tabs of some sort. Why hadn't the browser updated itself to IE7? Seriously, why doesn't our software just fix itself? Why don't my drivers automatically update? ARRRGGG!!!!

Ok, I feel better.

New Layout

2009-01-09T22:52:00.000-08:00

As you can tell, I picked a new layout from blogger. Let me know what you think.

Rules for running an IT organization

2009-01-08T07:01:00.000-08:00

The last post was how to run a research organization. In this post, I'm going to set my sights even higher and tell how to run an IT organization. These rules have been picked through my studies of various companies.

1. Hire the best people - I've harped on this before. So have others and others and still others. If you don't know by now that there is at least a 10x difference between the top programmers and everyone else then you haven't been paying attention. I can't say much on this topic that hasn't already been written, but I will point out that you need to be proactive about hiring the right people. It's not just the free food. It's about providing employees with incentives to do great work. If you just need a warm body, then provide him with a steady paycheck. But if you work in IT, you don't want warm bodies, they are not in the 10x group. You want the best, so you have to make it worth it. You have to make them feel important and wanted. You have to put effort into finding them at the top colleges, recruting them, and retaining them. If you are a small company, you can provide stock options. A large company? You can provide free food :-) Either way, you have to provide challenging problems, a sense of ownership, and other fantastic people to work with. Remember, if you have ten of the 10x group that is equivalent to one-hundred of everyone else. If you don't think that is true because of parallelism, etc... you are wrong. Parallelism doesn't apply because the communication pathways increase leading to lower overall productivity. Just like you don't get a linear increase with most parallel algorithms, the same applies for programmers. The communication overhead gets in the way. Therefore, with ten 10x programmers you can be more productive than with one-hundred other programmers. And you don't even have to pay them 10x as much, though you will have to pay some extra. With the savings, you can provide more stock options or free food :-)

2. Make the source available to all - Everyone in the company should have access to all the source code. At Google, the designers of the library can easily update it, because they can open everyone else's code up in eclipse, choose refactor, and then save and recommit it. They are not blocked. In addition, an open code base implies group accountability. Too often, programmers get too attached to their work. They don't see the flaws that are inevitable in their programs. An open code base allows everyone to view and comment on everyone else's work. It forces programmers to realize that they are mortal and make mistakes. Eventually, they will come to know that the group is better than the individual and their work improves due to peer review. Forcing an open code base allows this to happen sooner and with more acceptance.

3. Dedication to infrastructure - Who is responsible for the build system? Who writes the core infrastructure components? Who sets up the distributed computing system? Who determines which dependency injection framework should be used? All of these are core infrastructure decisions and they all matter. As we'll see in a future bullet point, standardizing the infrastructure is vital. You want your application programmers to focus on their individual application. If every application programmer has to focus on their infrastructure, then you are losing 3 to 6 months out of every project. If it takes a week to set up an automated build system and a week to attach the test harness and another week to set up the distributed key/value store, then you have lost 3 weeks of your project to things that have to occur for nearly every project! Instead, you want application programmers to think about their application. You want them to worry about delighting their customers. They need an automated build system, but they shouldn't have to think about which one to use, how to set it up, or what happens when it isn't working. That is infrastructure. In the past, there were extra teams responsible for hardware, networking, and OS setup. These were not the responsibility of programmers. Now, we're adding additional layers. The build system, test framework, and distributed computing platform are additional infrastructure components that must be standardized and managed elsewhere. There could be additional infrastructure components for your organization as well. For instance, Google uses dependency injection so often that they wrote their own framework for it. Notice that I didn't say every team wrote their own framework. Instead, one team wrote it and maintains it and everyone else uses it. This consistency and willingness to use other people's work makes for a successful company. As another example, Google has a Java collections library that the company uses. Every team can take advantage of this without having to rewrite it. In other words, the goal of the infrastructure group is to find and eliminate duplication throughout the company. This could be with hardware, applications, or libraries. Regardless, duplication is the enemy of the IT organization and it must be eliminated!

4. Repeatability - Everything that is put into production must be a repeatable process. Not only that, but it must be repeatable by someone else! This means both applications and documentation must be written and available that show how to repeat it. Once again, we're trying to seek out and eliminate duplication. Programmers in the future shouldn't have to reverse engineer or re-create your application. If it is worth putting into production, then it is worth documenting and ensuring repeatability.

5. Enforcing standards - You want programmers to feel empowered, but you also want productivity. You need standards to ensure the latter, but you need only the right standards to ensure the former. Standardizing on one build system (perhaps per language) ensures that everyone can access and build everyone else's code. Standardizing on a common base class ensures pandamonium. You want to standardize tools, not techniques. Not only does this allow programmers to quickly move from one project to the next, but it also provides continual feedback and improvement on your internal tools. When a programmer says, "Tool X doesn't provide capability Y so I'll write my own" you are in for disaster. Now, every project begins with a 3 week tool writing cycle. Instead, if the programmer would just fix Tool X then everyone else can take advantage of capability Y. Libraries work the same way. Pick a dependency injection library and use it across the organization. It doesn't matter if one team happens to like Spring over Guice. They are both open source and you can alter it to suit your needs. Just pick one and be consistent. Get everyone moving in the same direction. That way, when they increase others' velocity they move in that direction even faster.

6. Don't start from scratch - If nothing exists, then you have to start from scratch. However, if you have a working product, then don't start rewriting it from scratch. The only thing you do is create new bugs that you don't know about instead of fixing the old ones you already knew about. Now, that doesn't mean that you shouldn't take a troublesome component and rewrite it. That doesn't even mean that over the course of a year you don't eventually rewrite 90% of the application. It does mean that you work piecemeal, with legacy code. You create tests, if you don't have them. You write documents, if you don't have them. You continually improve the product you have. Then, when you are ready, you begin refactoring. You improve its structure a little bit at a time. Just enough to add your new functionality with new tests. Then a little more and a little more. Eventually, your crufty working system blossoms into a beautiful piece of artwork. Well, you'll think so anyway, but the next developer won't understand why you did X, Y, and Z and he'll want to rewrite it from scratch. That's the problem and the point. When we don't understand how something works, we want to rewrite it so that we do. However, the next maintainner doesn't understand it either, so the rewrite circle continues and is vicious. If something works, use it, clean it, modify it. Don't rewrite it.

7. Be dedicated to testing - The best organizations have dedicated testers. This is not a coincidence. Recognizing quality as a core attribute of a product is vital to having a quality product. Manufacturing companies have known this forever. Why is it that IT shops think they can ignore quality and still have a quality product? Google's Chrome has unit tests for highly ranked web pages, automated UI testing, and random input testing. Not only that, but they also ran other test suites against it. For instance, it passes 99% of webkit's layout tests and passes all but 2 of jQuery's unit tests. Quality is a core attribute. At Microsoft, there is a Software Development in Test job role. Each team is assigned one or more of these resources to ensure they deliver a quality product. These people are top notch programmers that love to break things. They are not random guys off the street. They can code just as well as the SDE's and it is vital that they can do so. Testing today is about coding. It is about double entry bookkeeping. It is about automation and repeatability. People expect thier products to work, out of the box. They expect future releases to be backwards compatible. They expect a quality product. To delivery that, quality must be a feature. The organization must be dedicated to quality - having a special testing division is one way to commit to that level of dedication.

8. Metrics - "In God we trust, all others bring data." Metrics are at the core of process improvement. How can you possibly know if you are improving if you don't measure that improvement? Would you be satisfied with your water treatment plant if it told you the water quality was improving because it looked a bit clearer? No. You'd want to know the Ph levels, the amount of sediment in the water, etc... You expect a quality product to have metrics that back up its quality. If speed is a feature, then you'd expect metrics around how fast the product will go in certain conditions. If accuracy is a feature, then you'd expect benchmarks showing the accuracy against other products or human judges. In all cases, metrics are vital to a product in order to show improvement and achievement of goals. The one caveat is to be sure you are measuring the right thing. It is inevitable that programmers will find a way to improve the metrics. If the metrics are measuring the right thing, then that is great. If the metrics are measuring the wrong thing, say lines of code, then you have a recipe for disaster. Make sure that your metrics are measuring externally visible things, not internal ones. You want improvements to your metrics to affect the customer, not your programmer's salary. Everyone cheats the system, you want those cheats to have a positive impact on your final product.

Well, there you have it. 8 rules for running an IT organization. Hopefully they will make your company the next IT powerhouse!

Applied Research

2009-01-06T22:44:00.000-08:00

At one point in my career, I had the experience of being on an applied research team. In fact, I was one of its founding members. At the time, I wasn't sure what applied research was; even now, I can't say for sure I know.

For our team, applied research was new product development. Honestly, I think that had disastrous effects. We were in limbo between delivering a new product and maintaining our "research" mantra. In the end, we wanted product teams to adopt and maintain our product. This, too, led to tension. Product teams want to feel comfortable with what they will eventually own. They want to use and support things they have used and supported in the past. Research products are wild-cards and not to be used unless nothing else like it exists. Even then, most product teams will choose to rewrite it. Take, for instance, Pig. Pig is a dataflow language created by Yahoo! Research to run on Hadoop. It was created to prove a point, but it was also created to be used. However, once it transfered to a product team in Yahoo!, it was scheduled for rewrite. I'm not sure the cause. It could be Not Invented Here syndrome. It could be that research teams are not focused on the long term, so they deliver a short term product. It could be that research teams don't know how to code or that product teams and research teams speak a different language, so they can't see eye to eye. Regardless, having a research team deliver to a product team is doomed to failure, if you count failure as an eventual rewrite of the product or technology.

To help guide my thoughts on this matter, I had the good fortune to speak to Hector Garcia-Molina of Stanford University. If you don't know who this guy is, you are missing out. Stop and go read the wikipedia entry linked to above. He recounted to me his description of what a research organization should do. I'll recount here and embelish a little.

First, a research organization should publish. The benefit of publishing is that it brings notariety/publicity to your organization. The company's sales force can go to battle with slides that reference conference proceedings. Of course, no sales person would read the proceedings, but it does make their presentation look legit. In addition, presenting at conferences allows the researches to make the aquantence of people like Dr. Garcia-Molina and bring new insight and innovations back. Finally, publishing creates an attractive employment environment. New graduates from top schools want to go to a place that has a publishing history so that they can continue their research. To get a graduate of MIT or Stanford, you need a publication record. I'll add one more to his list. I think a research department that publishes shows a commitment to innovation by the company; a commitment that roots itself in the culture and makes the company a hotbed of innovation.

Second, a research organization can be used as a SWAT force. Tackling a hard problem or subset of the problem. I think this can be the area where the most "good" can be done internally. Instead of creating a product, create an extension to an existing product. There are always "next version" features that never get created. These features either provide too little value or are too difficult. It is that latter segment where the research department can really shine. Since they are not constrained by time to market, etc..., the research department can think outside the box and take the time to create an "academic" solution. For example, PageRank was an academic solution to the problem of which web sites were more popular. It is a beautiful recursive algorithm that just happens to produce great results. Is it a perfect algorithm? No, of course not. Was it better than the "engineering" algorithms of the time? You betcha! It was what happened when two academics got together and had the time to think about the problem. They realized the probelm was similar to that of research paper citations, so they devised an algorithm that treated the problem thusly. Had they had to meet an arbitrary deadline so that their employer could make the trade show deadline, they would not have come up with PageRank. That is the benefit of a research team. Not to create some fancy product for the trade show, but to take the existing product the next step. To finish out the "next version" features and do so elegantly.

The final task for a research organization is to benefit the company at large. There are many ways to do this. One is to create best practices and spread them out to the other development teams. Another is to investigate various technologies and report on how they could/should be used throughout the company. An additional way could be to create the infrastructure to ensure developer productivity if no other team is responsible for it. Do developers have access to distributed key/value stores? If not, install MemcacheDB or CouchDB, and help developers to connect to it by creating modules in various languages. Do developers understand and have access to technologies like Hadoop and Pig? If not, create demos and give a roadshow. All of these things lay in the "best practices" umbrella and often organizations don't have the teams in place to create and distribute the "know-how" required to use them.

In all three cases, the applied research team stayed away from the product team's core product. Instead, the research team focuses on small, manageable pieces that fit nicely into the strategy already outlined by the product team. This creates trust and will foster future collaborations between the product and research teams.

Good luck and let me know of your experiences dealing with research teams!

Gay Boyfriend

2009-01-03T15:50:00.000-08:00

I'm not sure which one I like the best

dorky fan version
dorky house version

Ouch

2009-01-03T13:34:00.000-08:00

I hope not

Facebook lament

2009-01-01T19:30:00.001-08:00

I have too many facebook friends. I lament it. I only have about 5 that I actually want to monitor and communicate with; however, when people request friendship I don't want to say 'no, I care nothing for you.' I really want a "preferred facebook" view where I can just track and interact with those I care to. One would think that it is not that big of a deal, but it really is. For instance, I just went to superpoke a friend of mine and it took far too long because I had to find that person in my list of friends (and I don't have *that* many). It actually reduces the amount of time I spend on facebook.

Less is more.

Infinities and Series

2009-01-01T17:51:00.000-08:00

Those of you who read this blog (all 1 of you!) know that the number of integers is infinite and the number of irrational numbers is infinite, but the latter infinity is greater than the former infinity. I tend to think of this as mathematical shenanigans. The idea that one infinity is larger than another just doesn't meet the "beauty" test that accompanies mathematics. In the past, I've argued that infinities don't exist, so we can make contradicting remarks about them to our hearts content. It's similar to asking the question "Can God make a rock so big even he can't lift it?" The words make sense and are in the right order, but the semantics of the sentence are off. They produce a barber paradox that belongs to the realm of meaninglessness. They show that Goedel is alive and well and relevant for today's meta-mathematical problems, if only we'd heed his words. Ok, back to infinities.

First, can we create a more intuitive reason for why one infinity might be greater than the other, a reason that doesn't fall back on establishing a one-to-one correspondence with the integers?

First, let's establish that the integers exist in one-dimensional space. In fact, they exist on a number line which is the definition of one-dimensional space :-) But, let's consider a slightly different definition of dimensionality. In this definition, we'll look at the number of infinite dimensions. In the case of integers, the length of the integer is finite. No matter how big the integer becomes, there is always a finite number of digits. Even if the integer explodes to a googolplex digits, there is still a finite number of them. Therefore, the only infinity is in how many integers there are, the size of the actual integer is finite. So, there is only one dimension of infinity.

Let's now look at rational numbers. In the case of rational numbers you might say that there are two dimensions of infinities. The first dimension is the number of rational numbers. There are an infinite number of rational numbers. The second dimension is that some rational numbers have an infinite decimal expansion. For example, 1/3 has an infinite expansion of 0.333333333... Therefore, rational numbers have two dimensions of infinity and should be larger than integral numbers, right? Not so fast. That's just their decimal expansion. If you keep them in their functional form, then we get a different story. All rational numbers can be expressed as the division of two integers. Moreover, we know that both integers have a finite number of digits. Finally, we know that adding two integers with a finite number of digits will produce a third integer with a finite number of digits. Therefore, there is a representation that is finite in length for every rational number. That leads to the logical conclusion that all rational numbers have one dimension of infinity.

Next up, irrational numbers. Irrational numbers extend to positive and negative infinity, giving one dimension of infinity. In addition, they have an infinite expansion in every base, which gives them a second dimension of infinity. So, we can easily see why there are more irrational numbers than rational numbers, because we allow irrational numbers to have an infinite expansion!

So, if we can't represent irrational numbers with a fixed number of rational numbers, what can we represent them with? Why, an infinite number of rational numbers, of course! For example, PI can be represented by the following series (one of many): PI = 4 * (SUM[k=0 to inf] (-1^k)/(2k+1))

So, in essence, we have an infinite set of numbers each composed of an infinite set of numbers. Two dimensions of infinity!

But wait! If we can create a series to represent each irrational number, does that mean that there exists a representation that is not infinite and therefore we can count them, similar to the rational numbers above? No. With rational numbers there was a finite number of integers that created the rational number. With irrational numbers there is an infinite number of rational numbers.

So, it is true that the number of irrational numbers exceeds the number of rational numbers, right? Well, maybe. I think it is fair to say that an infinitely expanded irrational number doesn't exist, so we're back to the land of Goedel. It is worth thinking of an irrational number as a function of an infinite number of rational numbers much the same as a rational number is a function (division) of two integers. Functions are often useful in mathematical manipulations, but that doesn't make them "real". The number 3 is a physical, real number. You can count out 3 things. The number PI is not a physical, real number. We can only approximate it. In fact, complex analysis is based around the number i, which is a function (sqrt) applied to -1. As long as we don't expand the function, we can do mathematics with it, but if we ever need to expand it our equations blow up. The same thing is true with irrational numbers, they are mathematical niceties. Abstractions that we can manipulate as long as we don't look too closely. Similarly, questions about abstractions such as if one abstraction is infinitely larger than another abstraction requires you to look to closely, so you get crazy results, just like if you had really taken the sqrt of -1 or divided by infinity (another function).

So, the next time you see PI, take it for what it is, a function that can be evaluated to the necessary precision. A mathematical abstraction that can be admired from afar. Just don't get too close.

North vs South

2008-12-30T18:40:00.000-08:00

I've been in the Pacific Northwest for four months now and I thought I'd share a few of the differences I've noticed.

In the South, we have sweet tea. In fact, we have most any fattening item you can imagine: gravy, lard, fatback, etc... In the Northwest, everyone drinks their tea unsweetened and even IHOP lists the number of calories in their food.

In the South, you drive everywhere. If you take the bus or walk you are most likely poor and almost always frowned upon. In the Northwest, you are hailed as a hero and considered "green".

In the South, PTA was for the crazies who had nothing better to do with their money. In the Northwest, our PTA paticipation is at 100% for the third year straight.

In the South, the kids look forward to deer season. In the Northwest, the kids look forward to the new Star Trek movie.

In the South, teachers send letters home with the children. In the Northwest, teachers email the parents

In the South, we get our coffee from McDonalds. In the Northwest, the city would shut down if Starbucks closed.

In the South, the biggest technical gathering is when Ma Potter drops the security on her wireless router. In the Northwest, you are constantly bombarded with invites to technical events.

In the South, a top IT graduate comes from Vanderbilt. In the Northwest, a mediocre hire comes from Berkeley.

In the South, the churches are dense, huge and filled with Southerners. In the Northwest, the churches are sparse, huge and filled with former Southerners.

I'll pause here and reflect on a few things. First, with regards to schools, it is easy to find a correlation between money spent and quality. The schools in the Northwest are better funded. Heck, my daughter's school here has a buffet! However, those people who feel that spending more on education will fix it have missed the boat. The real issue is parental involvement and peer pressure. In our schools the children challenge each other and the parents are involved. At our PTA social events nearly everyone is there. We, and the children, want each other to succeed. No amount of money will make kids want to have a read-in instead of play outside. No amount of money will make kids come to school dressed as their favorite storybook character instead of their favorite pop-star. No amount of money will make kids succeed. It takes dedicated parents. Moreover, it takes a school full of dedicated parents. Otherwise, you will run into the problems faced by other behavioral economists. The smart kid with dedicated parents will be ostracized. He or she will be considered an outcast. After all, they aren't going to be staying around after graduation, so why invest your friendship in them? You need an entire school full of dedicated children and dedicated parents in order to succeed. Money won't help, changing the culture is required.

Secondly, you can see the failure of the church in the Northwest. The educated, affluent people avoid the church while the Southerners flock to it. I think there are a number of factors at play here. First, the larger churches are getting the publicity and they are taking a stance against education. I have personally been in a church where the pastor said that anyone who believed in the Big Bang is going to hell. I didn't go back to that church. However, if a church accepts everyone and everything then there is no point in going. You can socialize on the net. So, there is no middle ground. The educated people are turned off from the backwards southern denominations and have no reason to attend the more "progressive"/"liberal" variants. If higher education becomes the norm in the South (which is a big question mark), then the church as we know it is doomed. The church must find its way in a new era. It must bridge what we know to be true, scientifically, with what we believe to be true, spiritually. It must exclude certain things as immoral, even though it accepts them civically. For instance, homosexuality is banned in the Bible. However, so is adultery. No churchmember protests the legality of adultery; hell, half of them have committed it themselves. But homosexuality is an abomination! The same goes with other moral sins such as lying and blaspheming. The church needs to realize that it does NOT have a civic duty to outlaw immoral behavior. No one can legislate morality and those that do are seen as haughty and hippocritical. Instead, they should accept that the world's morality and the church's morality are different. Christians are "sanctified". Before Christianity, to sanctify something was simply to set it apart; there was no religious meaning. If the church gets to legislate everything, then there is no more sanctification; we are just like everyone else and that is not our mandate. We are to work in the world and change the people. That can only be done by example. Right now, we're not setting a good example. It won't be long until the church is completely irrelevant outside a few poor areas where their only role is to give the poor hope.

In total, I've really enjoyed living in the North. I have no idea if I'll stay here long term, but it's been a great experience so far and I'm glad I was given the opportunity.

C# Awesomeness

2008-11-23T03:35:00.000-08:00

As you can imagine, my current employer gives me a number of opportunities to work in C#. I've really been enjoying myself, but only scratching the surface of what C# was capable of. So, tonight, I tried a few more interesting ideas that use the C# anonymous types and lambda function capabilities.

The first one is a pretty simple copy of ruby's IO.each_line function. My goal is to have the C# function encapsulate the logic of opening and closing the file and me pass in a lambda that does the processing I want (just like Ruby's).

Here's the code


1    public delegate void IOProcessor<T>(T line);
2    public static void ForEachLine(string fileName, IOProcessor<string> processor)
3    {
4        using (StreamReader reader = new StreamReader(fileName, Encoding.UTF8))
5        {
6            while (!reader.EndOfStream)
7            {
8                processor(reader.ReadLine());
9            }
10       }
11   }

First, I declare a delegate. In C or C++, it would be a function pointer. Here, it is more than that because it can be generic, which is utter coolness in a box. We'll see the point of the genericity in a moment.

The next line declares my function which takes the file name and the delegate (we will be giving it a lambda.) Here, we explicitly set the generic parameter to a string because we know that is what we are retrieving from the file.

The using statement opens the file, specifying a UTF-8 encoding. It will also ensure the file is closed whether or not an exception occurs.

Finally, we have a loop that reads each line and passes it to the delegate until we run out of lines. Very simple and straightforward.

If we wanted to use this code to sum up the lines in a file we could write code like the following.


1    int sum = 0;
2    
3    ForEachLine("my_integers.txt", (line) => { sum += int.Parse(line); });

After line 3 finishes, sum contains the sum of each line in the file.
For instance, if the file was
10
20
30
40
Then sum would be 100.

Another thing I do a lot of is handle delimited files. Usually, I'll open one up, perform a line by line manipulation of the file, and close it back. Of course, the obvious string.Split() method comes to mind, but that is somewhat unsatisfactory because you are still dealing with integer offsets into an array. How do I know that offset 3 is the anchor text and offset 7 is the ubercool feature? It would be nice, if I could specify their names in the beginning and then work with objects.

So, to handle that, I created a function that would objectify my delimited files.

Here goes:


1    public static IEnumerable<T> EachDelimitedLine<T>(
2           string fileName, char delimiter, T outputObject)
3    {
4        Type outputType = outputObject.GetType();
5        using (StreamReader reader = new StreamReader(fileName, Encoding.UTF8))
6        {
7            while (!reader.EndOfStream)
8            {
9                string[] fields = reader.ReadLine().Split(delimiter);
10               yield return (T) Activator.CreateInstance(outputType, fields);
11           }
12       }
13   }

I'll break this function down line by line in the next blog. Specifically, it takes in a prototype object called outputObject and creates an object like that from each line of the delimited file, using the strings after splitting to initialize the object. I call this function like


1    foreach(var x in 
2       EachDelimitedLine("delimitedFile.txt", ',', 
3                         new { Title = "", Body = "", Anchor = "" }) 
4    {
5       if (x.Title == "Thoughts of Me")
6       {
7         // do something with my blog...
8       }
9    }

As you can see, I specify a prototype object of an anonymous type and my code uses that prototype to create objects from the delimited file. Of course, in production code you would want checks for too few fields or too many fields so that you don't get the weird error messages you would get from this code by default. However, I think it gives you a flavor of the power of C#.

Now, for the final piece, we combine the ideas of the ForEachLine function and the EachDelimitedLine function to get a ForEachDelimitedLine Function. This also shows you the power of the generic delegate.


1    public static void ForEachDelimitedLine<T>(
2        string fileName, char delimter, T outputObject, IOProcessor processor)
3    {
4        foreach (var x in EachDelimitedLine(fileName, delimter, outputObject))
5        {
6            processor(x);
7        }
8    }

In this case, the IOProcessor now accepts a generic argument T which is the same type as the prototype object I pass in (called outputObject).

Let's look at the above example code redone to use the ForEachDelimitedLine function


1    ForEachDelimitedLine(
2        "delimitedFile.txt", ',', new { Title = "", Body = "", Anchor = "" }, (x) =>
3    {
4      if (x.Title == "Thoughts of Me")
5      {
6        // do something with my blog...
7      }
8    }

There, no more foreach statement. Now, the logic is part of the function itself.

Next, I plan to extend my C# emacs mode to generate a class around my static functions and compile and run for me so I can have a C#-script of sorts. Don't get me wrong, I still love and use perl on a daily basis, but C# is often much faster than perl, surprisingly enough, and seems to be able to handle memory more efficiently as well. However, I do admit that is anecdotal and not based on any tests I have performed. On a more pragmatic side, it is easier to integrate with exsiting C# libraries from C# rather than writing a SWIG interface.

Hope you enjoyed!

disgruntled iPhone user

2008-11-22T22:38:00.000-08:00

I'm tired of the Apple iPhone. As long as you don't need to do anything unusual, it is fine, but try to go outside what the folks at Apple have deemed appropriate for you and it blows up. For example, if you want to sync with two computers, you are hosed. If you want to make a different interface (for example, I want playlists to have folders), you are hosed. If you want to do anything custom, you are up a creek - I'm tired of it. When my contract expires, I will be moving to a different phone. No more Apple for me, I want something more open.

Midomi

2008-11-22T22:35:00.000-08:00

Just a quick post to give props to the Midomi team. I always enjoyed Shazam, but it only works for commercially recorded songs. Midomi lets you sing and then tries to determine what song you were singing. It is great karaoke fun! My wife and I played a game of Horse with it recently and had a blast.

Great job, guys!

The end of broadcast TV

2008-09-01T23:22:00.001-07:00

Seems like broadcast TV should be in its death throws. I give it no more than 7 years. I imagine within 5 everyone else will chime in with its death. I wonder how Dish/Comcast/DirectTV/etc... will fight back. Will they try to lure the RIAA into banning places like hulu.com? Or will they hold out hope that people will want to see their shows as soon as possible instead of waiting for them to come online? At what point do they stop coming out in broadcast form first? Seriously, between netflix, hulu, veoh, and mtv.com I don't really need cable. I have enough entertainment with just those sites. That doesn't even include iTunes and the paid providers. The tail is growing in this area and it will only be a few more years before it becomes mainstream. Not only that, but the monitization ability is already there through commercials, so it is a viable model. I do hope it doesn't get bogged down by commercials though - and I hope the commercials become personalized. Just because I'm watching The Hills doesn't mean I want to see a cosmetics commercial...however, my eyebrows do look a bit...nevermind.

What a great family

2008-08-24T09:15:00.000-07:00

I received these pictures from my wife and kids when I arrived in Seattle. They are a great family and I miss them. From left to right is my niece Ashlan, my daughter Brooklyn, and my son Carter. See you soon!

Amazon Interview

2008-08-13T22:51:00.001-07:00

I went through my interview with Microsoft in my previous blog entry. In this entry I plan to discuss my Amazon interview. I applied to Amazon after having visited the Silicon Valley area. I knew that I didn't want to work in that area and hoped the Seattle area would be nicer. Amazon gets tons of traffic daily and I'd been very impressed with their S3 and EC2 technologies, which I discuss here. I wanted to work at internet scale and Amazon seemed to be a prosperous and growing company.

I received an email from an Amazon recruiter not too long after submitting my resume. She described the process: two phone screens where I would have to write code over the phone and then they would fly me to Seattle. I had just come off my interviews with Google and Yahoo, so I was excited to have another opportunity ahead of me.

For my first phone screen, I was out of town, so I had to do it in my car. They mentioned I would have to write code and I shouldn't be driving. I had pulled over in a parking lot and was ready with pencil and paper when the call came. I had also turned off my car and it was about 100 degrees F outside; it was definitely uncomfortable. In this first interview, he asked me to write a binary search function for an integer array. Normally I don't describe the questions that are asked; however, in this case I don't think I'm giving away any big secrets.

I wrote a recursive binary search implementation and read it back to him over the phone. It was a bit odd to read code over the phone. I had to read out curly braces, square brackets, the whole works! When I finished reading it he asked me if line X was ok. I told him that I thought it needed a +1 to it. He said ok and then asked me why I chose a recursive implementation. I told him that I thought it would be easier to write. I tend to think recursively. He asked me what the downsides of a recursive implementation are. I told him that it requires time to push on and off the stack. I also mentioned something about stack overflow, but in hindsight that was a bit silly. The greatest stack depth you can ever have for a binary search is 32 (on a 32 bit machine). I also mentioned that a tail call optimizer would eliminate the performance penalty. I'm not sure he understood that, so I didn't pursue it. Besides, I don't know of any C++ compilers that include tail-call optimizations.

We had plenty of time left, so he asked me to rewrite it iteratively. I complied and started writing it. In the middle of writing it, I realized I screwed up the recursive version. I told him about my screw up over the phone and called myself an idiot. We both got a laugh out of that. I finished my iterative implementation, double checked it for accuracy, and read it to him over the phone. He seemed happy with that approach and I mentioned that it was easier to write than the recursive version. However, I imagine that is because I had calmed down some and the recursive version had prepped me. He asked me about some of the test cases I would run on it. I mentioned as many as I could such as element not in the array, element at each end of the array, element in the middle of the array, duplicate elements, etc... He seemed satisfied and began telling me about their team and projects. In the end he asked me if I had any questions. I only had one or two about the team and working conditions. I'm not a huge questioner, I guess.

Honestly, at that point I wasn't sure I'd be getting a call back. I had flubbed the recursive version of a binary sort for goodness sake. I mean, come on, who does that? I should have nailed that one. I was a bit disappointed. (On a side note, there is a really great article on binary search in Beautiful Code. If you don't have that book, you really should.) Since my phone screen was on a Thursday evening I had to wait until the next week to hear my results. The recruiter called and told me that they were interested in talking to me further and they would like to set up another phone screen. I was excited to be moving on to the next round!

The next interviewer also asked me a fairly basic programming question. It is one that I ask a lot in interviews and therefore quickly pounded out the optimal solution. In this case, it seemed to take him a few minutes to verify that it worked. I was a bit surprised - I figured if you asked a question you should know the optimal answer for it. It could be that he was testing me to see if I would rush to change anything, but I was confident in my answer. He seemed pleased and we moved on to talking about other things. After this interview, I was pretty confident that I would be getting to go to Seattle and after a few days, the recruiter called to confirm it.

There were a few negatives about the trip to Seattle with regards to Amazon. First, the put you in a hotel downtown, which means that you are within walking distance to everything. That's not a negative. However, they don't imagine you need a rental car, so they don't provide one. Instead, they reimburse you for taxis. Now, I appreciate being reimbursed, but it is a lot of trouble. I have to find the cash to pay the taxis, get receipts, keep the receipts, turn them in, and wait 6 weeks for the money. Honestly, it's just not worth it. Secondly, the hotel they put me in didn't have free in room internet. I wasn't going to pay $10 a day to get it, either. They did have free internet in the lobby, so I would go down there, download an Ars Digita Video Lecture and go back to the room to watch it. I will say that the staff at the hotel was very courteous and the restaurant was great, but not having in-room internet sucks. Big time.

Amazon flew me in a day before the interview, so the first day I was there I went and walked around the downtown area. I found it vibrant and clean. I went to a suggested restaurant nearby and had some really amazing food. However, it was getting late and I was tired, so I went back to my room to rest up for the next day.

The next day I awoke and took a taxi to the Amazon building. It was on 5th street South. Either that or 4th Street South. I forget. But the reason I bring it up is because the directions explicitly say that South is different from not South :) In other words, they are on different ends of the town. I'm paranoid that my taxi driver won't know that and keep repeating to him, "South, right? I mean it's a different street or something." We get on 4th Street (or 5th Street...who knows...) and it's not South and I'm repeating again "4th Street South!". Finally, he assures me that he knows where he is going and I should just let him take me there. I sit back, say "ok", and enjoy the ride. We drove by the Seattle Public Library and I am amazed by its architecture. It is truly stunning.

Finally, we arrive at our destination. He lets me out and he pulls off after giving me a blank receipt. For that matter, all the taxi drivers have given me blank receipts. Do I fill in the amount and sign them myself? I have no idea. Anyway, I'm looking around and I don't see an Amazon sign anywhere. I'm freaking out thinking "Oh my gosh, he has taken me to the wrong street!" However, I do see a street sign and it has South on it, so I must be in the right place.

Finally, I see an entryway on the side of the building with "Amazon" on it. I go inside and speak to the receptionist. I'm about 30 minutes early, so she asks me to take a seat. Interestingly enough, as I'm sitting there thumbing through magazines, I find an advertisement for my current company, Acxiom. It had to be the worst advertisement I'd seen. It was a city-scape with a lake and the words "We make information intelligent." What does that even mean? How do I know what Acxiom does from that? I sat there for about 10 minutes coming up with better advertising campaigns. It wasn't hard. Having worked at Acxiom, I am Jack's complete lack of surprise.

A little after the appointed time, my first interviewer came and got me. He didn't say much as he walked me to the room where I would spend the rest of the day. In fact, once we were in the room he immediately asked me to code the solution to a problem. There was no introduction, soft-skills questions, or questions to make you comfortable. It was just an immediate call for action. I did well on the first question, though it took the entire time. The next interviewer had to wait outside the door a bit for us to finish up. The only odd thing was that I still have no idea what the first interviewer's name was or on what team he worked.

The second interviewer was a bit better, I think he told me his name :) However, he once again avoided any comfort questions and went straight to the coding ones. He asked a question that I put to my CS 101 students. I told him that it is a programming assignment that I give them and that it is usually a bit long to write out; however, I hoped I could do a better job than they could. Still, the program just takes time to write and it took up an entire whiteboard by the time we were done. He asked quite a few questions about it and I fixed a few bugs reading back through it. He also asked me how I would test it and I went through the various scenarios. One of those scenarios failed with my current implementation, so we fixed that as well. Then, it was time for the next interviewer.

The next interviewer asked a design question. It was a question that I had some familiarity with it as it included aspects of record linkage. In fact, I explained a few things to him from the leading edge of research that he was not familiar with. We got into a little debate about whether user click-streams could be substituted for a heuristic algorithm, but on the whole it was a good interview.

After that, it was the team's boss's turn to take me out to lunch. Amazon doesn't have a cafeteria (at least they didn't take me to it), so we went across the street to a Thai restaurant. Turns out my interviewer liked the same type of food I did and we ended up ordering the exact same thing. We talked about my experience and work history over lunch and he talked about the team. He mentioned a number of times that it was a production team and I would have to carry a pager. He wanted to make sure I was ok with that. I told him that I was and that I had done support in the past and was fine with it.

When we returned to the office, it was his turn to ask questions. His were more logic/match puzzles. At first, he started by saying "You have an array..." and I thought, "Oh boy, here we go again." Pretty much every company asks the same array question. "You are given an array with N integers. Each integer is in the range of [1,N-1]. Furthermore only one integer is repeated. How can you find the repeated integer?" I got this question and variants of it in 3 of the 4 interviews. I was getting ready to answer it again for Amazon when he threw a curve ball and asked a variant of it that I had never heard. This one was more interesting and actually fun. Now, I don't think that this type of question shows anything about the programmer other than whether or not he's heard the question before. It's kind of like the moving Mt. Fuji questions of old. However, I worked through the question, got the "Aha!" moment, and solved it. I tend to like solving those questions. Even though it didn't say anything about me as a programmer, I had fun with it.

The next interviewer was to assess my C++ and OO design skills. He asked me stock C++ questions, which I answered without difficulty. He then posed a coding question that was really more about interface design than actual coding. I had to do things like make sure my constructor was correct and write operator + in terms of operator+=, etc... I wasn't familiar with the domain (and told him so), but in the end I came up with a solution. He told me that it was the same solution he came up with when he first attempted the problem. However, he had to do it in a production setting, not an interview setting. I felt like coming up with the same solution as my interviewer was a good thing, so I was ok with that.

The final technical interview of the day was another design question. It was with this question that I had the most trouble. It was a question that was directly related to how they track and update pricing information. I tried to use a database to help solve the problem. I'm not sure if this was the right approach or not as it really constricted me. In the end, I came up with a pretty pathetic solution to a very complex problem. I don't think either the interviewer or I was happy with it. It was the one interview that I sucked at :)

After that was supposed to be the boss of the second team I interviewed with. However, he was out of town so he sent a sub :) This person described his team and the other team that I was interviewing for. I asked a lot of questions trying to distinguish the teams. I don't know that I ever could distinguish between the two teams, they were so similar. The only difference I could gather is that one was also responsible for a new framework.

After not getting the team structure sorted out, I was on to the final meeting of the day. It was with the human resources person. He and I chatted about a few HR matters and then he showed me to the lobby where they called a taxi for me.

On the whole, my experience with Amazon was just "OK". They were obviously not a "tech" company. Their dress code, lack of free drinks, and general frugality said that they were a retail business. The employees were smart, but seemed a bit like "cowboys". Their plans were overly ambitious and I wondered about their success rate. I'd also read online about how hard they worked and how little they were rewarded for it. Now, I certainly don't believe everything I read online, but it can't help but color your views.

In the end, I thought that Microsoft would be the better choice. I've never worked for a "true" tech company and the search space was very exciting. I really enjoyed visiting Amazon and I'm sure it would be a fantastic company to work for, but in the end the prospect of working for Microsoft was too good to pass up.

Well, I hope you enjoyed this second installment of my interviews and be sure to look for the third (Yahoo!) and fourth (Google) installments.

Microsoft Interview - Live Search

2008-08-12T22:58:00.001-07:00

After reading about Ben's interview at Microsoft, I thought I would post my own. Perhaps I'll post my interviews at Google, Yahoo, and Amazon later.

Where to begin? Let me start by saying I'm not a Microsoft fanboy. I don't have anything against them and use Windows on my home desktop and Office at work, but that's about it. I spend most of my time in Cygwin: a linux environment for Windows. In addition, I use Emacs and Eclipse. I have programmed professionally for 8 years, 7 1/2 of those years have been exclusively in a Linux or Unix environment. My primary languages have been C++, Perl and more recently Java. For a while, I ran Ubuntu on my desktop, but the kids and wife didn't like that so much :) Nevertheless, I think you can see that I am by no means a Microsoft fanboy.

I first applied for a position at Microsoft in 2003 in their Visual Studio group. I had recently completed my Ph.D. at Clemson and thought I was God's gift to programmers. I won't go into that interview at this time, since this entry is focusing on my latest interview, but I will say I bombed badly. For one thing, I ate something that disagreed with me and spent more time in the bathroom than in the interviewer's offices. Secondly, I was interviewing for both a PM role and an SDE role and so I kept having to switch modes. Thirdly, I was bull headed and wouldn't listen to any of the interviewers. I just sucked. They said I could apply again in a year, but I didn't. I figured they had a big red X on my submission folder.

Most of my professional career has been spent at Acxiom, a global interactive marketing services firm. Primarily, I study and implement ideas around matching and record linkage. Over the last two years, we've been bringing machine learning and information retrieval research to bear on the record linkage problem and it has been very exciting. I wanted to spend more time working on those large scale problems. Therefore, I submitted my resume to a few of the larger companies: Google, Yahoo, Amazon, and Microsoft. I got callbacks from the first three. Microsoft still had that big ole X on my folder.

My Google interview was first. I'll describe it in another post, but I bombed it. I didn't study and they didn't give hints. They were a great group of people, but it just wasn't my day.

Next up was the Yahoo! interview. I thought I had bombed it as well, but apparently not. I got an offer to work with the Pig team. However, by this time I also had an interview with Amazon upcoming, so I requested that they wait for my decision until after that interview. On a side note, I think the Pig team is great and I wish them all the best in the future.

Needless to say, I was very excited after receiving the Yahoo! offer. Perhaps I wasn't an idiot after all (I had begun to wonder after the Google interview - and my wife was making fun of me!). The first thing I did was announce it on twitter. The funny thing is, Gretchen, of JobsBlog fame, follows me on twitter. Her response? "Congratulations! Sounds like we'll have to do something about that." (Note: Since twitter is public, I don't have a problem reposting her words here). By the end of the day, I had three Microsoft teams contacting me. Among those teams was the Live Search team. Since I was interested in machine learning and information retrieval, I requested that team be the one I interview for.

I wasn't too worried on the day of the phone screening. After all, I had passed two phone screens for each of the three other companies; how hard could this one be? Turns out, it could be pretty hard. The screener started out by asking if I primarily used live search. My response, "No, I prefer Google." Once it escaped my mouth I immediately knew I bombed. How could I interview for a product that I didn't even use! She then asked if I had ever used Live Search, to which I responded positively. I told her I didn't see much difference in the results, which was true. She then moved on to the "coding" question. I won't go into the question, but I will say I didn't do too well on it. I started out trying to use a dynamic programming algorithm. She quickly informed me that the problem could be solved in linear time. Ouch! We worked on the program for quite some time. I got down the right path, but needed quite a bit of help. She then took questions from me and the interview was over. I knew I wouldn't be moving to the second round. I even sent out a few text messages saying "When interviewing with Microsoft, the answer to 'Do you use live search?' is not 'No, I prefer Google'".

A few days later I was driving my family to a local water park when I got the call from Microsoft. They wanted to fly me out! Wow! Apparently it is OK to use Google after all! I certainly didn't expect that. I was already going to be in the Seattle area for my interview with Amazon, so I asked if they could schedule their interview at the same time. It required some fast moving on their part as my interview with Amazon was only a week away. However, they responded brilliantly and set up my accommodations and new return flight. The only thing left for me to do was choose which teams inside of live search I would prefer to interview with. They gave me a list of teams and their descriptions and I ranked them.

At this point, I'll skip over the Amazon interview and move forward in time to the day before the Microsoft interview. Amazon does not provide a rental car, but instead reimburses you for taxis. Therefore, I had to take a Taxi back to the airport and then get the rental car from Microsoft. From there, I drove to Redmond and found my hotel. It was in the Redmond Town Center, which provided a great venue for eating and shopping. I got there in the afternoon and I found greek diner in the town center. After lunch I went back to my hotel and watched some Ars Digita University algorithms classes. In addition, I had also spent some time reading the CLRS Algorithms book. Those two things, coupled with an online MIT course on algorithms would be my primary study guide. Unlike Ben, I didn't work too many problems out on my own, just geeked out over videos :) On a side note, the hotel that Amazon provided didn't have free in-room internet, so it was nice to be in a hotel that did.

At this point, my worst nightmare happened. My stomach began to churn and I started spending more time in the bathroom than out. Why did this keep happening to me? Was it nerves or do I REALLY not like Seattle food? I tried a couple of times to wander around the Redmond Town Center, but each time I kept having to run (literally) back to my hotel room. If this didn't pass by the next day, I was going to just die.

Luckily it went away. I ended up eating something light for supper instead of all the greek and italian food I'd been eating. That seemed to help. By the morning, I was going to the bathroom at a much slower pace, so maybe I'd be ok.

I left very early in order to get to Building 19 on time. I didn't map out the route the day before, so I wanted to be sure I could find it. I'm glad I did leave early because the signs to it aren't overly visible and I looped the Microsoft campus a few times before finding the right building.

The receptionist inside the Lobby of Bldg 19 took my name. I commented on her ear thingies. She had things in her earlobes like they have in Africa. I asked her what they were called and she said, "Gauges." I told her I was from Arkansas and we don't see too many things like that, but I thought they were cool. She thanked me and pointed to the waiting area. Yes, right, don't flirt with the receptionist...go sit down.

The waiting area came complete with an XBox 360 and a copy of Guitar Hero, which another candidate was playing. Well, at least I thought it was a candidate. I have to admit, she was really tearing up Guitar Hero - definitely a pro! After her turn ended, she looked back over at the receptionist and said, "Ok, your turn!". It turns out she was the OTHER receptionist. They swapped places and Gauge Girl began playing Guitar Hero (well, she offered it to me first, but I politely refused). Sadly, I began wondering if that was a test. Maybe they only hired people that played Guitar Hero when given the chance? (yeah, I'm sad like that)

After a bit of waiting, my recruiter came in. He took me back to his office and we began to talk about Microsoft. He gave me a great spiel about the company; he was a good salesman. We ended up talking longer than we should have and I had to hurry to get to a bus. Unfortunately, all the buses were gone and we had to wait for one to come back. It made me late to my first appointment :( He said not to worry, he would call over and tell them I was going to be late. Furthermore, like Ben, I was give a schedule that only went until 2:00. If I didn't perform, I'd be done then.

My first interview went ok. I never do great in the mornings, but I answered his questions satisfactorily. I forgot one simple case which finally came to me, but other than that, I did fine. I mentioned this failing to the next interviewer who said not to worry about it. The next interview was more challenging, I had read a bit about what he was asking, so I had some background, which I explained to him. However, I only had the broad theory, not the intricate details, so we proceeded to hammer out the details over the board. It was actually a lot of fun because I knew certain things to be true, but didn't know why. We discovered why together over the board. It caused a lot of "Aha!" moments. The only downside is that I missed a key part that caused my runtime to explode. I figured this out as he was chatting with the next interviewer and when they returned I mentioned the optimization to him. He nodded his agreement and passed me off.

At this point, it was lunchtime. My interviewer took me to the cafeteria. I got Chinese food because I thought I could eat the rice without it upsetting my stomach. We talked over lunch and I didn't eat much. We mainly discussed coding styles, agile methods, etc... Turns out he was interested in a book club I had started with my current company because he was running one for his team.

After lunch, we returned to his office for some interface design. I teach a UML class at The University of Arkansas at Little Rock so I sketched out my interface and design in UML. We went into detail around some of the decisions, like whether to use a visitor pattern and factory pattern. I think I did ok, but it is hard to design an interface without seeing use cases for it first. I mentioned this toward the end and he agreed. At the end of this interview it was 2:00...and...he took me to the next interview!

During this interview I was back to coding. Actually, I never got around to coding too much as I spent most of my time determining the algorithm. This is a big difference from my first Microsoft interview as I would have gone straight to the code. In this interview, I stepped back, looked at a number of examples and came up with the right solution first. I coded it pretty quickly, but no major mistakes. He showed me some of the cool things his team had been working on. I was really impressed! Then, he took me to the next interviewer. This interviewer focused me on a "real world" problem. In other words, this problem was one that they had seen and solved in the past. It took me about half the interview, but I came up with the solution. He seemed impressed and said that not many of their interviewers come up with that solution and it is the one that they actually used in production. I was pretty pleased with myself at that point. We spent the rest of the time talking about their projects, team structure, etc... It turns out that both teams I interviewed with spend a lot of time working with Microsoft Research, which is really cool for an academic like me :)

That was the last interview before the "big boss", who took me to get a drink and a snack. I was hungry since I didn't eat much lunch, so I took him up on a granola bar and a bottle of water. He spent a lot of time telling me about Microsoft and asking me about my previous experience and the work I did with my current company. I told him what I could without violating any NDAs. He seemed pleased with what I told him and I was very impressed with what he was saying about the future of the team. He described a lot of their internal systems and frameworks, all of which excited me. Like the recruiter, he was a great salesman. That must be a Microsoft thing :)

After our discussion, he said that I should meet the other team's "big boss" (my words, not his). He left me in the lobby of his building and went to hunt the other one down. Turns out the other "big boss" had just gotten done playing softball with the interns and needed to clean up, but offered to take me to dinner. I graciously accepted and sat down to wait as he got ready. I went to eat with him and one of his team leads (who I had interviewed with previously) at an Italian restaurant in the Redmond Town Center. We talked about Microsoft, the Yahoo deal, Google, our mutual desire to WIN, etc... He was also a great salesman.

I was pretty pumped after leaving there that night and couldn't sleep a bit on my red-eye flight back home. I called my wife and told her that I was pretty sure we'd have an offer from Microsoft to consider. Turns out we would also have an offer from Amazon.

I won't go too much into my decision making process other than to say that I did not like the Silicon Valley area. It just felt dirty to me. I was much more at home in Seattle. I liked the contemporary vibe and the fact that there were actual trees. Lots of trees. Yeah, I know it rains, but I don't like the sun much, anyway :) Therefore, though the Yahoo! job was very attractive, I just could not accept it. My decision was between Amazon and Microsoft.

At one point, I thought I wasn't going to accept any of the offers. We are settled, the kids are in school, we own our home, and life isn't too bad. However, I think the ability to work with some amazingly smart people and have Microsoft on the resume is too good to pass up. It is not often that you get to work with internet scale data. My work at Acxiom is on billions of records, but nothing like what you see when you consider search. The playing field is very, very different and you have to think WAY outside the box, which I love to do. Moreover, I think it would benefit our kids to be in an environment like Seattle. There's a lot to see and do there and there are many more opportunities there than there are here in Arkansas. Finally, the school systems there are very good and I think the kids will benefit greatly from that.

I start on August 25th and I am very excited. I'll be sad to leave a great team behind, but I know they wish me the best as well. Now, I'm looking forward to starting the next phase of my life as a member of the Live Search team. Google, look out!

New Job

2008-08-12T15:18:00.000-07:00

I'm excited to announce that I am joining Microsoft to work on their Microsoft Live Search Engine. It's going to be a big transition, but I've never lived in the northwest, so it is a very exciting time as well. I begin there on August 25 and am very excited!

Please keep me in your prayers during this exciting, but stressful time.

The last month

2008-07-12T00:25:00.000-07:00

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

2008-07-08T23:25:00.001-07:00

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

Researching in a Search 2.0 world

2008-07-01T21:54:00.001-07:00

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?

2008-06-20T15:24:00.000-07:00

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

2008-06-16T23:37:00.001-07:00

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

2008-06-04T21:45:00.000-07:00

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

2008-05-29T14:02:00.000-07:00

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

2008-05-27T11:28:00.000-07:00

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

2008-05-26T22:17:00.000-07:00

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

2008-05-24T13:36:00.000-07:00

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

2008-05-23T17:12:00.001-07:00

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

2008-05-22T21:27:00.000-07:00

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

2008-05-22T15:48:00.000-07:00

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

2008-05-22T13:04:00.000-07:00

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

2008-05-21T15:50:00.000-07:00

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

2008-05-21T10:38:00.000-07:00

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

2008-05-20T12:34:00.000-07:00

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

2008-05-03T18:32:00.000-07:00

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

2008-04-27T00:20:00.001-07:00

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

2008-03-20T06:27:00.000-07:00

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.

Data mining

2008-03-18T04:23:00.000-07:00

To feed my continuing interest in behavioral economics, I've decided to dig deeper into data mining. It seems that every researcher uses data mining in some way. I'm taking a course in statistical approaches to natural language processing. It is definitely improving my understanding of the difficulties involved in analyzing the data. I also hope to get a few books on the subject soon.

It seems that real estate data is quite the gem of the behavioral economics world. I guess because it is free and easily accessible, it gets more interest, much like blogs for the search community.

Probably the best thing to do would be start with a question. What do I want to know about the world? And then start finding the right ways to answer it. I'm not sure what my question will be. Stay tuned. In the mean time, I wonder where you find real estate data...

Lost

2008-03-13T21:15:00.001-07:00

The other day, we lost a student in our program. Our website, still in beta, was a bit too buggy and too confusing. He or she was right to leave, we should have put more time into user testing. Instead of throwing out half-baked ideas, we should have made them a little more solid. We released a student site and sent them a link, but didn't link to it on our homepage. We did have a link to our forum, but our forum username wasn't the same as the student username and password. But we learned from that experience. We're focusing heavily now on usability. We're trimming unnecessary fat and trying to unify our systems. I lost one student, but I don't want to lose another for similar reasons.

So, if we send out a link to it, the link better be on the front page. Also, people like to have a button that says "login". Finally, if you have multiple features, the login information should be consistent among all three. Since we grew organically and a little haphazardly, we didn't think of these things. Now they've bitten us and it is time to fix them.

Michael Buble

2008-03-11T17:01:00.000-07:00

My wife and I went to see Michael Buble' last night in Memphis. He's a very good entertainer. However, it was sad to think that he is the best standards singer of our time. He's not on the level of a Frank Sinatra or even a Bing Crosby. I think of him more like a Sammy Davis Jr. type. I actually like his original compositions more than I do his take on the standards. Anyway, I would recommend going if you get the chance, he's worth that. I just wouldn't go more than once.

At least Memphis in May is coming up soon. I am looking forward to that!

Remote users

2008-03-07T22:35:00.000-08:00

Remote users are the worst. It was nice when all I had to deal with were me and my friend. There were no versioning problems and when differences did arise, I just drove down the street and took care of them. Now, my software has to run on XP and Vista (yes, that can be problematic). It has to run with different versions of Internet Explorer. It has to deal with all sorts of problems that it didn't have to when it was just for me. However, I have to say I'm learning a lot. I can now manipulate the DOM like nobody's business. Is that useful? Probably not. But then again, when have I cared about usefulness, as long as its cool :)

Why doesn't everyone use unicode?

2008-03-07T03:49:00.000-08:00

Well, my promise to blog daily was short lived, but I'm back now. Wednesday's are going to be hard for me to blog because I teach a night class about 2 hours from where I live. But, I should have blogged on Thursday, no excuses there.

On to today's topic.

I spent multiple hours yesterday dealing with a character set encoding issue. As I've mentioned, our chess training site is multi-lingual. Therefore, we store all of our messages in UTF-8. Our database, MySQL, is set to use unicode as is our server side language, PHP. Our client side language, perl, is also set to use unicode. However, no matter how hard I tried, whenever I sent a message using red hot pawn via our software, the message got corrupted. I could manually copy and paste the message from our database viewer to the message sender and it would work fine, but when my software did it, the ä came out looking like Ã and some other symbol that I wasn't familiar with. Of course, having it print to my screen from perl caused it to come out looking like a third symbol Σ. Obviously, Internet Explorer, perl, and my windows console were all using different character sets. I found my setting for Internet Explorer. It was set to ISO-8859-1 (Latin 1). I did not find the setting for my windows command prompt. I assume it was using some Windows character set. I tried changing the Internet Explorer setting, but it didn't seem to have an effect. Finally, after a few hours of hunting and validating various settings, I checked the encoding on the red hot pawn page. It was set to ISO-8859-1. Ah ha! So, they were enforcing their own encoding on the page. Apparently, when I copy and paste, the operating system does the conversion in the background for me. However, when my program does it, I have to do the conversion myself. Because of a few limitations, using the perl Encode module was not an option for me. So, I settled on utf8::downgrade. This won't work if someone's desktop settings are not Latin-1, but is suits my needs at the moment. Why can't everyone just use unicode?

The value of free

2008-03-04T22:46:00.000-08:00

Predictably Irrational spends quite a bit of time talking about the value of free. Apparently, free makes you go bananas. For instance, if you are checking out at a store and are offered a hershey's kiss for free or a lindt chocolate truffle for $.14, over 70% of the people take the free kiss. If you charge just $.01 for the hershey's kiss, then over 70% of the people will take the truffle, even though it is $.15 (adding the penny back in for relative difference reasons). Free makes people bananas.

Another study came from Amazon. When Amazon started offering free shipping, their sales increased dramatically everywhere but in France. France saw no difference. After researching it, they discovered that the French division had decided not to go completely free, but instead charge 1 Franc (about US $.20 at the time). This small fee was enough to change people's brain chemistry. When they reduced the price to free, France also saw a big jump in purchases.

The next chapter expands this by considering social norms and market norms. We deal with both every day, but we try not to mix them. If you are using a social norm (like eating dinner at a friend's house), you don't offer to pay. You can give a small gift as appreciation, but you NEVER bring up money. Contrariwise, if you are using a market norm, then you want the best deal - you act selfish. What their research found was that the smallest payment was enough to change people from a social norm to a market norm. In fact, even the idea of money was enough to make the change. For instance, if you ask someone off the street to help you move a couch, they will agree. If, instead, you offer to pay them $1.00 to help you, they will turn and run because they are insulted. When operating in market norm phase they want the best deal, when operating in social norm phase, they want to help.

Perhaps we take the free Hershey's kiss over the lindt truffle because we want to operate in a social norm. We are social creatures and we want to be unselfish. Perhaps by thinking of the kiss as a free gift, we get to stay in our social environment that much longer, keeping out the harsh market realities.

Force and Counterforce

2008-03-03T22:46:00.000-08:00

I'm programming the Personal Chess Training website with a friend. He does most of the content work (web design, chess problems, hints, etc...). I do most of the hard core programming. We split the database work, the hard stuff goes to me and he picks up the easier things.

The one thing that is interesting is how force and counterforce work together between us. For example, I prefer to take things slow and steadily. He prefers to rush in and see what breaks. I have my students set to 1 or 2 problems at a time, he sent out 25 to all of his students at once. I had hoped to add 1 or 2 additional teachers, he signed up 10. Often, his forces create counter forces in the code base. For instance, I got tired of hardcoding the teacher name in the code, so now I pull it automatically from their cookies. We needed some way to handle his problem load, so we created tracks and simultaneous games that could be set per teacher. I also added automatic restarting of mates in 1 since he was having to work through so many that students missed. Each push that he has given has resulted in a counter push by me to automate the site to reduce my workload.

I wonder how many other things have come about from a force and a counter force. After all, necessity is the mother of invention.

Personal Chess Training

2008-03-02T19:25:00.001-08:00

Recently, I've been working on a chess training site with a friend. He's around 2100 and is a very good endgame technician. We designed a course to help others with their endgames. If you are interested in improving your chess endgame (for free!), then please visit our site. You use a free correspondence chess site www.redhotpawn.com to play the games with REAL HUMANS. We've had a number of great comments on the redhotpawn forum that we can direct you to if you are interested.

To subscribe, just join red hot pawn and message me (thgibbs) or my friend (petrovitch) with a message indicating your interest.

Comparisons and Anchors

2008-03-02T19:06:00.000-08:00

It's been a while since I posted, but I'm going to try and post daily from this point on - we'll see.

I've been listening to the book Predictably Irrational: The Hidden Forces that Shape Our Decisions on my iPhone that I got from my audible subscription. In this book, the author describes how we compare things and how anchors affect us. In short, an anchor is the first thing that we related to a category. I'll give an example. If we see a bicycle advertised for $20, then $20 becomes the anchor price for all bicycles. If we later see a bicycle for $40 we believe that it is either better in some way or overpriced, but we always go back and compare it to the first price we saw. He performed studies where anchors were used to manipulate the amount people would pay for an item. For instance, if people were asked if $10 were a reasonable price for an item, their maximum price was much higher than those people who were asked if $0.10 were a reasonable price. The initial anchor greatly affects how we view future spending on an item.

I believe that an iterative approach to software development should be described in these terms. With the first iteration we give the user an anchor. He then can make decisions about that program with the initial program in mind. His requests should be more rational because he is going to frame them in the context of the initial anchor. With a traditional waterfall approach, the user has to create the requirements without an anchor. This leads to unnecessary requirements and unused features because the anchor isn't present. There doesn't exist a "good" or "bad" context to help shape the program, there is only air. By creating an initial draft of the program, we create an anchor that guides the user, giving them the all important context that ensures a successful program.

Fox News

2007-05-01T10:36:00.001-07:00

Gotta love Fox News and Katrina Victims getting together.

Warning: Not work safe!

Here's the link

iGoogle

2007-05-01T10:32:00.000-07:00

I really like iGoogle, it helps me keep all my blogs and news together on one web page and it is with me wherever I go.

However, this morning, I logged in to check it and all my content was gone. I had spent a lot of time setting it up, now I'll have to go back through and do it again :-( How disappointing.

Google Themes

2007-04-28T09:21:00.000-07:00

Wow, Google has done it again! I opened up my Google homepage to notice that you can set the theme for your homepage. I picked the seasonal theme, because I like the whimsy. The really cool thing is that it changes based on the time of day, season, etc...

Google has a brilliant strategy. They are slowly making you productive and happy on the web. It's not a huge shift, just small steps, each one increasing your happiness. Eventually, you won't even consider using a desktop app, because you'll be completely comfortable with the web based ones. The content can be updated constantly, you take it with you wherever you go, you can share it easily with others, etc...

The people at Google are brilliant.

What I've Learned

2007-02-26T07:29:00.000-08:00

I learned a number of things over the last week, so I thought I'd share

1) I could never be an academic, I don't own a suit
2) I really like playing the piano, even though I suck at it
3) The good thing is, I suck at everything, so there's not much incentive not to do it
4) I am an idiot (Actually, I already knew that, I just keep learning that I'm more of an idiot than I previously thought.)
5) RFID tags will be the next big thing. There's going to be some cool stuff done with those.
6) Ecclesiastes is the coolest book :-)
7) I like the term psychological gymnastics. I tend to perform them often. It's a constant struggle between seeing what you want to see and seeing what is really there.

The Shape of Data

2007-02-20T03:55:00.000-08:00

The first time I heard anyone talk about the shape of data, it was Anders Hejlsberg. He was discussing C# and LINQ. I distinctly remember him discussing the shape of arrays as being rectangular. He contrasted this with the more jagged shape of XML data. Not only that, but one can change the shape of the XML by choosing to use attributes instead of tags. I tended to think this was fascinating and worth further thought. The ability to view data structures geometrically could lead to some amazing insights. Of course, after the initial flash, I gave it no more thought. However, the folks at Microsoft Research did, and they've produced this paper. I hope it is as interesting as Anders' initial insights were.

Meta Math!

2007-02-16T07:22:00.000-08:00

I've been reading Chaitin's book Meta Math! about Chaitin's Constant. I can't really say I enjoy his writing, but his ideas are very interesting. If he were less of an arrogant, self-centered prat, the book would be more enjoyable.

The section that was most interesting to me was the one in which he argues that trancendental numbers aren't really numbers. This reflects some of my earlier blog posts where I also say those numbers don't exist. Instead, I believe they are functions which generate the numbers to a specified precision.

Anyway, the book is interesting, though poorly written. Maybe some of his other books are better. Probably not. I'm sure they are also full of self-gloating and self-adoration.

Ecclesiastes 1

2007-02-16T07:11:00.000-08:00

I always felt I understood Solomon and wanted to pattern my life after his. Here, at this point, I understand Ecclesiastes and continue to follow in the Teacher's wake.

Vanity of vanities," says the Teacher,
"Vanity of vanities! All is vanity."

What advantage does man have in all his work
Which he does under the sun?

A generation goes and a generation comes,
But the earth remains forever.

Also, the sun rises and the sun sets;
And hastening to its place it rises there again.

Blowing toward the south,
Then turning toward the north,
The wind continues swirling along;
And on its circular courses the wind returns.

All the rivers flow into the sea,
Yet the sea is not full.
To the place where the rivers flow,
There they flow again.

All things are wearisome;
Man is not able to tell it.
The eye is not satisfied with seeing,
Nor is the ear filled with hearing.

That which has been is that which will be,
And that which has been done is that which will be done.
So there is nothing new under the sun.

Is there anything of which one might say,
"See this, it is new"?
Already it has existed for ages
Which were before us.

There is no remembrance of earlier things;
And also of the later things which will occur,
There will be for them no remembrance
Among those who will come later still.

I, the Teacher, have been king over Israel in Jerusalem.

And I set my mind to seek and explore by wisdom concerning all that has been done under heaven It is a grievous task which God has given to the sons of men to be afflicted with.

I have seen all the works which have been done under the sun, and behold, all is vanity and striving after wind.

What is crooked cannot be straightened and what is lacking cannot be counted.

I said to myself, "Behold, I have magnified and increased wisdom more than all who were over Jerusalem before me; and my mind has observed a wealth of wisdom and knowledge."

And I set my mind to know wisdom and to know madness and folly; I realized that this also is striving after wind.

Because in much wisdom there is much grief, and increasing knowledge results in increasing pain.

Dark

2007-02-15T19:49:00.000-08:00

I've been in a dark mood lately for various reasons. Today, I went to visit random blogs, I thought it might cheer me up. Boy, was I wrong. People write the most mundane, idiotic things. I don't care about your shopping list. I don't care about what you got for Valentine's day. Write something with some substance, try to make a freaking difference! Don't depress me further.

Life sucks and then you die.

Poem

2007-02-14T04:52:00.000-08:00

I once wrote a poem in high school for a class. I always liked the poem. I don't have it anymore, but I remember the last verse. I thought I would create a new poem that was similar and used the last verse. Here goes.

Shadows lurk on closed windows.
The moon's luster provides
a fitting nursery.

Monsters spring forth
depriving me of slumber,
laughing at my countenance.

I turn away,
horrified.
They persist;
they encircle me.

I board up the window
with long nails,
and time-worn planks.

The monsters vanish,
but their tendrils remain.
They prod me,
tease me,
remind me.

The warmth on my back is shocking.
I turn.
A new window has opened.

Its light is brilliant.
There are no shadows here,
but the sun will set;
they will come.

For a moment,
I bask in the warmth;
I feed off the glow.

But shadows lurk on closed windows.
Cold,
Dark,
Lonely,
I will never forget.

It needs some work, but I'll try and edit it from time to time. Stop back by to check on its progress.

I hate dreaming

2007-02-13T14:14:00.000-08:00

I hate dreaming. I absolutely hate it. Most of my dreams are awful. When I was a child, I had night terrors. Like most cases, they went away as I grew up. Unfortunately, mine returned after my father died. It is said that they can return after a stressful or traumatic event, and they did. What's worse is that I've always been able to recall them. Most people just wake up screaming with no idea why. Me? I have full recollection of the terrors. Luckily, my wife is used to it, she just ignores me when I wake up screaming; although I'm sure it annoys her.

Other dreams are just as bad. They usually represent something I've repressed and don't want to think about. So now, I've done a good job of not thinking about certain topics and my dreams just drag them up and force me to confront them. I can't win. The whole point of repressing things is so that I don't have to deal with them. What good does it do if my subconcious is plotting against me! Arrrrggggg!

Anyway, the whole point of this post is to say that I hate dreaming. It sucks. Anybody have any good dream experiences and maybe some advice on how to get those instead of the ones I have? It would be most appreciated.

Dr Jim Gray is missing

2007-02-04T17:13:00.000-08:00

It is a very sad day. Dr. Jim Gray, brilliant database researcher (two phase commits, anyone?) has gone missing. Apparently, he was on a boat trip to scatter his mother's ashes and no one has heard from him since. Amazon has set up a number of satellite images that you can manually inspect to see if you can help find his boat. You can read more about it here.

My prayers go out to Dr. Gray and his family.

And, if you don't have a copy of his book, Transaction Processing, you should. It is a must read, especially in the coming world of multi-core processors.

Why I hate working from home

2007-02-03T23:17:00.000-08:00

I work from home for a living. I go into the office, on average, once a week. At the present, I don't really work closely with a team of people, so I really don't have a need to go into the office. However, I have to say that I absolutely hate working from home. The main thing I miss is the people. I like working with people. I like to run my ideas past people and get their opinions. I like to help other people with their problems. Right now, I live my life behind a mask of email and text messages. It is so boring. I don't get to hear another adult's voice until my wife comes home at night, and you can only listen to the TV or radio for so long before it affects your concentration. Furthermore, working from home severely limits your career movement. That's not something I'm overly concerned about, but it certainly doesn't add anything.

So, why do I work from home? For my kids. My wife works an hour from where we live; she's a nurse in a children's hospital and she loves her job. I wouldn't ask her to change that for anything. However, with two children, someone has to be available to pick them up in the afternoons from school and watch them. This is the job that I have chosen to do. When my wife was in nursing school, I worked for a company that was an hour away. I really did enjoy it. The company and the people were great and I loved being in an office atmosphere. When my wife graduated, we moved away and we both worked near the home. However, this meant that the kids were in day care until 5:30 or 6:00 every day. That was not how I wanted my kids to be raised. So, we moved back home and I took a job working out of my home again. It was a hard thing for me to do; those closest to me know it was a real struggle. Nevertheless, it was the right choice. The kids are the most important thing and one day they will be old enough such that they won't need me here. Until then, I'll chat away online and thinking to myself that working from home sucks.

Don't get me wrong, if you work in an office for a living, then working from home occasionally is a nice change of pace. On the other hand, working from home permanently is like being locked away in solitary confinement. You end up stir crazy talking to the dog or yourself, typically both. I often wonder what other people do in this situation. Does one of them not work? I can't imagine asking my wife to not work, she loves what she does. Do people leave their kids with other family members? Perhaps they go the day care route, or maybe something else that I'm not considering? I know my solution to the problem, but I'd be curious to know others' solutions and why.

There is but one infinity

2007-01-29T22:39:00.000-08:00

I've always been hung up on the notion of countable vs uncountable infinity. It seemed a rather silly thing to say, that you could have more than infinity. I understand the argument for it, but from an intuitive level, it felt wrong. Now, I feel that it is completely wrong. There are only two kinds of numbers, those whose digits can be represented and those whose digits can't. 7, 13, 10000000 all belong to the first category as well as .015, .139, and .00000000000000000000000000000000001. PI, 1/3, and e all belong to the second. The second category of numbers are not really numbers but ideas. They are, in essence, equations. Given a precision, they can produce a number of the first category, but they are not numbers in and of themselves. Another example would be the summation of the reciprocals of all integers, given a precision, we can produce the number, but the summation itself is just an abstract notion. With that we can understand that what we consider to be countable infinity doesn't really exist. It is in the second category and is therefore part of the larger infinity. If you give the countable numbers a precision (limit), then you can discuss those numbers; however, without a limit, the countable numbers are just an idea, much like PI, or the zeta function. In fact, you could think of the countable numbers as a function that, given a number, produces a new number one higher. However, there is a difference between the "idea" of the function and the numbers that the function produces. The idea of the function can go into the infinite, the actual numbers cannot. The same holds true with PI. The idea of PI can go into the infinite, the actual number can't. The problem with the proof of uncountable infinity is that the natural numbers are limited to the finite whereas the irrational numbers are allowed to go to the infinite. When one realizes that the irrational numbers cannot go to the infinite, then the proof becomes nonsense.

The Game

2007-01-24T21:39:00.000-08:00

Last Sunday I went to the AFC Championship Game between the Indianapolis Colts and the New England Patriots. It was a blast. The game was amazing and the RCA Dome is an excellent environment. The one thing I noticed is how loud it is there, well, at least when the other team is on the field. You don't get a true idea of the volume through TV or radio. The other thing I noticed were how great the fans were. We were sitting beside a number of Colts fans and they were extremely classy and fun to be around. I have to say that I was surprised at how much fun I had watching the game. I had begun to think that football had become a television sport, but I can safely say that is not the case. It was soooo much better watching it live and in-person. It didn't feel productionalized. It felt raw and real. I had a truly amazing time and I can't wait for next year's game!

Google Books

2007-01-17T17:54:00.000-08:00

I didn't know google had a public book storage and viewing mechanism, but apparently they do. Since I've been searching for boolean equation stuffage, I ran across it.

Here's a Dover book I found:
Boolean Reasoning: The Logic of Boolean Equations.

BigTable

2007-01-17T16:19:00.000-08:00

Google has been slowly developing tools and technologies to support its unique requirements. I'd like to use this post to catalog information about them.

BigTable is google's answer to the database. Wikipedia has a good article on it here.
MapReduce is google's answer to workflow. The article is here.
Sawzall is google's high level distributed language. The paper is here.
GFS is google's file system. The article is here.

Great CDI Blog

2007-01-17T13:26:00.000-08:00

Here's a great blog from someone who understands CDI from the business perspective. An excellent read. Head's up, her name is pronounced "dishay".

Google's video picks

2007-01-17T06:43:00.000-08:00

For those of you who want a little substance and are having a hard time finding it with YouTube, check out Google's top 20 video picks here.

Big brother strikes again

2007-01-17T06:24:00.000-08:00

Where do we draw the line? Jeff Jonas details the using of a P300 brain response as allowable evidence in court cases.

I would like to have seen more information about what a P300 response is. Is it possible that some people are "malformed" and have this response even when presented with an unfamiliar image? What if it is your living room and, while the blood is unfamiliar, the rest of the information is. There are too many variables for me to enjoy this.

As for going to jail because you thought about committing a crime, that is ludicrous. The difference between humanity and animals is that we can control our actions. I'm not sure we can control our thoughts. Regardless, as humans, we must be judged on what we can control.

Boolean Equation Problem

2007-01-16T13:12:00.000-08:00

I'm struggling with the following problem.

I have a series of boolean equations. Only one of these equations can be true at any one time. I need to find an efficient way of determining which of these equations is true. I would also like to know more about these equations, like is it true that only one of the equations can be true and what new equations are needed to make that true.

Here's an example. Let's say that half of the equations deal with the condition where variable A issw equal to the value 'M'. 25% of the equations deal with the condition where variable A is 'm', 25% of the equations deal with the condition where variable A is 'n', 15% where the variable A is '?' and 10% where the variable A is 'N'. The variable B has a situation where 75% of the equations deal with the condition where it is 'M' and the other 25% of the equations are divided among the other choices. There are also variables C, D, E, F, and G. Which of these variables do I evaluate first? What factors should I consider? Are there algorithms that will help me in determining this?

Ch-ch-ch changes

2007-01-16T10:08:00.000-08:00

The previous year was a year of changes. I worked for three different companies, in three different cities, one of which required me to move 800 miles away. Now, I'm back where I began and I've learned an awful lot and met some truly amazing people.

One of the first things I learned is that there is nothing more important than your family. I missed being able to pick my kids up from school and taking care of them in the afternoons. I also missed the good friends I had made here. I didn't realize how much I had missed them until I moved back.

Second, I learned that going to church is an important part of your spiritual development. Seems obvious, right? Well, I've recently been going to the First United Methodist Church of Wynne and have really enjoyed both the service and the Sunday School. I've been going there with friends, which really helps.

Third, I have learned a lot, technically. I've learned the value of having business people drive functionality and I've learned the value of architecture that is planned over architecture that evolves. I've learned about J2EE, CORBA, networking, TIBCO, and a whole host of other things. I enjoy learning, so that was fantastic.

Fourth, I learned that to be a good team leader, you've got to be able to stand up for those who are working for you. I've had leaders that I really enjoyed at all the companies -- they were all really positive experiences. Each one had a different style, but when it came time to go to bat, they were there to stand up for me.

Fifth, I learned that if you want to stay challenged in a traditionally business IT shop, you need to challenge yourself. It seems the expectations of those places are low and you can easily "just get by." In fact, you can easily descend into madness. But, to truly excel, you have to challenge yourself to come up with innovative ideas to make their software cost less and be more stable. I think more and more the key to good programming is focusing on stability.

Sixth, I learned that I have to make tradeoffs and I'm thankful for the past year because it helped me understand what those tradeoffs are. Right now, I work from home. It allows me to pick up the kids and help out my wife, who drives an hour to work three days a week. However, it also isolates me from communication with others. I really like the office setting where I can talk to an adult when I run into a roadblock, instead of being isolated from everyone. Therefore, I have to realize the need exists and try to assuage it in a different manner. Eventually, I'll go into the office more (at least 2 days per week) and hope that helps. However, right now I'm not working with a team, so going into the office doesn't really help. Nevertheless, spending the last year in two different office environments helped remind me that it can be a lot of fun and that I need to remember to go into the office more when I feel isolated.

Finally, as I head back to my old job, I realize that the reasons I left it are still there. However, after spending a year studying myself and other companies, I'm am in a much better position to adapt so that those things will no longer bother me. Right now I just want to be appreciative of the great gifts that God has given me. I'll worry about the other things later :-)

Similar Characters

2006-12-28T09:25:00.000-08:00

I try to keep track of people who are similar to me: past, present, and fiction. I have three, currently, that I believe fit the bill.

1) House - I've blogged on this before, but Greg House from the TV show House is very similar to what I am like. I think he has let his pride control him more than I have and that accounts for a few differences. But, on the whole, we are very similar.
2) Isaac Newton - We have similar interests, religious beliefs, and personalities. He, of course, was far more brilliant that I ever could be, but we are very similar in our pursuits.
3) Brad Paisley - Yeah, the country singer. It's uncanny how many ideas in common we've had. In fact, before they released his "Two people fell in love song", I commented to my wife that everything that has ever been was because two people had sex. Mine was more crass, but that's beside the point. When my wife heard it on the radio, she immediately came to find me and show me my idea had become a song. It was funny. I still say he has spies that watch me...I need to go now...I have to elude them!

Aliens

2006-11-21T09:34:00.000-08:00

I watched a history channel special the other night on UFOs. It had some interesting interviews on it. One thing that was eye opening was the replay of a nasa astronaut saying over the radio that he was looking at the alien spaceship out of his window. He said it very matter-of-factly and very clearly. He was neither surprised nor concerned. I have no problem believing in aliens. However, the Roswell stuff is a bit far fetched. How is it that the aliens can fly billions of miles across the universe and then crash in New Mexico? Doesn't make a whole lot of sense to me.

However, I propose the following. I think the next candidate for president of the United States should run on a platform of revealing all government knowledge of UFOs. I'd vote for that person, I think it'd be cool to know. What about you?

Unfair Infinities

2006-11-20T09:56:00.000-08:00

We all know that the cardinality of the set of all integers is countably infinite. To me, it seems unfair that the cardinality of the set of real numbers is uncoutably infinite. It also seems odd that it is unintuitive to most (including me). However, I now understand why it was unintuitive to me. The key point to remember is that mathematicians don't allow integers to have an infinite number of digits. Instead, you can increase the integer by 1, but at any given time it has a fixed number of digits. However, with real numbers, there can, and often does, exist an infinity of digits. For instance, 1/3 is 0.333333.... So, not only do the real numbers extend countably to infinity, they also can have an infinite number of digits. In essence, they are infinite in 2 dimensions, whereas integers are only infinite in 1 dimension. I would imagine that complex numbers will one day be proven to be infinite in 3 dimensions, but who knows.

To be honest, I think it is a bit silly. We're not actually talking about different orders of infinities here, we're only talking about the existence of a function M that will map from one infinite set to another. If we can find that function, then we say the sets have an equivalent cardinality. Otherwise, the cardinality of one set is said to be greater than the cardinality of the other. If we could extract M from mathematics, and instead use an algorithm, then M could simply be, pick a real number, get next biggest integer, rinse, repeat. However, algorithms are not yet mathematical (unless you're Stephen Wolfram).

Readable Code

2006-10-10T18:20:00.000-07:00

I think, to structure your code readably, you have to partition your code into different levels. Perhaps the different levels are written in different languages, perhaps not. The top level is the business level. At this level, you should be speaking a mostly declarative language and should be side effect free. Your code should be straightline. The second level is the logical level. At this level, you can have conditions and iterations and anything in the first level. The third level allows anything in the second level plus side effects. Finally, the fourth level allows comparative and arithmetic operations plus anything in the third level. The interesting thing to note, I believe, is that side effects are more readable than comparative and arithmetic code. Of course, it could be that comparative and arithmetic code is less useful than side effect code, so it is pushed to a lower level.

Let's look at an example:

extern int debug;

void foo()
{
int i;
for(i = 0; i < 100; ++i)
{
if(debug)
{
printf("%d\n", i);
}
}
}

This is a level 4 function. It has side effects, comparisons, etc... Let's try to turn it into a full 4-tiered function (yes, you wouldn't do that to something like this, but just for example.)

// level 1 - straightline
void foo()
{
print_numbers_to(100);
}

//level 2 - conditions
void print_numbers_to(int count)
{
if (in_debug())
loop_to(count, print_integer);
}

// level 3 - side effects
void print_integer(int i)
{
printf("%d\n", i);
}

// level 4 - comparisons
int in_debug()
{
return debug == 1;
}

// level 4 - side effects
void loop_to(int count, void (*func)(int))
{
int i;
for(i = 0; i < count; ++i)
{
func(i);
}
}

See how much better that is?

Responses

2006-09-12T07:11:00.000-07:00

I put some responses in with comments. However, I would like to say that I was imprecise in a previous statement...it's a habit of mine. My statement should not have been that deficit spending causes war. Cos is entirely correct that war causes deficit spending, not the other way around. You can check the comments for the full scoop, but I was attempting to say that the ability to deficit spend leads to war. If you can't fund the war, you won't have the war (or you won't be successful at it). If you have easy access to funds, then you can easily create a war machine. If not, it is much harder. It is not deficit spending, but the ability to deficit spend. Check the comments ;-)

Response 3

2006-09-12T05:58:00.000-07:00

Now, I'd like to respond to a few things I agree with from Cos's reply

1. I really like the idea of the states paying the Senator's salaries. This further reduces the federal stranglehold on our country. That is just pure brilliance!

2. My hope is that people who have a concern for our country would want to be electors. However, now that you mention it, I wouldn't be surprised if party-liners didn't run for electors just to be paid back at a later date by the party nominating them for an office position. I really don't want to enable a lot of restrictions, because that doesn't lead to a naturally balancing system. For instance, we could say that electors can never be publicly elected, but that is just silly in the long run. My hope is that the more educated, politically motivated people would become electors...however that is naive.

Nevertheless, what I realistically expect to happen is that entitlement spending drops dramatically, and socialistic programs begin to decline. When the voters don't elect you based on the entitlements you give them, you no longer give entitlements. Obviously, an elector could run on a platform of entitlements, but it doesn't really help him. He's not getting a huge salary and a plush office for life, so why does he care. His sole purpose is to do what is right for the country, because it is right, not because he's getting compensated. It could be a naive position, and I know it will eventually be corrupted, but I'm hoping that won't be for a number of years, when the system is stable enough to support a number of years of corruption before being reset again.

Response 2

2006-09-12T05:33:00.000-07:00

I'd like to respond to a portion of a very well thought out comment from Cosbert Callis:

3) Frankly neither suggestion of the barter system or the gold standard, nor the idea of eliminating the Fed represents an understanding of economics 101.
(as a fiscal conservative, with a BA in Political Science and a Minor in Economics, you would have failed any econ class I was in with these ideas..)

Foreign trade (including deficit spending, which is a form of foreign trade) represents one of the most important natural forces for peace in the world. People just do not make WAR with trading partners. I don't where your original thought inevitably leads to war and inflation. comes from, there is NO, ZERO, NADA in the way of empirical evidence to suggest there is a single iota of truth in that statement.

First, deficit spending is not always a form of foreign trade. Deficits can come in many forms. First, you can sell bonds to your own country. Second, you can have the Fed print more money, thus causing inflation, but giving you the money you requested. Third, you can sell bonds to other countries. I would only classify the last as deficit spending.

Second, deficit spending MOST DEFINITELY causes war. You would have failed any history class I took with your ideas. War's have to be funded in some way. Without funding, you can't fight. There are many ways to get funding, but the easiest is through deficit spending. Do you think the war in Iraq would have happened if we would have had to raise taxes to pay for it? People understand taxes: they understand the effect that taxes have on their pocketbooks. With deficit spending, they don't understand the correlations and are less likely to complain. Therefore, deficit spending is VITAL in starting and maintaining a war machine. Without easily obtainable money, there are far fewer wars.

Third, we didn't always have a national bank. The current Federal Reserve system was established in 1913. Notice that it DIDN'T provide economic stability, as was its mandate. We still went through booms and busts (including the great depression). Before 1913, we had a myriad of different banking styles, including no central bank from 1837 to 1862. Do I think we need banking regulations? Sure. Do we need a central bank? No.

Fourth, a return to the gold standard is independent of the federal reserve system. The Gold standard was not revoked until 1971, almost 60 years after the establishment of the federal reserve. The goal of the gold standard is to reduce inflation. I would say that it did it's job pretty well considering the amount of inflation that has happened between 1971 and today.

Finally, trading partners most definitely go to war. The US traded with Iraq (oil and weaponry). Iraq traded with Kuwait. The US invested in Germany before WWII. The examples go on and on. In a global economy, there is more than one way to get at any resource, so it becomes much easier to bite the hand that feeds you. But, it becomes much harder to bite if you have no teeth. By eliminating easy access to money (via deficit spending through the Fed), we can take out a few rows of teeth.

Fanatics

2006-09-08T12:46:00.000-07:00

I love this quote from Ron Jeffries. I found it on a thread in his Agile Forum.

A fanatic is anyone who believes differently from us, and just as strongly.

Response

2006-09-07T20:00:00.000-07:00

Mark made a very intelligent comment on my previous post and I'd like to respond to a few of his points.

1. Repeal the 17th amendment:
This sounds good on paper, but what guarantees that the state congress isn't going to simply choose their Senator soley on party lines for just the possibility of future political favors? Even the lowest of state politicians harbors hopes of being president.

I want the state congress to choose their Senator for future political favors. The point is that the people do what is in their best interest, but the state politicians will do what is in their best interest. What is in their best interest is greater state powers. The people's interest is different. If a Senator lessens the state powers, then the state will not vote him back in. Therefore, the Senator must pander to the state in order to be re-elected. Why is that important? Because state's don't care about gay rights, flag burning, and national health care. State's care about schools and roads and infrastructure. All of the stupidity that is pure popular pandering goes away.

2. I like the idea of taking away the presidential election from the idiot masses who decide solely on superficial traits of candidates ("He's a normal guy who I think I could have a beer with." Who the hell wants to have an average person in the most powerful position in the world??). Anyway, I digress. The problem with this is that you're assuming that the electoral college will be composed of people who are more intelligent than the masses as well as unaffiliated with any political party. That's a tough thing to find I suspect.

I do believe that the electorial college will be slightly more educated than the typical voter, but that's not the main benefit. The main benefit is that the electorial college has no constituents. They don't get paid, they shouldn't get bribes (having fewer people will allow more scrutiny on their financial affairs), and they have no real reason to want to get re-elected. Therefore, they won't pick a president because he promises more welfare or free healthcare. People pick a president because he promises entitlements or "No new taxes" or whatever. They vote in what they think is their best interest (unfortunately, they don't understand the consequences). The electorial college could safely ignore those issues and pick a president based on what is best for the country. Since they don't care about re-election, they are free to make more intelligent choices.

3. Let's go back to the barter system. Most politicians really have nothing to offer other than words, so that should sufficiently weaken the ever-growing hegemony those in power represent. :-)

I believe a return to the gold standard is very similar to going back to a barter system. By preventing the devaluation of the dollar because of deficit spending, we can force politicians to tax us explicitly instead of through inflation.

Waiting on the World to Change

2006-09-07T07:13:00.000-07:00

I really like John Mayer. Especially his new song. However, I have to disagree with his approach. First, the song:

me and all my friends
we're all misunderstood
they say we stand for nothing and
there's no way we ever could
now we see everything that's going wrong
with the world and those who lead it
we just feel like we don't have the means
to rise above and beat it

so we keep waiting
waiting on the world to change
we keep on waiting
waiting on the world to change

it's hard to beat the system
when we're standing at a distance
so we keep waiting
waiting on the world to change
now if we had the power
to bring our neighbors home from war
they would have never missed a Christmas
no more ribbons on their door
and when you trust your television
what you get is what you got
cause when they own the information, oh
they can bend it all they want

that's why we're waiting
waiting on the world to change
we keep on waiting
waiting on the world to change

it's not that we don't care,
we just know that the fight ain't fair
so we keep on waiting
waiting on the world to change

and we're still waiting
waiting on the world to change
we keep on waiting waiting on the world to change
one day our generation
is gonna rule the population
so we keep on waiting
waiting on the world to change

we keep on waiting
waiting on the world to change

Now, the analysis
The sentiments are good, but he misunderstands a fundamental part of human nature. The elite that are corrupting our society now will hand their corruption to their chosen successors. Just because those successors are from our generation doesn't mean they will be any less corrupt. They will continue to attempt to plunge us into a feudalistic society with them at the helm. The fact that we're "waiting" just makes them smile broader. They know we're powerless to stop them so they're taking full advantage of it. Our freedoms have been tromped upon. Our civil liberties abolished. We have our own version of the SS (we call it Homeland Security - anyone notice how these guys go after child porn? No one complains because we all know child porn is bad, but how is that homeland security? It's not. It's the start of our own version of the secret police.) Why will our generation act any differently? The fringe, artistic types such as John Mayer have never supported war or abdication of civil liberties; however, their generations didn't set things right. Why does John think his will? He's completely wrong. Instead, he's promoting the attitude that suits the would-be dictator's perfectly. He's sitting back and watching it all happen. Eventually, it will be too late to stop it.

What can we do to stop it? We have to take away their power base. Of course, we can't rely on them to do it, because they like their power base. Instead, we have to use the one constitutional outlet that they haven't taken away. We need a 2/3 majority of the states to support certain constitutional amendments.

I propose three amendments that should erode the power base of those in charge.
1. Repeal the 17th amendment. This amendment took away states rights and consolidated power to the federal government by moving the election of the senators to the people. Previously, the states chose the senators that represented them. This made it far less likely that a media campaign could buy an election. It also ensured that the person would actually support the state instead of what made them electable. Now, it is all too easy to support a law because it is "popular". Since you only answer to the people, that is all that matters. The Senate is no more than a balanced House of Representatives. Instead, it is supposed to represent the states. Senators would have a much harder time revoking states rights if they had to answer to the state congress.
2. Make the party nomination of presidential candidates AFTER the election of the electorial college. Furthermore, electors should not be allowed to express allegiance to a political party. Currently, the population, not the electorial college, elects the president. This is NOT how it was designed to work. The writers of the consititution knew that the general population is too stupid to choose the correct presidential candidate. Therefore, the general population should choose a bunch of smart people, who choose the president. This has been lost on today's generation. We have to bring back that purpose. The popular vote for a president should never be taken.
3. We must erode their monetary control of our society. The last amendment should abolish the federal reserve and return us to a gold standard. For the reasoning behind this, I would recommend Griffin's The Creature from Jekyll Island. It is a very informative (and very large) book about the history of the federal reserve, fiat money, and fractional reserve banking. It shows how control of the money system directly leads to a controlling, manipulative, feudalistic government.

We have to stop waiting on the world to change and use what power we have as a people to ensure our future.

Cultural Progression

2006-09-02T17:49:00.000-07:00

How do we, as a culture, define our differences with previous cultures. Do we define it by our use of technology? I don't think we can. There are cultures that have advanced technology, yet have similar cultures to their ancestors who didn't have such technology. I think we have to find something that shows motion, not advancement. To that end, I propose we use music. It appears to me, that music is the definition of culture. In other words, by sharing music, you share your culture. By blending music, you blend your culture. Furthermore, music is always changing and adapting. It blends the past into something completely new and unexpected. Music seems to define our progression. Music defines our culture. Explore that concept and let me know what you think.

Generics

2006-08-12T18:31:00.000-07:00

Boo doesn't have generics. This makes me sad. Since I want a strongly typed matching solution, I _really_ want generics. I also want macros. ARRRRRGGGGG! Why won't people give me EVERYTHING. One option is to use arrays instead of lists. Another option is to add generics to the language. I think I'll start with the first and then migrate to the second. That should be sufficient for my needs.

Ok, now on to the O/R mapping.

First, since this is all about types, we're going to add the type information for (most) things in the database. Why, you ask? Shouldn't we know if it is a FirstName or a LastName because we have knowledge of the table? Yes, that is correct, but you're thinking too simplistically. In true OO fashion, FirstName and LastName will be nothing more than base classes. We will end up with an AsianFirstName, AngloFirstName, HispanicFirstName, etc... The same is true for last names. Then, when we consult our statistics, we'll be able to use statistics based on the frequency of the name within its ethnic culture (and also within the geographic location). Therefore, we want to be able to generate and store this extra type information. In addition, we'll want to use the type information when comparing names with the matching engine. We might use a completely different function when comparing a HispanicFirstName to an AngloFirstName as we would a HispanicFirstName to an AsianFirstName (auto-reject, anyone?). By emploring multi-method dispatch on the type information, we can quickly choose the right matching logic.

But enough skipping ahead, back to the O/R mapping.

Obviously, each Element will be stored in its own field. It will have an associated type information field. It may also have a pointer into a metadata table. I'm not sure on that one yet, we'll have to see what sort of metadata we will keep that is outside of the type system.

An entity becomes a little more complicated. Remember that an Entity is a collection of other entities, groups, and elements.

Let's look at two different Entities:

class Name(Entity):
first_name as FirstName
last_name as LastName
middle_initial as Nullable(MiddleInitial)
name_suffix as Nullable(NameSuffix)

Wow, what's that Nullable thing? Well, the type system should include whether or not the field can be blank, and Nullable is just as good a choice as any. I'm really starting to want to do this project in O'Caml. I'm getting very close to breaking open the docs on F#. Of course, now that I think about it, C# might be a good choice. I wouldn't need to modify the parser if I had introspection, which C# gives you. Plus it is strongly typed and has generics...hmmm...I had forgotten introspection...drat!

Ok, back to the task at hand.

In most cases, the Name entity will have a Name table. Each element within the entity will correspond to a field in the table. There will also be the associated type field (and perhaps metadata fields). Each record in the table will also have a unique, primary key.

That was easy...

Now, for a more complicated example:

class Person(Entity):
name as Name
address as Address
ssn as Nullable(SSN)
birthday as Nullable(Date)

For a person we will have a unique primary key, but we will also store the primary key of both the name and address information. The ssn and birthday elements will be stored "in-line" like the name elements were in the previous example.

Of course, we might want to force denormalization of the table...we could try something like

class Person(Entity):
[inline]
name as Name
address as Address
...

Now, name has an inline attribute and will not go in a separate table. Instead, the name fields will be placed in the Person table. However, when we extract the Person object from the table, we'll extract a Name object as well, so you can't tell the difference from the user side.

I'm hesitant to allow an [inline] attribute, because you get to the same point as with C++ and its inline modifier. The compiler can't inline without you telling it, so you're forced to make decisions that the compiler should be able to make. Therefore, if we have an [inline] modifier it will be more like "auto" in C++, a hint but the compiler can do what it wishes with regards to inlining. Hopefully, it's usage will vanish just like auto's.

Ok, next time we'll look at the O/R mapping of groups. I'm still not using the mailing list from SF because I sent things to it that I never got back, so I'm waiting until I have a successful test run before I move there for good.

Sourceforge Site Available

2006-08-12T08:06:00.000-07:00

You can now go to The STARS Sourceforge Site and sign up on the see-stars-devl mailing list. I hope to make most of the technical discussions through that list so that they will be archived and open for discussion. I will also post previous blog entries to the mailing list for historical purposes.

SourceForge site

2006-08-11T07:02:00.000-07:00

http://see-stars.sourceforge.net will be the sourceforge site. It has been created and I am in the process of getting someone to set it up ;-)

Secondly, I'd like to discuss how the type system will interact with the database. First, I said that we're going to be strongly typed. This is not just fancy terminology, this will affect how the database is structured. For instance, we might want to subdivide names for etnicities. John Doe might get the standard US ethnicity, but Wing Fe might get an asian ethnicity. This can be represented by using subtypes. Therefore, this type information must be stored in the database for fast access. In addition, we might have types for strongly cohesive groups, loosely cohesive groups, etc... (perhaps even a composite group that composes multiple strongly cohesive groups so you can see the heirarchy).

But wait! You say. If we're only doing updates then it won't take too long to create all this information, but our initial database population will take FOREVER! People will get tired of waiting! To that, I say, you're absolutely right. That is another beauty of callbacks. We're not going to do it for the initial population. Instead, we're going to use reasonable defaults, but we're going to allow for processes to continually improve the data. I think consumers expect this. They want their data fast, but they also want it right. They hope that over time their data gets better. To ensure that, we'll have reasonable defaults (so, they won't get the Asian/American matching function, they'll get the statistically based one), but when we correct that decision later, we'll let them know through the callbacks. So, they can make their business decisions quickly and then revise them when the situation merits it.

Of course, if they want to wait around, they definitely can, but we need to be adaptive and fast and continuously improving!

Two quick things

2006-08-10T21:22:00.000-07:00

1. All operations must be idempotent. I'm not sure (yet) how to enforce that...it may just be a really strong suggestion.

2. Versioning will be a big part of the system. We need to be able to add fields to an entity and remove fields from and entity, inline an entity (more on that later) and extract an entity. I'm sure there are a number of "refactoring" tools that come from this, but I want them FIRST, not "when there is time." For instance, if I want to add a Title to a Name, then that needs to be as easy as adding title as Title to the Name class and running an upgrade program with an optional map function to create the title given the name (the map could set them all to a default (blank) title or it could try to guess a title of Mr or Mrs based on a derived gender).

Right now, I know I want automated upgrades when I
a) add a field
b) remove a field
c) inline an entity
d) extract an entity
e) add/change the validation method
f) add/change the normalization method
g) add an implied attribute

Also, we better darn well be able to downgrade!!!!!

Creation

2006-08-10T18:37:00.000-07:00

Now that we can define the objects (though not rigourously, that's coming later), we need to know how to create them. Obviously, object creation could possibly mean invoking the database for lookups and the like, so it needs to be well abstracted. In this case, we'll use the abstract factory pattern to create factory objects which will create our entities. For example, if you define the following entity:

class PersonAtAddress(Entity):
name as Name
ssn as SSN
birthday as Date
address as Address

Then you will end up with the following abstract factory

class AbstractFactory:
def getNameFactory:
...
def getAddressFactory:
...
def getPersonAtAddressFactory:
...

class PersonAtAddressFactory:
def Create(name_key as Name.ID, ssn as SSN, birthday as Date, addr_key as Address.ID):
...

Now, we have a consistent, programmatic way to create entities. We can wrap these calls in CORBA or SOAP or whatever, but the foundation is solid.

Next time, we'll start looking at how the objects map to a relational database.

Two Things

2006-08-09T21:50:00.000-07:00

I'm pretty sure of two things at this point. First, the name of the system will be the Staticly Typed Advanced Recognition System (STARS). I hope to get a sourceforge site for it up soon.

Second, the system will be written primarily in Boo and run on mono. Boo has all the right things for this project.

1. Strongly Typed
2. Type Inference
3. Macros
4. User defined compile steps (this will be very useful when creating the database schema from the source files).
5. .NET/Mono compatible - at some point people will want to run their own code, there is a likelihood that the code will be .NET.
6. Clean syntax - based around python (I prefer Ruby, but...)
7. Duck typing
8. Multi-thread capable
9. Functional + Object Oriented

As soon as I get the SF project up, I'll post a link to it here. I'd like to write the specifications in the project's mailing list.

Callbacks

2006-08-09T20:05:00.000-07:00

Callbacks are the key to a good recognition system. A typical batch recognition system forgets about the importance of letting consumers know as soon as information is available. However, this is the lynchpin to a good recognition system.

Let's assume that a typical use case is the following:

1. Run a large file through the system to create a repository
2. Run the files through the repository to ensure correct linkage
3. Rinse and repeate monthly

You have to run the file through twice because you don't know what might happen later in the system to change one of your records. This is because the system is not set up to tell you about events.

If, instead, we allowed the sytem to tell you about important things that are happening, you would be able to complete your run in one pass. So, what needs events. Well, first let's say that we'll use a publish/subscribe mechanism so that only those events that we're interested in will be delivered to us. Second, let's say make the rule that anything that could have an impact on the end result should have an event fired. That means that any time an Entity or Group is created or deleted as well as any time an Entity is moved from one Group to another. I would say that Element updates should be allowed to have events, but not forced to. It could be that updating the salary field doesn't affect anything and you don't need that information to be disseminated.

There are lots of optimizations you can do to make this fast and I don't want to get into those right now, but suffice it to say that the event/callback mechanism can make for an extremely flexible (and efficient!) system.

Obviously, the code for the callback won't be in the same file as the code defining the entities. However, we may want to augment the event with some information at event generation time; therefore, we allow the override of the OnX methods (where X is something like Consolidation).

For example:

class Consumer < Group
def Consolidation(Group other):
if ...:
consolidation_reason = ...
elseif ...:
consolidation_reason = ...

def OnConslidation(ConsolidationEvent event):
event.reason = conslidation_reason

I'm not sure, but you might even be able to suppress events...I don't necessarily like that, but it could come in handy.

Adding operations

2006-08-09T19:13:00.000-07:00

First, for the sake of this post, let's change the syntax a bit. Instead of saying

Entity X

We're going to say

class X < Entity

Basic types, like FirstName, will become less basic and will inherit from Element (or in this case, a derivitive: StringElement)

class FirstName < StringElement

Groups will go from the generic Group(PersonAtAddress) to

class PersonAtAddress < Group

Now, this is not going to be the final syntax, but I want you to think of it as inheritance, because we're going to overload functions.

For instance, an Element should know how to validate itself. A simple example might be

class FirstName < Element
def validate:
return representation =~ /[a-zA-Z-]+/

A more complicated example might make a SOAP call to the validation server defined for that type (we'll see how to do that in a later post).

Elements also need to know how to normalize themselves. For instance, a name might wish to be represented in all upper case:

class FirstName < StringElement
def normalize:
representation.upper!

Another operation you're probably screaming for by now is creation. In this case, the StringElement does the right thing for you, it sets the internal representation to a passed in value. However, you might want to do more. For instance, you might want to keep a map of how often you see each first name to handle statistical based maching. Therefore, you want

class FirstName < StringElement
static Hash seen # would be @@seen in ruby
def initialize(String value):
super(value)
seen ||= new Hash(0)
seen[value]++

Other methods might include update and clear.

For Entities, we need the following operations:

initialize - pass in a value for each of the "member variables" and assign them if they are consistent. Otherwise, throw an exception.
validate - validate the state of an entity
update - update one of the fields of an entity

Update is the most interesting because we could update one or many of the fields. I think it might be interesting to use nil for fields we don't want to update, but I'd rather not. Perhaps a hash? But I don't want to miss a field on accident, and I'd like it to be "compile-time" checked. So, we're back to nils.

class Name < Entity
FirstName first_name
MiddleName middle_name
LastName last_name
NameSuffix name_suffix

def update(FirstName fn,
MiddleName mn,
LastName ln,
NameSuffix ns):
begin_transaction:
first_name.update(fn) unless fn.nil?
middle_name.update(mn) unless mn.nil?
last_name.update(ln) unless ln.nil?
name_suffix.update(ns) unless ns.nil?
rescue => { rollback } #undo all operations in the transaction (maybe a validate fails?)

I'm fairly convinced that a transaction is the right way to handle this situation, but I'm not convinced of the syntax, there are definitely other ways to handle it. For instance, you could have an updater that makes the determination based on the exit strategy of the function.
FirstName::Updater updater(first_name, fn)
It could also handle the nil? case. If the function exits normally, the updater commits - otherwise it rollsback. Regardless, a transaction is needed for exception safety.

You may also delete an entity. I imagine that this should return a boolean on whether or not the delete should succeed, but delete's probably shouldn't fail.

A Group has some additional operations. Since a group is just a collection of entities, it may have an entity added to it or removed from it. It addition, it may also have a list merged into it or part of another list sliced into it.

Let's look at each operation in the abstract:

Add:
original list -> [A,B,C] value -> D new list -> [A,B,C,D]

Remove:
original list -> [A,B,C] value -> B new list -> [A,C]

Merge:
original list -> [A,B,C] value -> [D,E,F] new list -> [A,B,C,D,E,F] new value -> []

The merge adds all of the elements of the value into the list and deletes them from the value.

Splice:
original list -> [A,B,C] value -> [D,E,F], 1, 1 new list -> [A,B,C,E] new value -> [D,F]

The splice takes an array and a begin and end offset and adds those elements to the new list while removing them from the old.

The merge we will call a consolidation and the splice we will refer to as a split.

An important property of a Group involves it's MetaGroup. The MetaGroup is the Set that consists of all the instances of the Group.

So, let's say we have a Consumer Group. We want to say that a consumer can not appear in more than one group. That means that the order of the union of all groups is equivalent to the sum of the order of all groups. To do this, we say that for every group, it's MetaGroup must be a true Set, and cannot include duplicate entities.

Now, back to the operations. Each one of these operations must take place in a transactional environment. For example, an update can fail because of an implied field mismatch.

What's an implied field? A field in a group may be declared strongly or weakly implied. I'm not sure how this declaration will take place (I hate the .NET attribute syntax). However, once it is so declared, it will enforce conformance for all the elements in a group. A weakly implied field will ensure a no conflict match for a field across all the entities in a group. So, if we say that NameSuffix is weakly implied for the Consumer Group, that means all Consumers in the same Consumer Group must have the same Name Suffix (or a blank one). A strongly implied field removes the ability for blanks to match.

Ok, this post has gone on long enough. In future posts, we'll return to the formal specification of these operations.

Type safe recognition

2006-08-09T12:40:00.000-07:00

I believe that recognition (part of Customer Data Integration) can (and should!) be made strongly type safe. Basic types (in the US) might include FirstName, LastName, SSN, Street, CompositeStreet. More advanced types would include an Entity (a collection of basic types) and a Group (a collection of entities).

Notice how this mirrors a programming language. A basic type would be something like an int or float. An entity is like an object, and a Group would be a collection of objects (think an array).

This leads to a few interesting questions. Let's consider the following:

Entity Name:
FirstName first_name
MiddleName middle_name
LastName last_name
NameSuffix name_suffix

Entity Address:
CompositeStreet street_line_1
CompositeStreet street_line_2
City city
State state
Zip zip

Entity Person:
Name name
SSN ssn
Date birthday

Entity PersonAtAddress:
Person person
Address address

Entity Consumer:
Group(PersonAtAddress) occupancies
SSN preferred_ssn
Address preferred_address

At this point, we have types for our recognition system that can be manipulated and understood by both humans and computers. We can further augment them. I'll work on describing the augmentation/annotation of the types in the next blog.

Questions:

Should an entity be allowed to contain more than one group?
Should an entity be allowed to contain another entity that contains a group?
For example:

Entity Household:
Group(Consumer) members
Address preferred_address

More to come!

What to do

2006-06-10T13:14:00.000-07:00

My old job gave me many ideas on how a company should be run. The second job I took, at the beginning of this year, changed some of those. Basically, this blog was a running commentary on things I wanted changed at work. With my current job, I have no complaints. It makes it hard to write about. We do code reviews, unit testing and integration testing. We do some pair programming, when it makes sense. We have continuous integration and we hire smart people. We try to do more with less quantity and more quality. It is, in many respects, an enviable situation. So, I'm going to start posting more at Thoughts of He and less here, because I don't have a lot to gripe about, anymore. What a great feeling that is!

I'm Back!

2006-06-06T19:14:00.000-07:00

I'm back with all new material! How cool is that!

My last employer blocked Blogger, so I stopped posting, since it was a pain to get around the firewall. However, my new employer is much more lenient in what they allow.

What have I learned? What haven't I learned is a better question. My previous job, which lasted all of 5 months, taught me TIBCO and Java/J2EE. However, what I really feel like I took from there is the value of logging and some new techniques on how to retain information. I also learned what management should really be like (and what it shouldn't!). I learned how to do more with less, and how to prioritize based on ROI instead of a manager's whim. All in all, it was a very positive experience and I hope we cross paths again someday.

In my current role, I'm learning how productive one can be when all distractions are taken away. I'm also learning how to test properly and ensure the software works correctly. This is also more "mission critical" software, so I'm getting my first exposure to that side of things.

This employer is also away from my home state, Arkansas, so my family is going through a transition period. I'm not expecting it to be easy, but I'm sure we'll pull through.

Until next time!