While demoing Live Search at the Web 2.0 Expo, people continually asked the same questions: “What makes Live different?” or “Show me some features that will make me want to switch from my search engine” or the extremely confrontational “Why do you think you’re better than Google?”

If only I had a dollar for every time someone asked me one of these questions when demo-ing Zook (my company’s Mobile search engine) …I would have been richer by at least a couple of hundred dollars!

How do you convinve someone that your search engine is better than Google? How do you convince someone that Google is not the do-all and be-all of search engines? Don’t get me wrong, I love Google. But I do resent the fact that, with their enormous market share, Google has moulded an expectation of what a search engine is and is not into people’s minds; so much so that if even Google itself introduced anything drastically different, it would probably get rejected! How do you convince someone of something when they are already convinced of the contrary? If you run a Web search engine, Mark Johnson offers some advice:

So, after awhile, I started my demos with a caveat about the nature of a search engine: I implored my audience to try out Live Search for a week so that, in the words of the immortal Lavar Burton of Reading Rainbow, “But, you don’t have to take my word for it.”

This is a great tactic if you are a generic Web search engine. But if you are a more specialised search engine which has been built to answer only a subset of the queries that people go to Google for — but answer them much better than Google does — you are out of luck: people are not too keen on juggling between different search engines for different needs; they want a single box into which they would like to type in a query and get the results. So what is the recourse?

If you have Deep Web content — data that others (read as: Google) do not have access to — you are through. Can there be anything sweeter than a monopoly? This is usually achieved by search engines that own the data they are searching. Usually, most of this data is inaccessible to the regular search engines. Several local search engines are this way. YouTube, the second largest search engine in US, also falls in this category. As do Amazon and eBay and Craigslist. But with the increasing domination of Google and its growing importance in driving traffic, many of these websites are resorting to Search Engine Optimization (SEO) techniques resulting in large portions of their content being made available to be indexed by Google.

If you are a vertical search engine, you can entice people with features that go well beyond mere listing of results. These features can include things like sorting (example: sort by price in product search), actionable results (example: book tickets in movie search), faceted search (example: narrow down by brands in product search — useful for cameras, laptops etc.), community inputs (example: user reviews & ratings in restaurant search) and so on. Often, several such perks are needed to get people to try out your search engine long enough for them to really experience it.

But if you are a drastically different search engine trying to bring in a whole new paradigm of search, you are facing a real tough battle. Wolfram|Alpha learned it the hard way after its recent launch. Powerset faced similar hurdles when trying to convince people of they are worthy of attention. Several other such attempts have been made but none too successfully.

–

Developing a brand new search engine in this Google-dominated world is no more just about coming up with great technical ideas. The technical superiorities need to be market driven. The ideas need to come from a marketing perspective. This does not imply that there is any less scope for leaps of technical improvements, it just means that without a marketing plan to go with them, such improvements will find themselves in obscurity in a hurry.

We came to this realisation at Zook a long time ago. When we did, and started developing our marketing strategy, it was mere good fortune that we found that most of our development until that time would align quite well with the strategy. We were lucky.

–

We like to think of Zook as a lateral search engine i.e. we specialise in some kinds of content unlike a horizontal search engine (most Web search engines) but unlike most vertical search engines we pan across several verticals without going too deep into any one of them. Being this way, we are able to offer several of the features/benefits that are normally the privilege only of vertical search engines — actionable results (examples: buy/download a song, reserve a table at a restaurant, subscribe to alerts), faceted search (examples: restaurant bangalore, ringtones, movies) etc.

Another thing we have going for Zook is that people seem to be more open to trying out alternative search engines on their mobile than they are on their desktops; Google deosn’t yet have a stranglehold on mobile internet users. In most cases, the promise of “exact/precise information instead of a set of links that you have navigate yourself to find the information” gets people excited enough that they are willing to Zook a try.

Zook has a lot of Deep Web content that we source directly from the multitude of our partners. That helps too .

I think everyone has a moral (:P) responsibility to add to the confusion. Only through such attempts can we achieve clarity. This post — an attempt to put in words, my understanding of what Cloud Computing is and is not — is a contribution to that end.

Read on…

It is not possible to use the regular database indexes (usually B-Trees or Hashmaps) for this purpose because they require that you provide the full value of the column you are searching in; in essence they do an equality search. In the blogging software example, the user would then have to type in the entire blog post verbatim in order to find it; even if you could imagine the most patient of users, if s/he already knows the entire post by-heart, why would s/he be looking for it anyway?!

Read on…

But more than the article itself, the debate that ensued in the comments there is very interesting. The “High Scalability” blog published a compilation of some of the interesting quotes from the debate. This compilation provides a great overview of the (admittedly long) discussion.

I would recommend that you read the original article first and then the compilation of the quotes at the High Scalability blog.

Read on…

A program which performs crawling is variably known as a crawler, a spider, a robot or simply a bot. The set of pages from which the crawler starts crawling is known as seed list.

Although it seems pretty straightforward, writing a good web crawler is not very much so. There are a good number of challenges which vary subtly depending on whether it’s a large-scale web crawler or a crawler for a handful of websites. These challenges include: ensuring politeness to the web servers (by observing the widely accepted robots exclusion protocol), URL normalization, duplicate detection, avoiding spider traps, maintaining a queue of un-fetched pages, maintaining a repository of crawled pages, re-crawling and a few more. For large-scale crawlers, one of the most important challenges is to increase the throughput by optimizing the resource utilization, because their coverage usually gets limited by this.

Read on…

It is given that if a person having a disease takes a diagnostic test for the disease, the test returns a positive result 99% of the time, or with a probability of 0.99. Now, for some person picked at random, if the test returns a positive result, what is the probability that s/he has the disease?

You might think that the probability is of course 0.99. But of course that isn’t so. If you did reach the naive conclusion, don’t worry: a lot of eminent scientists and doctors have been seen doing the same mistake (try it with your doctor!)

Actually, there isn’t enough information to give an answer to that question. To be able to get to the answer, we need to know how rare the disease is. Let’s add in this information and work out the answer.

Let’s say it is also known that 5 people in every 1000 suffer from this disease. Put another way, if you pick a person at random, the probability that s/he has the disease is 0.005. Let’s also say that if a person who does not have the disease takes the test, s/he tests positive 2% of the time, or with a probability of 0.02.

Now let’s get down to business.

If we pick a person at random,

let A be the event that the person has the disease, P(A) = 0.005

let B be the event that the person tests positive for the disease, P(B) = ?

let A’ be the event that the person does not have the disease, P(A’) = 1 – P(A) = 0.995

it is given that if a person has a disease, s/he will test positive with a probability 0.99, P(B | A) = 0.99

it is given that if a person does not have the disease, s/he will test positive with a probability 0.02, P(B | A’) = 0.02

We are looking to find P(A | B).

From Bayes’ rule,

P(A | B) = ( P(A) * P(B | A) ) / P(B)

We know everything on the right hand side except P(B). We can calculate P(B) as follows:

P(B) = P(the person has the disease and tests positive) + P(the person does not have the disease and tests positive)

or P(B) = P(A) * P(B | A) + P(A’) * P(B | A’)

or P(B) = 0.005 * 0.99 + 0.995 * 0.02 = 0.02485

Now let’s get P(A | B).

P(A | B) = ( P(A) * P(B | A) ) / P(B)

P(A | B) = (0.005 * 0.99) / 0.02485 = 0.199

That’s less than 2% chance that the person actally has the disease given s/he tests positive for it. And you thought it was 99%!

Assume that boys and girls are equally likely to be born. Let us say that a family has two children. Given that one of them is a boy, what is the probability that the other one is a boy too? (Source: One of Scott Aaronson’s (http://scottaaronson.com/blog/) lecture notes.)

Update: It turns out that after stating this problem this way here, I solved a different problem altogether. Thanks, Nikhil, for pointing it out in the comments. To keep my life simple, I’ll state a modified problem below — the one that I did solve.

Assume that boys and girls are equally likely to be born. Let us say that a family has two children. Given that one of them is a boy, what is the probability that the other one is a girl?

Most people would jump out with 1/2 as the answer. Of course, if the answer was that obvious the question wouldn’t exist. The answer is 2/3. Here I will describe two different ways of arriving at this, as well as the common mistake that leads people to 1/2.

I will start by defining the problem in more formal terms. We are doing an experiment of giving birth to two children. Let GG, GB, BG and GG denote the outcomes that the children born are girl-girl, girl-boy, boy-girl and girl-girl respectively.

So the sample space S is, S = { GG, GB, BG, BB }

Since each outcome is equally likely, the probabilities of the outcomes, P(GG) = P(GB) = P(BG) = P(BB) = 1/4

We are given that one of the child is a boy.

We are interested in the event E that the other child is a girl, E = { GB, BG }

But before seeing the correct solutions, let us see one of the the flawed solutions that generally leads people to the conclusion that the the probability is 1/2.

S = { GG, GB, BG, BB }

P(GG) = P(GB) = P(BG) = P(BB) = 1/4

E = { GB, BG }

P(E) = P(GB) + P(BG) = 1/4 + 1/4 = 1/2

Voila! Of course this is wrong, the first of correct solutions below should make it clear why it is so.

Now the correct solutions:

1. Let’s just count.

S = { GG, GB, BG, BB }

Since we are given that one of the children is a boy, our sample space reduces to

S’ = { GB, BG, BB}

See how GG is conspicous by its absence? That is because the outcome GG cannot occur (wow, a boy cannot be girl!)

In this reduced sample space, our probabilities become

P(GB) = P(BG) = P(BB) = 1/3

E = { GB, BG }

P(E) = P(GB) + P(BG) = 1/3 + 1/3 = 2/3

Huh!

2. Using Bayes’ Rule.

S = { GG, GB, BG, BB }

P(GG) = P(GB) = P(BG) = P(BB) = 1/4

E = { GB, BG }

Let F be the event that at least one of the child is a boy, F = { GB, BG, BB }

We are looking for probability of E given F, P(E | F)

Using Bayes’ rule,

P(E | F) = (P(E) * P(F | E)) / P(F)

Now, P(E) = P(GB) + P(BG) = 1/4 + 1/4 = 1/2

P(F) = P(GB) + P(BG) + P(BB) = 1/4 + 1/4 + 1/4 = 3/4

Because E is the even that there is one boy and one girl and F is the even that there is at least one boy, P(F | E) = 1

So, P(E | F) = (1/2 * 1) / (3/4) = 2/3

The observant might notice that we did not reduce the sample space in second solution. This is no trick: we could reduce the sample space and would still end up with the same answer; try it yourself. But there is no need to do any such thing when using the Bayes’ rule because the fact that the sample space is actually reduced is inherently captured. In fact, many a time it is not possible to simply “reduce the sample space and proceed” — Bayes’ rule really shines then.

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice?

If you have not come across this problem before, intuition would make you say “it just won’t matter” (if not, either you are really clever or your intuition is screwed up; I’d put my money on the later.) It does matter. But I’m not going to tell you which is a better strategy (to switch or not to switch). New York Times has a good simulation of the game, go play the game yourself a few times with different strategies and I assure you that you’ll be stunned. After you’ve played it a few times, click on “How it works” to get a decent understanding of why the best strategy is what it is. If you want a better explanation, both in words and mathematical (using Bayesian analysis), refer to the Wikipedia page linked above.

I do agree with a good number of the points he brings up, but at the same time believe that such a blanket statement is not warranted. I believe that adding more data to a given algorithm does give out better results, especially if the new data is independent and the algorithm is capable of utilizing such data appropriately. But to say that better data is more important than better algorithms most of the time is far-fetched.

Such generalizations usually fall flat in the absence of the unstated assumptions under which they have been made. In the case of Dr. Rajaraman’s post, these assumptions include (but are not limited to): the data that is already available is not representative enough so that more data could add value; the algorithm is capable of utilizing the additional data; the additional data is good, even better, than the existing data.

There is data. There is information. There is a small ’semantic’ difference between the two. Data has an ‘informational value’ which can be described as the information it brings to the system. Additional data, if it does not add any information to the system is more often than not useless. So, more data only helps if it adds to the information in the system. Even where there is data available that can add information to the system, the value of that information needs to be considered. If a lot of additional data adds a marginal value, it might not be worth using that data. That is because processing the additional data requires additional resources in terms of time and machine power, and, in machine learning applications we are usually trying to optimize the resource utilization.

Most simplistic algorithms need to be modified for them to be able to utilize more than one independent sets of data. So in this case, the algorithm is being improved, as well as more data being added. This is the case, for example, with Google’s PageRank: Google decided to use the hyperlink information for ranking web pages but the existing ranking algorithms could not utilize that information, so they improved on them to come up with PageRank. Now, this very example could have been stated in another way: Google came up with a better ranking algorithm that could utilize the social citations of web pages to rank them, this new algorithm needed new data and hyperlink information happened to be that data; it might as well have been the bookmarks of all the people, if cloud computing was invented before the Internet (sic).

At the end of the day, whether more/better data is more important or better algorithm is highly dependent on the particular application at hand.