NYTimes on Crawling the Deep Web

The New York Times has a great piece today on crawling the deep web - the portion of the web that isn't easily accessible to normal web crawlers.

The challenges that the major search engines face in penetrating this so-called Deep Web go a long way toward explaining why they still can’t provide satisfying answers to questions like “What’s the best fare from New York to London next Thursday?” The answers are readily available — if only the search engines knew how to find them. Now a new breed of technologies is taking shape that will extend the reach of search engines into the Web’s hidden corners. When that happens, it will do more than just improve the quality of search results — it may ultimately reshape the way many companies do business online.

Oddly enough, Google published a paper on this topic at VLDB 2008 entitled "Google's Deep-Web Crawl".

This paper describes a system for surfacing Deep-Web content; i.e., pre-computing submissions for each HTML form and adding the resulting HTML pages into a search engine index. Our objective is to select queries for millions of diverse forms such that we are able to achieve good (but perhaps incomplete) coverage through a small number of submissions per site and the surfaced pages are good candidates for selection into a search engine's index. We adopt an iterative probing approach to identify the candidate keywords for a [generic] text box. At a high level, we assign an initial seed set of words as values for the text box ... [and then] extract additional keywords from the resulting documents ... We repeat the process until we are unable to extract further keywords or have reached an alternate stopping condition. A typed text box will produce reasonable result pages only with type-appropriate values. We use ... [sampling of] known values for popular types ... e.g. zip codes ... state abbreviations ... city ... date ... [and] price.

The smart guys over at Kosmix were also quoted:

“The crawlable Web is the tip of the iceberg,” says Anand Rajaraman, co-founder of Kosmix (www.kosmix.com), a Deep Web search start-up whose investors include Jeffrey P. Bezos, chief executive of Amazon.com. Kosmix has developed software that matches searches with the databases most likely to yield relevant information, then returns an overview of the topic drawn from multiple sources. “Most search engines try to help you find a needle in a haystack,” Mr. Rajaraman said, “but what we’re trying to do is help you explore the haystack.”

...

In a similar vein, Prof. Juliana Freire at the University of Utah is working on an ambitious project called DeepPeep (www.deeppeep.org) that eventually aims to crawl and index every database on the public Web. Extracting the contents of so many far-flung data sets requires a sophisticated kind of computational guessing game.

Interesting. I'm going to have to reach out to them to offer our help with Spinn3r (more on our research program shortly).

Spinn3r Sponsors 2009 International Conference for Weblogs and Social Data Challenge

Spinn3r is sponsoring the International Conference for Weblogs and Social Media this year with a snapshot of our index.

The data set was designed for use by researchers to build cool and interesting applications with the data.

Good research topics might include...

• link analysis
• social network extraction
• tracing the evolution of news
• blog search and filtering
• psychological, socialogical, ethnographic, or personality-based studies
• analysis of influence among bloggers
• blog summarization and discource analysis

We're already used by a number of researchers in top universities. Textmap (which presented at ICWSM last year) just migrated to using Spinn3r and Blogs Cascades has been using us for a while now.

The data set is pretty large. 142GB compressed (27GB uncompressed) but you need a solid chunk of data to perform interesting research.

The dataset, provided by Spinn3r.com, is a set of 44 million blog posts made between August 1st and October 1st, 20092008. The post includes the text as syndicated, as well as metadata such as the blog's homepage, timestamps, etc. The data is formatted in XML and is further arranged into tiers approximating to some degree search engine ranking. The total size of the dataset is 142 GB uncompressed, (27 GB compressed).

This dataset spans a number of big news events (the Olympics; both US presidential nominating conventions; the beginnings of the financial
crisis; ...) as well as everything else you might expect to find posted to blogs.

To get access to the Spinn3r dataset, please download and sign the usage agreement , and email it to dataset-request (at) icwsm.org. Once your form has been processed, you will be sent a URL and password where you can download the collection.

Here is a sample of blog posts from the collection. The XML format is described on the Spinn3r website.

Spinn3r 2.2.1 Released

Spinn3r 2.2.1 is out the door.

This is evolution on over Spinn3r 2.2 which has a number of features and fixes suggested by our user base.

New API Methods:

As a result of our recent infrastructure changes, we're now able to provide a more robust feature set to our customers.

Ninety percent of our users are served by our raw crawler API but occasionally there are questions regarding support for a specific weblog, access to archive posts, etc.

These new methods should help improve this situation by making it easier to interact with Spinn3r.

At the moment this functionality is only supported with our permalink interface. We're working on back porting this functionality to our feed API as well.

source.list

Our new source.list API is designed for customers with existing crawlers that want to tie into our spam prevention and ping infrastructure.

The source.list API was designed to help 3rd party crawlers tie into Spinn3r's ping stream and realtime polling and prioritization backend.

Returns an RSS feed with lists of weblogs that have either been found or discovered by Spinn3r or published after a given timestamp.

You can see the source.list documentation for further information.

permalink.history

A number of Spinn3r customers have requested the ability to fetch historical content for specific blogs. This is now possible with our new permalink.history method.

Given a weblog URL, return recently published articles. This can be used to find the most recent results from techcrunch.com, gigaom.com, etc.

Results in recent posts sorted by reverse chronological order.

This is made possible due to the backend database improvements we've been steadily working on over the last year. We're going to port these changes to the feed API shortly. We're waiting to bring more hardware online for this which should take 2-3 weeks.

permalink.status

This provides the ability to obtain the status for a specific post (permalink) within Spinn3r.

General Crawler Improvements

This release also includes the following crawler improvements:

Faster Polling Interval

We've migrated to 45 minute (vs 60 minute) polling intervals for all cyclical feeds and sources. Everything else in Spinn3r is updated in real time when we receive a ping.

We're going to be reducing this to a 30 minute polling interval in the next week or so. We're going to pause at 45 minutes to see if any sites complain and make sure there aren't any performance issues which we have to deal with.

This should be fine as Bloglines has been using 30 minute polling intervals for a few years now and it hasn't caused any problems.

Weekly Indexing of Pinged Weblogs

We've also moved to a mechanism of re-indexing pinged weblogs on a weekly basis. While 99% of blogs in our index send pings correctly there's the possibility of dropped ping due to misconfigured blog host. This could be do either to an error on their part or a temporary network outage.

To correct this behavior we've migrated to a weekly re-index mechanism where we send out our crawlers if we haven't heard from a blog in at least a week.

feed.getDelta supports publisher_type

This was an omission from Spinn3r 2.2 that one of our customers pointed out.

The permalink.getDelta method supported a publisher_type but the feed.getDelta method did not.

Advanced Mainstream Media Feed Detection

Mainstream media support for RSS has always been mediocre at best. Our permalink API was designed to help improve this situation by indexing all recent posts on a given website.

The problem is we would still be missing additional metadata such as the original publication date, author, and title.

It's impossible to discover these feeds because they may be buried deep within the website and many of these sites don't have RSS autodiscovery setup correctly.

Kiplinger.com is a good example. This website has a number of RSS feeds but the only way to find them is to click on an 'rss' link at the bottom of the page, which is a link to another HTML page which contains a set of RSS feeds.

Some sites are even worse. AOL News has a page which lists the RSS feeds but they don't actually link to them - they link to myAOL. They have an RSS feed link when you view the page in a browser but this is actually generated via javascript which (obviously) crawlers can't see.

The solution has been to release a focused crawler for these sites to recursively index pages and attempt to find links to RSS feeds. These RSS feeds are then indexed and used to fetch additional metadata.

We've pushed the first pass of this functionality and are going to be releasing another version of our crawler that allows us to discover even more mainstream media feeds.

Documentation Updates

There have been a number of documentation updates available over on our wiki.

Specifically, the changes around the source and permalink APIs.

More to come...

We're also going to be releasing Spinn3r 2.2.2 which will have more updates in our crawler including additional support for forums and mainstream media feeds and enhancements to our core weblog discovery algorithms.

I suspect that this will be about two weeks before all the backend infrastructure work is complete.

Thanks to Flickr users josef.stuefer, buntalshoot, and Mr Usaji for the amazing photos of the above spiders.

Spinn3r 2.2 Released

Spinn3r 2.2 rolled out the door today.

We've been working on a much larger release which is still pending but wanted to release new functionality out the door for some of our more recent clients.

So what's new?

We've added the ability to register weblogs directly within Spinn3r. All that's necessary is to call a new source.register method with a link to a weblog or any URL that has an RSS feed and publishes dynamic content. Spinn3r will then do the rest. We'll fetch the HTML feed, perform RSS autodiscovery, and then add it to our source list and start crawling in real time.

What's interesting is that this allows our clients to collaborate on weblog discovery. Spinn3r does a great job at discovering weblogs but there are some niche sources where we'd love to have a few more signals to help out in our spam detection.

This also fixes a number of bugs including:

• Our permalink crawler API now adds the ability to filter by API tier.
• We've added better mainstream media site detection.
• A new post:resource_guid field is available within Spinn3r results to identify a unique post
• New publisher types including FORUM, CLASSIFIED, and REVIEW.

It sounds crazy but we've also started a sub-project to allow Spinn3r to also license spam content. We've had a few malware and anti-virus companies approach us looking for a solid stream of real time spam posts. Unfortunately, Spinn3r wasn't setup to provide this as 99% of our customers are only interested in ham.

This adds a new spam_probability backend variable which isn't exposed just yet. We'll allow our customers to add &spam_probability=x.x in their API call to control how much spam they want to receive.

Believe it or not, some customers would like to boost up their signal a bit and add a bit and add more spam as a tradeoff to get a bit more recall.

By default, this content will only be available to the client who registered the source. This prevents clients with niche requirements to index special feeds (search feeds being a good example) without hurting any of our other customers.

Spinn3r 2.5 is also right around the corner. It's taken us a bit longer than we had hoped to bring our new hardware online. You can read about our progress here on my personal blog.

Spinn3r Client Driver for Perl

The guys over at Slaant were nice enough to write an Open Source driver for Spinn3r written in Perl.

They did all the work here and we're immensely grateful that they decided to release it as Open Source.

This is 100% native and uses Expat for XML parsing.

As part of this release I also wrote some notes on client design guidelines. It turns out that 80% of the problems are produced by common implementation issues. Things like using read and connect timeouts, correct DNS caching, UTF-8 encoding, etc.

WWW::Spinn3r is an iterative interface to the Spinn3r API. The Spinn3r API is implemented over REST and XML and documented throughly at `http://spinn3r.com/documentation'. This document makes many reference to the online doc and the reader is advised to study Spinn3r documentation before proceeding further. ...

This module gives your a perl hash interface to the API. You'll need just two functions from this module: `new()' and `next()'. `new()' creates a new instance of the API and `next()' returns the next item from the Spinn3r feed.

Yahoo Extends Semantic Web Support?

Looks like Yahoo is releasing more details about web standards, RDF, and microformat support in their search platform:

While there has been remarkable progress made toward understanding the semantics of web content, the benefits of a data web have not reached the mainstream consumer. Without a killer semantic web app for consumers, site owners have been reluctant to support standards like RDF, or even microformats. We believe that app can be web search.

By supporting semantic web standards, Yahoo! Search and site owners can bring a far richer and more useful search experience to consumers. For example, by marking up its profile pages with microformats, LinkedIn can allow Yahoo! Search and others to understand the semantic content and the relationships of the many components of its site. With a richer understanding of LinkedIn's structured data included in our index, we will be able to present users with more compelling and useful search results for their site. The benefit to LinkedIn is, of course, increased traffic quality and quantity from sites like Yahoo! Search that utilize its structured data.

... and of course a rising tide lifts all boats. I expect this will help out Spinn3r as this just means more structured content for us to index.

They're using the right vocabulary though:

In the coming weeks, we'll be releasing more detailed specifications that will describe our support of semantic web standards. Initially, we plan to support a number of microformats, including hCard, hCalendar, hReview, hAtom, and XFN. Yahoo! Search will work with the web community to evolve the vocabulary framework for embedding structured data. For starters, we plan to support vocabulary components from Dublin Core, Creative Commons, FOAF, GeoRSS, MediaRSS, and others based on feedback. And, we will support RDFa and eRDF markup to embed these into existing HTML pages. Finally, we are announcing support for the OpenSearch specification, with extensions for structured queries to deep web data sources.

Techcrunch has more on the subject and generally likes the direction Yahoo is taking.

Announcing Spinn3r 2.1

I'm very excited to announce that Spinn3r 2.1 is now available.

A number of major new features have been implemented in this release which has taken us more than three months of hard work to get out the door.

We've also finished up another stage of our backend and are planning on buying a few more toys in 2008 which should make things interesting moving forward.

Let's dive into the details.

Full Crawler Support

Our new crawler functionality fetches the full HTML of every post we discover, extracts the body of the post, excluding sidebar and chrome and provides this content under a new API.

Our reference client implements the new API and existing clients should be able to easily port their code to support this new functionality.

This is a major new architecture for us and we plan on expanding support for this moving forward.

Content Extraction

The quality of mainstream media RSS feeds is notoriously lacking. For example, CNN has RSS feeds but they only have a one line description instead of the full content of the post.

This has always been a problem with RSS search engines such as Feedster or Google Blog Search - what's the point of using a search engine that's not indexing 80% of potential content?

We're also seeing the same thing with a number of the A-list blogs. RSS feeds turn into a liability when bandwidth increases significantly every month with each new user. The more traffic a blog gets the greater the probability that they'll enable partial RSS feeds in order to reduce their bandwidth costs and increase click through rates.

Spinn3r 2.1 adds a new feature which can extract the 'content' of a post and eliminate sidebar chrome and other navigational items.

It does this by using an internal content probability model and scanning the HTML to determine what is potentially content and what's potentially a navigation item.

For a visual example, you can see the attached screenshot of a page with content highlighted in yellow. This screenshot was generated by passing our content extraction algorithm over this article on The New York Sun.

This method isn't always 100% accurate. It has a small probability of false negatives for the first few words of a post. As such, it's meant for consumption by algorithms and not by humans.

To increase accuracy we also implement Google ad section targeting and hAtom entry-content which help us focus on the body of the post.

We also support Yahoo's robots-nocontent to help with HTML chrome/sidebar elimination.

About 15% of our content is indexed with these additional methods.

Better Mainstream Media Support

Since Spinn3r 2.0, we've been indexing mainstream news sites such as CNN, the NY Times, etc.

We've improved this support in 2.1 by tuning and performing extensive QA for these mainstream media sites. We've implemented parsers for individual sites such as the NY Times and performed manual audits on more than 600 sites to make sure our crawlers were indexing them at optimal levels.

Expanded Online Archives

In previous versions of Spinn3r we only kept about seven days of content online at any given time. Since most of our customers are only interested in the most recent content this wasn't a problem. As we grow, we're starting to have more and more requests for access to older content.

That's easier said than done though. Spinn3r is currently indexing over 500GB of data. Providing all of our customers with real time access while maintaining adequate performance is a difficult task.

Thanks to the recent architecture updates we've performed we're now able to keep all of our content online. Right now Spinn3r has about 2.5 months of data (around 200GB) online. We're going to be expanding this in future versions to keep all of our legacy content online and available to our customers.

Spinn3r Reference Client

In November, we announced the availability of our Spinn3r reference client for Java.

This has significantly reduced our initial client implementation time. One of our recent clients was able to get up and running under two hours!

Spinn3r 2.1 has an updated reference client which supports all new protocol updates for this release and additional command line options as well.

What's Next?

Spinn3r is growing. November and December were big months for us. We closed 5 new clients and are now used by companies which have raised more than $50M in VC funding.

We're also now being used in production by a number of researchers from top universities including the University of Maryland Baltimore County (my alma matter), University of Washington, and the University of Southern California.

Having so much feedback from multiple parties makes it clear where we need to move Spinn3r in the future.

Having public stats about our crawler is a common request. Spinn3r 2.2 will introduce a lot more statistics about our crawler including the ability to view individual weblogs, total bandwidth usage, total posts per hour, etc.

Comment extraction is also a popular request. We're going to extend Spinn3r to index each individual post and extract each comment as a unique entity with individual title, link, and body for each comment.

Stay tuned. We still have a few more tricks up our sleeves.

Storing the Full Internet

The other day I blogged about Blekko and what it would take to in terms of hardware index the full Internet.

High Scalability responded with some interesting thoughts.

Kevin Burton calculates that Blekko, one of the barbarian hoard storming Google's search fortress, would need to spend $5 million just to buy enough weapons, er storage.

Kevin estimates storing a deep crawl of the internet would take about 5 petabytes. At a projected $1 million per petabyte that's a paltry $5 million. Less than expected. Imagine in days of old an ambitious noble itching to raise an army to conquer a land and become its new prince. For a fine land, and the search market is one of the richest, that would be a smart investment for a VC to make.

The comments are interesting.

Borislav Agapiev made some interesting comments.

"(far) less than 5 PB - a world class index would be 20B pages times 10KB per page = 200TB. This is for page storage, there would be more for storing the index i.e. posting lists. It would depend on size of individual postings and lengths of posting lists but few PB would cover it."

It's more than just the raw page HTML.

You need metadata, previous archived pages, diffs, ngram distribution for text clustering algorithms and duplicate detection and

Also, avg page size in Google's full 'net crawl is 15k. We see similar numbers in Spinn3r.

The bottom line is the storage required is very cheap. BTW, $1M/PB = $1/GB seems too high, nowadays cheap SATA 500GB disks can be had for $100.

Yes.... This is a standard SATA disk or $.2 / GB. However, this is JUST disk not CPU, a redundant copy of that disk, and additional disks for high IO transfer rates.

You need a LOT more spindles to be able to access this 5P. Storing the data is one thing. Making sure it's highly available, fault tolerant, and high performance is a totally separate issue and ends up seriously increasing your costs.

For instance, one can crawl with a good crawler 1M pages/day on 1Mbps bandwidth i.e. 1B pages/day with 1GBps. So with 20Gbps one can crawl entire Internet daily. 20Gbps of crawling bandwidth goes for $100K/mo in the Valley, you can saturate it with , say, thousand cheap crawlers ($1-$1.5K each). I would think that Google spends way more in their cafeteria than that :)

This doesn't include the political aspects. You can't build a full web crawl in one day. You'd be blocked instantly. Crawlers have to be polite.

We spend a TON of time working with blog hosting companies to make sure our crawlers yield to their policies. For example, LiveJournal won't allow us to crawl with more than 10 threads.

Borislav rephrased this by saying that "crawling does not scale" since you don't HAVE to scale it as much as you'd think because you can only build the crawl at a slow pace.

There are other factors here though. Building a web graph, recomputing your ranking algorithm so you can re-prioritize your crawl, serving the content to clients, finding duplicates, all this stuff requires more resources than you initially think.

Of course maybe these aren't actual problems. Building this stuff is fun!

Thoughts on Efficient Crawling through URL Ordering

I'm re-reading "Efficient Crawling through URL Ordering" and a few other papers I've read a few years ago.

Now that I have Skim I can take notes in the PDF directly which is turning out to be amazingly productive.

It dawned on me that I should also blog these notes as well.

First, some background:

A crawler is a program that retrieves Web pages, commonly for use by a search engine [Pinkerton 1994] or a Web cache. Roughly, a crawler starts off with the URL for an initial page P0. It retrieves P0, extracts any URLs in it, and adds them to a queue of URLs to be scanned. Then the crawler gets URLs from the queue (in some order), and repeats the process. Every page that is scanned is given to a client that saves the pages, creates an index for the pages, or summarizes or analyzes the content of the pages.

The authors discuss a number of priority metrics including query driven crawling, pagerank and backlink based crawling.

This paper is a bit dated with the authors noting that the web is about 1.5T in size. The web has grown a bit since then.

Crawl & Stop. Under this model, the crawler C starts at its initial page P0 and stops after visiting K pages. At this point a perfect crawler would have visited pages R1, ..., RK, where R1 is the page with the highest importance value, R2 is the next highest, and so on. We call pages R1 through RK the hot pages. The K pages visited by our real crawler will contain only M pages with rank higher than or equal to I(RK). We define the performance of the crawler C to be PCS(C) = (M•100)/K. The performance of the ideal crawler is of course 100%. A crawler that somehow manages to visit pages entirely at random, and may revisit pages, would have a performance of (K•100)/T, where T is the total number of pages in the Web. (Each page visited is a hot page with probability K/T. Thus, the expected number of desired pages when the crawler stops is K2/T.)

This a useful model for estimating the accuracy of a crawler. Our discovery engine approaches 100% of the connected graph. We then promote these URLs into Spinn3r which are then indexed by our crawler.

Spinn3r by definition is designed to approach 100% accuracy of the crawl with 100% realtime indexing. When a blog is posted we have to index it within 5 minutes for our clients.

For larger crawls, estimations of the efficiency become more important.

...

Query driven crawling also offers additional benefits. Back in the day, URLs weren't generated from mainstream content management systems so it wasn't really possible to extract metadata from them directly:

As we will see, for similarity, we may be able to use the text that anchors the URL u as a predictor of the text that P might contain. Thus, one possible ordering metric O(u) is IS(A, Q), where A is the anchor text of the URL u, and Q is the driving query.

Now, URLs have additional metadata that we can extract. For example, from:

http://feedblog.org/2007/12/25/what-is-wrong-with-icerocket/

We know that the article as published on 12-25-2007. We also know that the title might be "what is wrong with icerocket".

If we were performing a targeted crawl for articles created in 2007 about icerocket this would be an additional way to hint your queue to prioritize this URL for indexing.

...

Their trust metric based crawling (pagerank) is obviously superior to anyone who's researched trust metrics. Their observation that backlink counting metrics behave like a depth-first crawl is accurate and the exact same behavior I've seen with our crawlers.

Announcing Spinn3r 2.0

After nearly a year in development, I'm pleased to announce the release of Spinn3r 2.0.

We've also been heads down working on Tailrank as well and are announcing Tailrank 2.5 today as well.

All of this has been possible due to the sheer amount of work we've invested into our software and hardware infrastructure. We're pretty ambitious and now that we've completed the majority of our infrastructure work we can ship more applications at a faster rate.

This release includes a number of new features which have been requested by our customers over the last year including:

Now indexing to 12M weblogs

When we first released Spinn3r 1.0 we wanted to focus on the core portion of the blogosphere which received the most attention. While this is still a major focus for us, increasing our index to cover more niche topics and user generated content has been a big request from our customer base.

We've built out a complex discovery engine to find new weblogs which takes in a number of factors including publication rate, link analysis, content analysis and other factors to determine if a blog should be added to our index.

While other services claim to support a lot more than 12M blogs we try to focus only on the portion of the blogosphere that publishes at least once per month.

We also spend a good deal of time fighting spam which is also beneficial to our user base.

Mainstream News Crawler

We've added a new mainstream media crawler which indexes the top 10k high ranking news sites such as CNN, the New York Times, and the Wall Street Journal. We expose the full HTML of each mainstream media article within our API, including the article title and additional metadata.

This will also be the basis of new crawling technology for or main index which will help us backfill partial content feeds, extract comments from blog posts, and numerous other features.

Tags

We now index tags in both HTML rel-tag form and within RSS and Atom categories. Not only are tags included in API output but you can also query for a specific tag with the API.

Language Classification

We've implemented an in-house language classification library (based on current research) for analyzing content and determining the underlying language based on the raw text. This allows us to discover the language for a given page or weblog simply by the author's own words.

This becomes very valuable when the language of the blog isn't specified or incorrect due to a configuration error.

Weblog Influence Ranking

Not all weblogs should be considered equal. Certain weblogs have a lot more influence than others.

Taking this into consideration we've created a new ranking algorithm named "influence rank" which represents how successful a blog is at breaking a meme which eventually gets published on Tailrank.

Top Weblog Filtering

Only need the top 1k weblogs? Not a problem! We now expose our influence ranking (and other factors) to the user and filter results accordingly.

This has been beneficial for startups that are working on beta applications and don't yet have the compute capacity to process the blogosphere.

Author metadata

Author data included within the API when available from the source RSS or Atom feed.

This has been requested from numerous customers and is now a default feature in the API.

Ease of Use

We've made the API even easier to implement than before. Implementing the Spinn3r API should be as simple as downloading a URL. In fact, one of our recent customers had one of their interns implement it in their spare time! Not bad!

Free for Research Purposes

Working towards your PhD? Need a copy of the blogosphere for academic use? Not a problem! We're now making Spinn3r 100% free of charge for researchers.

Spinn3r 2.1

There were a few key features that couldn't make it into Spinn3r 2.0 that we're really excited about. We're planning on releasing Spinn3r 2.1 in the next couple weeks which will include some cool functionality (so stay tuned).