Data Mining: Text Mining, Visualization and Social Media

The State of Hawai'i Demands a New Search Engine

We will soon be embarking on a short trip to Hawai'i. Naturally, I'm turning to search engines to find out about the best beaches to go to. However, it turns out that this simple problem - where to go on vacation - is terribly under supported by today's search engines.

Firstly, there is the problem with the Web Proposition. The web proposition - the reason for traditional web search engines to exist at all - states that there is a page containing the information you seek somewhere online. While there are many pages that list the 'best beaches in Hawai'i' as the analysis below demonstrates these are just sets of opinions - often very different in nature. An additional problem with the Web Proposition is that information and monetization don't always align. Many of the 'best' beaches pages are really channels through which hotel and real estate commerce is done. Thus a balance is needed between objective information and commercial interests.

Secondly, beaches are not considered local entities by search engines. While the query {beaches in kauai} is very similar in form to the query {restaurants in kauai} the later generates results of entities of type <restaurant> while the former generates results of entities of type <businesses that have beach or kauai in their name or associated content>. While local search sounds like search over entities which have location, it is largely limited to local entities with commercial intent.

Finally, there is general confusion due to the fact that the state of Hawai'i contains a sub-region (an island) called Hawai'i.

To get to the answer to my original search query, I reviewed 8 sites which resulted in a search on Bing or Google for the query {best beaches hawaii}. I then reviewed each of these and created a spread sheet tabling all the beaches and whether they were voted for by the site.

Of the 57 beaches that were mentioned on at least one site, the average number of mentions was 1.89. This indicates a general lack of consensus regarding which are the best beaches. In fact, most beaches (38 out of 57) have only a single vote. Consequently, while there might be a set of pages returned by search engines for queries looking for such information, a user will be reading - in isolation - very different opinions with no aggregate view summarizing them.

The top beaches are summarized in the following table showing the beach and the total votes.

Search engines could do a far better job by:

1. Generalizing local search to include any entity which has location, not just commercial entities.
2. Leveraging editorial content (like that reviewed in this post) so that variance may be exposed to the user but aggregates can also be synthesized.

In addition, there is a very large opportunity here in analyzing the content associated with these local entities to determine which beaches are best for different activities, their accessibility, and so on.

When Data Mining Goes Horribly Wrong

Historically, the local search space was defined by aggregates of business listings purchased from companies whose original focus was various types of advertising and direct marketing. As the space has evolved, search engines have looked at ways to gather better data and, importantly, to merge different sources of data into a single unified view of the restaurant or business being indexed and served as the result of a query.

Consequently, when you see a details page - either on Google, Bing or some other search engine with a local search product - you are seeing information synthesized from multiple sources. Of course, these sources may differ in terms of their quality and, as a result, the values they provide for certain attributes.

When combining data from different sources, decisions have to be made as to firstly when to match (that is to say, assert that the data is about the same real world entity) and secondly how to merge (for example: should you take the phone number found in one source or another?).

This process - the conflation of data - is where you either succeed or fail.

Take this example from Google's local search product.

The entry is for a company called the West Seattle Blog - certainly one of the best hyperlocal blogs I've come across. This is clearly the identity of the corporation that publishes the popular hyperlocal blog covering news and events in the West Seattle neighborhood.

As the places page indicates it is an owner verified listing, which means that the business owner has confirmed and contributed some of the data.

However, because Google gets data from many sources, it has conflated these additional data sets with this authoritative listing. One of the local entities that it has conflated with the West Seattle Blog is the West Seattle Bowl - a bowling alley in the same neighborhood but at a different address. While it is easy to see how this has happened (the names are identical apart from a few difference between the words blog and bowl which could easily be accounted for by a typo on the part of either data provider) it is unusual in that the addresses of the entities and many of the other features conflict.

By adding the attributes of the two businesses together, we see that the hybrid entity has the categories 

 

Again, due to the mashing together of the data, the images - for a blogging company - are actually those for the bowling alley. In addition, a search on Google for 'west seattle bowl' brings up this listing and no listing for the bowling alley per se.

Because Google's local search, like most local search companies, provides reviews for businesses, this search result contains snippets of text reviewing the company. But compounding the problems of mis-associating these two entities, because the blog itself posts reviews about other local businesses, these too have been associated with the Blog / Bowl informing the user of the great chinese food, etc.:

Another feature of this result is that there are links (listed under reviews) to articles in the Seattle PI (a local newspaper). I imagine these have come about due to the journalistic nature and linking of the West Seattle Blog. However, the article one immediately reaches via the Seattle PI link on the page is entitled Shooter in West Seattle slayings reportedly had mental problems - not exactly ideal copy for potential customers of a bowling alley in that neighborhood.

I certainly believe that the mining of web content and the inference performed on multiple signals of data are two crucial technologies in the local search space, and I have plenty of respect for what Google has achieved in these areas. However, this example (which I came across via some original local search I don't recall) just seemed like an amazing example of a mutated associated graph with interesting consequences worthy of sharing.

Language Really Does Matter For Search

While most pundits regard the deep, formal semantics promised by the likes of Powerset as not important to search I feel that I am personally finding search dead-ends in my long tail queries that clearly indicate the need for this type of feature. I will commit the sin of using a single example to support my point.

The query 'embedding javascript in feeds' returns results on Google for using javascript to embed feeds in HTLM pages. While there are only 4 words in the query the order of these words and the interpretation of the word 'in' are vital in getting the results I'm looking for.

Perhaps there are no actual pages online that will answer my query and the incorrect (they are not alternate, they are wrong) interpretations are backfilling. But this is useless to me as a user. I'd rather know that the engine understands what I'm looking for and can tell me 'you won't find what you are looking for in our index.'

For clarity, the issue I'm interested in here is the behaviour of most feed readers of stripping javascript and other attack vectors from RSS and Atom feeds. I know there are resources out there that discuss this.

Update : here is a suitable hit for this query : element should not contain script tag from the w3c's feed validator documentation.

Excel-ence in Search

These days, I find myself executing many complex queries and - like everyone who is employed by a search engine - maintaining my search behaviour as far from the norm as possible. My focus of late has been in exploring the world of excel documents available online. Consequently, I've been looking at the difference in search experience between Google and Bing.

Firstly, to find excel documents, one can execute a 'filetype:xls' query in the search box. This works on both Bing and Google. Right there, one is exposed to major differences. Bing estimates it has 38, 100 hits, peanuts compared with Google's claim of 18, 000, 000.

Both Google and Bing provide some ability to inspect documents without having to load the actual excel data. The semantics are, however, a little different. Bing's 'cached' page (which all results appear to have) is actually an HTML version of the excel document. This is very useful for making quick judgments about the value of the hit. Google has both 'cached' and html versions of the document.

From the point of view of intuition, I find the Google design to be a little simpler, being explicit about cache and html viewing.

However, the problem with Google's implementation is that their cached pages are not always present:

In addition, not all Google pages have a 'View as HTML' option. So on the one hand you have fewer results in a less intuitive but consistently implemented interface, and on the other, a far larger collection with clearer semantics but with inconsistent implementation.

Comparing the HTML views of the spreadsheets, I find Bing's to be a little better, with Google's rendering often appearing with reams of whitespace and strangely repeated elements.

Unfortunately, I don't even believe all of the above summary. If you include a search term in the query - 'filetype:xls per' - you get back from Bing an estimate of 2, 810, 000 results, and from Google 828, 000 results. Who knows which of these numbers is correct - but Bing's indication of a super set of the more general 'filetype:xls' query is troubling.

Much of the evaluation of search engine technology focuses on the 'head' - do they get searches for movies right, do navigational searches for well known brands work, etc. However, I think by looking in the niche areas one can get an understanding of the rich opportunity that lies in the data available online as well as the manner in which this opportunity challenges the popular optimizations of search engines.

Search, Semantics and Shopping in Paris

It is quite common, in the social circles of the technorati, to observe individuals madly accumulating piles of random household goods while rapidly snapping away with mobile devices in order to demonstrate the quality of applications like Google's goggles, or Bing's iBing. These applications, among other things, provide image based search. That is to say, using images as input to search.

On one such occasion, I and a friend were testing Google and Bing's abilities with a certain CD cover: Martino Tirimo's recording of Debussy's Suite Bergamasque. The CD cover features Basile Lemeunier's "Shopping in Paris" and is pictured to the left.

Imagine our surprise when using this CD cover in image based search brought (I'm sure you've guessed it) the book "April Lady" by Georgette Heyer, pictured below.

Of course, the confusion was caused by the assumption of unique artwork used on covers. The Google application faired better of the two as it has access to a larger database of possible matches. This database covers not just products (that can be keyed off cover art), but also art works (possibly via online poster retailers). Bing, on the other hand, was only aware of the book. The features used to key the products are, firstly, overwhelmed by the nature of the artwork and, secondly, not intended to distinguish between types of objects. They don't 'see' a CD cover or a book or a poster.

This seemed like an interesting issue, and I bookmarked it for this blog post. However, in getting the facts straight for writing this, I had to recover the original art work. I had the picture of the CD cover and vaguely remembered the name of the art poster that Google picked up (which I thought to be "Shopping in April"). However, I couldn't for the life of me encourage the definitive information of the name of the picture or the author out of either Bing or Google. 

Searching on Google for "shopping in paris" brings up various lurid images of Parisian consumerism and a certain American socialite. Adding in the terms "fine art" didn't help at all. It was only when I came up with the idea of searching for art poster online stores that I managed to home in on the original picture, and the artist: Basile Lemeunier (France, 1852-1922).

 

 

The Case of the Missing Bagel

Coming back Portland (actually, Vancouver, WA to make it more geographically confusing), we decided to stop by Olympia for lunch. Craving some excellent Panera bread, we searched on Google maps and found a location at 1320 Marion St NE.

Excited to use our iPhone’s ‘from current location’ feature, we dutifully followed the prescribed route to 1320 Marion St.

Now, as Bing map’s awesome bird’s eye view feature shows, this is not a likely spot for a high street or mall style sandwich shop:

In fact, if we had used Bing maps, we would have found the nearest Paner to be located at the similarly sounding 1320 Marvin Rd NE, Lacey, WA.

Did we get it right? Not quite – this first listing is the sponsored link from Yellow Pages.com. Bing’s first listing is the incorrect address:

But, this isn’t a story of us versus them. This is about how data is sourced and proliferates through the web.

Searching on Bing for the incorrect address, we can see that Yellow Pages lists this address for Panda Express, providing the map to remote area. No doubt the source of the data updated the tenant but didn’t check the location (even though the sponsored link on Bing from Yellow Pages is to the correct address!)

Bing Local lists this incorrect address for Panera as well.

CitySearch also lists the Panda Express entry, even though:

Citysearch is a leading online lifestyle guide with the most up-to-date information on businesses, from restaurants and spas, to hotels and retail.

As a number of these listings provide the phone number, I searched on Google to see if there was any sort of reverse look up. Again, like Bing, Google appears to have multiple entries – a search for 360-456-4069 brings up the correct address:

While we often hear about where search will be in the next n years, and chuckle at Eric Schmidt’s need to humour Brin’s master plan we have to acknowledge that there are some basic wins in existing data sets that are simply slipping through the gaps. A big part of the reason is that we (the search industry) has never made any commitment to representing information in any serious manner. A logical representation of data wouldn’t permit the type of confusion we see around the above bread shop (sorry, this phone number is taken – did you make a mistake?).

What’s Up With Search?

I went to see Up with my family this weekend. If a movie is from Pixar, that is enough to recommend it. All we knew about the film was that it somehow involved balloons. The story was classic Pixar – in a way timeless and yet unprecedented.

Of course, you may have seen Up being used in one of the demos for our (Microsoft’s) new search engine: bing. Given that Pixar/Disney obviously named the movie intentionally as a challenge to search engines, I wanted to see what Google did with the query ‘Up’. I guess Google doesn’t like me. After seeing what they did with my previously posted example, perhaps the result for ‘Up’ shouldn’t surprise me:

At WWW2009 in Madrid this year, Tapas Kanungo put together a nice workshop on snippet generation for the web.

Note that though bing’s results are pretty good, the current Live Search results are not too great either. They provide show times near my location (good) but don’t provide a link to the movie home page (bad).

Update – Google appears to have fixed this as well.

Camerons in the Economist

[I'm way behind in blogging, trying to catch up...]

Cameron brings some data to this article in the most excellent Economist regarding some of the behaviours in Facebook. With the pointless rush for many to friend the entire online population, perhaps the most salient point is:

What also struck Dr Marlow, however, was that the number of people on an individual’s friend list with whom he (or she) frequently interacts is remarkably small and stable. The more “active” or intimate the interaction, the smaller and more stable the group.

Another interesting thing about this article. When I searched in Google for 'cameron economist facebook', it clustered the article quoting Cameron Marlow regarding Facebook in the Economist with another article in the Economist about David Cameron, leader of the Conservative Party. I understand the hit, but not the clustering. A basic understanding of Named Entity Recognition would protect the analysis from this type of error. Search has a loooooong way to go...

Simple Tricks, Stretched Thin

When dealing with text, you can get a certain way with simple tricks. But eventually, a lack of any real model comes back and bites you. I recently saw a referal on this blog from a search on Google for

"discovery engine" powerset

Google's results due to the 'AI' used in understanding the query, contained pages which didn't contain 'powerset' at all, but which contained some stem (for lack of a better word) such as 'powers'. You can get the results you intended if you put powerset in quotes as well (contrary to some belief that this is a crazy thing to do).

Discovery Engine, Powerset - both search engines - so, why do I get adverts for 'Find Landrover Parts?' Or more amusing 'Engine Set'.

A Tale of Two Bells

An image search on Google for 'bell' produces (can you guess?) a multitude of pictures of the type of bell that makes a pleasant ringing sound when one calls for afternoon tea, not to mention the more coarse cousins to be found in ships and belfreys.

A similar search on Live's search engine produces (can you guess?) an array of images of people with the name Bell.

Ask follows Google's bias whereas Yahoo does mix object and people, though the pictures of people are not, shall we say, quite what you might expect.

What is interesting about these differences is that there are obvious biases in the search engines in terms of how they disambiguate terms (is it an object or a person that the user intends to find?). However, none of the search engines really acknowledges the ambiguity, nor do they assist the user in dealing with it. Perhaps the best attempt here is in Ask's interactive query completion, however this is far from perfect as typing 'bell' precludes any suggestions that start with a term other than 'bell'. Thus someone with the surname 'bell' is not going to surface at this point in the interaction.