CSC3252 Lecture 22

Lecture 22

Mapping the Web

References:

Stross, C.
"The Web Architect's Handbook",
Addison-Wesley 1996, Chpt 8.

Searching The Web

The Web is ENORMOUS!

It can't be searched exhaustively by hand.
It can't be catalogued exhaustively because it is so dynamic.

...it is, in many senses, completely out of control!

Some of the strong points of the web's structure as a 'free for all' publishing house are its weak points for information retrieval.

There is no (practical) way to find all links to a given document
Links cannot be extracted from a document without first retrieving the entire document source
Content / function of a document is not catalogued externally to the document itself (All HTML documents appear just as 'HTML documents' until one is downloaded in its entirety and examined)
The web is not organized in any coherent manner beyond the level of individual site structure ...and even this is not guaranteed!

In the early days of the web What's New and What's Cool pages were maintained by NCSA, Yahoo, Netscape and a few others.
These sites provided a human readable list of new and hand-picked exciting sites to visit.
As the months rolled by these daily pages became larger and larger until they too were unmanagable without automatic tools.
These lists only contained sites which had been submitted to the maintainers, they did not actively seek out new web content to incorporate.

At http://www.altavista.com resides a well known web search engine (Scooter the Spider).
- Scooter actively follows links in the web
- The links gathered by the engine are stored in a database (150,000,000 documents as of May 1998)
- The Lycos database is searchable by keyword
- The web content is also stored in a hierarchical catalogue organized by content
At http://www.yahoo.com resides a well known web catalogue.
- A bunch of humans with nothing better to do investigates web sites submitted to them
- The sites the humans think (in their personal opinion) are worth a look are stored in a database
- The Yahoo database is searchable by keyword
- The web content is also stored in a hierarchical catalogue organized by content
- To access information on the Tour De France for example you might select links: News & Media -> Sports -> Sports Web (A Sport News Site).

Search Engines

A web search engine is usually a piece of software which recursively follows hyperlinks. The software is attached to a database where it stores anything it retrieves.
Web databases may store information such as:
- The document URL
- The document TITLE
- Keywords extracted from the document META tag
  
  <META NAME = "keywords" content = "bees, seas, peas, whys, poetry">
  <META NAME = "author" content = "Philip K Dick">
- The first n characters of the document content
- The entire text of the document content.

Robots, Spiders, Wanderers and Crawlers

The software responsible for searching the web is often known as a robot web-bot, spider or by a similar bug-like name.

Some robots may:

Follow links when they are encountered
Parse HTML source code

These robots are useful for verifying the hyperlinks of a website and checking the validity of the HTML on the site. (They may be useful for a webmaster with a large site to maintain.)

The beginnings of Dorin's URL Muncher ro-Bot (DUMB)

Open a new browser window
Write a new HTML document containing the following attributes of the current document:
- URL
- Title
- Number of hyperlinks
- Navigable list of hyperlinks / URL's

function DUMB(d)
{
	var newWindow = window.open("", "linklist", "width=300,height=300");
	
	newWindow.document.open("text/html");
	
	newWindow.document.writeln("<B>URL:</B> " + d.URL + "<BR>");
	newWindow.document.writeln("<B>Title:</B> " + d.title  + "<BR><BR>");
	newWindow.document.writeln("Number of links in this document:");
	newWindow.document.writeln(d.links.length);
	
	newWindow.document.writeln("<OL>");
	
	for(var i=0; i < d.links.length; i++)
	{
		newWindow.document.writeln("<LI> <A HREF=\"");
		newWindow.document.writeln(d.links[i]);
		newWindow.document.writeln("\">" + d.links[i] + "</A><BR>");
	}
	newWindow.document.close();
}

A call to DUMB is given at the end of this document's source.

DUMB(document);

It is responsible for popping up the new window when this page is first loaded!

Pretty nifty hah!? Don't get carried away though. JavaScript is paranoid about security so this method, as it stands, won't allow you to search the whole web.

Some other robots:

Follow links intelligently
Index the information in the HTML documents
Store URL's and other material as listed in the previous section

These robots are useful for creating large databases of material stored on many different machines around the world for use as web catalogues.

Robots usually work by:

Sending an HTTP HEAD request to a server to see if a file exists
Retrieving the file using a GET request
Saving useful info. about the file contents
Collecting the list of hyperlinks in this file (usually at least 1!)
Adding the hyperlinks to an internal database
Retrieving the next unsearched hyperlink from the internal database...

...repeating the above steps.

Robots must avoid:

Servers that are un-contactable
- Track file requests and avoid contacting servers that don't respond.

Cycles in the web structure

As a point of interest, given the content of the web, what is the likelihood of a small cycle? Very high!

You have a link to your partner's web site and they have one to yours!
You have a link to a researcher's site because your research is in Artificial Life, and they have a link to yours because you have the same interests!
You have a link to a software company becuase you use their product, they have a link to your site because you endorse it.

etc....

Check URL's against previously indexed URL's and avoid traversing the same path again.

Saturating a server with rapid requests for documents
- Don't request multiple documents from the same server in quick succession.
- Set up a list of servers to query, request documents from each in turn. (Delay requests to the one server)
Saturating the bandwidth available to a server
- As previous.

Traversing the List of Hyperlinks

Starting at a location on the web reveals a branching structure which, if cycles are avoided, is essentially a tree.

There are two methods for traversing a tree:

Depth First Traversal
1. Start at a node
2. Collect all hyperlinks from current node
3. Place newly collected links onto the top of a list
4. Visit the node on the top of the list
5. Repeat from step 2.
This method is likely to saturate a remote server as it will request documents as it travels deeply into each site's (probably hierarchical or contents table - indexed) structure.

This method is excellent for creating a catalogue of a local site.

Breadth First Traversal
1. Start at a node
2. Collect all hyperlinks from current node
3. Place newly collected links onto the top of a list
4. Visit the node on the bottom of the list
5. Repeat from step 2.
This method is not good for creating a catalogue of a local site because its search will quickly come to span several servers, each being visited in turn.

This method however has the benefit that it is less likely to saturate a server than depth first traversal.

Of course there is nothing to stop you writing a robot which selects between these methods depending on whether the intent is to search widely or deeply!

There are many traps and pitfalls (not all described above) for the novice robot writer to fall into.

It is a certified

*BAD THING*

to send a robot out to someone's web server
if you don't know what you are doing!

Consult the plethora of web literature concerning standards for robot authoring before proceeding!

Keeping Robots at Bay

Poorly written robots can slaughter a server.
If robots adhere to the standards it is possible to limit the files on your server to which they have access.

This can be achieved through the robot.txt file.

# /robots.txt file

# robbieRobot can roam freely
User-agent: robbieRobot
Disallow:

# DUMB (Dorin's URL Muncher Bot) can't look at anything
# (It is not allowed to examine anything whose relative
# URL begins with /, ie. everything!
User-agent: DUMB
Disallow: /

# Every other bot can examine anything except /tmp and /logs
User-agent: *
Disallow: /tmp
Disallow: /logs

You can prevent robots following links from a page by including an attribute in the document META tag...

<META NAME="ROBOTS" CONTENT="NOFOLLOW">

Or you can keep robots from indexing a page by including an attribute in the document META tag...

<META NAME="ROBOTS" CONTENT="NOINDEX">
Of course, if the robot doesn't follow the standards then there's not much you can do to prevent it accessing your site.
If you check out a list of robots you can determine how few of them actually support the exclusion standards fully.