Spiders and crawlers

Question 1

Information Retrieval

Answer 1

A field concerned with the structure, analysis, organisation, storage, and retrieval of information.

Question 2

Goals of Search Engines

Answer 2

Effectiveness - quality - retrieve the most relevant set of documents possible

Efficiency - speed - process results from users as quickly as possible

Question 3

Indexing Process

Answer 3

Text acquisition, transformation and index creation

Question 4

Text acquisition

Answer 4

Store parsed data into a document data store

Question 5

Text transformation

Answer 5

Remove duplicates from the store, classify information and organise data

Question 6

Index creation

Answer 6

Create an index to quickly locate information - stored in an index database that can be queried by user

Question 7

Query Process

Answer 7

Interaction, evaluation and log data

Question 8

Interaction

Answer 8

User interacts with document data store, which runs a ranking algorithm from the index to display most relevant results

Question 9

Evaluation

Answer 9

Find out how relevant results are e.g. quiz user on how relevant the results are so the algorithm can be updated

Question 10

Log data

Answer 10

Log user data and update algorithm

Question 11

Types of text acquisition

Answer 11

Crawler and feed

Question 12

Crawler

Answer 12

Web crawler is the most common method of text acquisition: opens a webpage and looks for links

Question 13

Challenges faced by crawler

Answer 13

Pages are constantly updated so crawlers must be ran very frequently to keep up; may not be able to handle huge volumes of new pages

Can only operate on a single website

Question 14

Focused crawler

Answer 14

Classification technique to determine whether a page is relevant or not; will not access pages that are deemed irrelevant

Question 15

Feed

Answer 15

Real time stream of documents e.g. a news feed

Search engine acquires new documents simply by monitoring the feed

Question 16

Feed Conversion

Answer 16

Documents in feed are rarely plain text

Search engines require them to be converted into consistent text + metadata

Question 17

Document Data Store

Answer 17

Database to manage large numbers of documents and structured data (metadata) associated with them

Question 18

Types of text transformation

Answer 18

Parser, stopping and stemming

Question 19

Parser

Answer 19

Processes a sequence of text tokens

Uses knowledge of syntax to identify structure of text/information

Question 20

Stopping

Answer 20

Removes common words from the stream of tokens e.g. ‘the’, ‘of’, ‘to’, ‘for’

Reduces size of index and does not affect quality

Question 21

Stemming

Answer 21

Group words together that derive from a common stem e.g. ‘fish’, ‘fishes’ and ‘fishing’

May not be effective for all languages

Question 22

User interaction

Answer 22

Query input, query transformation and results output

Question 23

Query input

Answer 23

Small number of keywords to query from a document e.g. web query

Question 24

Query transformation

Answer 24

Tokenisation, stopping and stemming must be done to compare with document

Question 25

Results output

Answer 25

Construct display of ranked documents - snippets of documents, important words/passages etc

Question 26

Logging

Answer 26

One of the most valuable sources for tuning and improving search engines

Ranking analysis uses log data to compare effectiveness of algorithm

Simulations

Question 27

Politeness Policy

Answer 27

Some crawlers may have a limit to one page every x seconds instead of max speed

Question 28

Ratelimits

Answer 28

A limit of times a single IP address is allowed to access a server

Question 29

Deep Web

Answer 29

Private sites (accounts), form results (bus/flight timetables), scripted pages (javascript)

Difficult for a crawler to find

Question 30

Conversion Problem

Answer 30

Text document stored in incompatible formats; PDF, raw text, RTF, HTML, XML, others

Sometimes in PPT/Excel documents or obsolete formats

Question 31

Big Table

Answer 31

Used internally at Google

A distributed database built for storing web pages. A big table

Split into tablets served by thousands of machines, any changes are recorded in the transaction log

If a tablet crashes then another server can read data from transaction log and take over