"Search Engines-Information Retrieval in Practice" by W. Bruce Croft, Donald Metzler, and Trevor Strohman

Chapter 1: Search Engines and Information Retrieval

What is information retrieval?

Salton is considered to be a founding father of IR, and proposed the following early definition:

Information retrieval is a field concerned with the structure, analysis, organization, storage, searching, and retrieval of information - Gerard Salton, 1968.

This old definition is still appropriate.

The traditional focus of IR is on text and text documents. Documents have some structure, e.g. with title and author that are attributes or fields, but the main distinction with database records is that nevertheless most information is unstructured text. In a database, the text of a document would likely be stored as a single attribute without further internal structure.

To retrieve documents, search queries therefore must compare the query with the contents of this unstructured text.

Understanding and modeling how people compare texts, and designing computer algorithms to accurately perform this comparison, is at the core of information retrieval.(2)

Interesting: the study of how humans search texts is according to this understanding also part of IR.

IR is extended to multimedia nowadays, but IR is still to a large degree reliant on accurate descriptions of multimedia content, such as tags for pictures.

This book prefers the terminology of collection over database to try and distinguish information retrieval from more straightforward database queries.

Types of search application

Web search is not the only form of search.

  • "Vertical search is a specialized form of web search where the domain of the search is restricted to a particular topic." (3)
  • "Enterprise search involves finding the required information in the huge variety of computer files scattered across a corporate intranet." (3)
    • Sources also include e.g. emails, reports, presentations etc.
  • "Desktop search is the personal version of enterprise search, where the information sources are the files stored on an individual computer" (3)
  • "Peer-to-peer search involves finding information in networks of nodes or computers without centralized control."

Exercise 1.2 concerns site search: searching the web pages of a single website. Compare site search to web search, vertical search, and enterprise search.

Search tasks

  • Ad-hoc search: a user query that is not prespecified
  • Filtering
    • May require tracking on a person's personal interests
  • Classification
    • Example?
  • Question answering
    • A specific answer rather than a list of documents is preferred

Main IR issues

  1. Relevance

"Loosely speaking, a relevant document contains the information that a person was looking for when she submitted a query to the search engine." (4)

Exact matches (a la grep) are not sufficient, due to the vocabulary mismatch problem: the same concepts can be expressed in various ways, using various words.

Topic relevance indicates that a document concerns the same topic as a query.

User relevance indicates the personal subjective (my words) relevance for the user. A returned document may be topically relevant, but it has less user relevance if the user has already seen it before. Modern search engines incorporate user relevance by tracking their personal preferences through previous choices and online behavior.

A retrieval model "is a formal representation of the process of matching a query and a document" (5) and serves as the basic procedure for determining relevance and ranking results.

An interesting feature of the retrieval models used in information retrieval is that they typically model the statistical properties of text rather than the linguistic structure. (5)

If you think about it, it is non-trivial that texts are represented with word frequencies rather than information about their linguistic structure. The latter is used sometimes, but is not commonly the primary method.

The idea that word frequencies can also represent the (semantic) content of texts was coined by H.P. Luhn in the 1950s.

  1. Evaluation

Cyril Cleverdon coined evaluation measures, including precision and recall.

However, these two measures assume that we know the total amount of relevant documents. In practice, for example with web search, this assumption does always not hold. For evaluation in terms of recall or precision, it is therefore common to use test collections.

A test collection contains:

  • Collection of text documents
  • List of typical queries
  • List of relevant documents for each query.
    • These are called/based on relevance judgements.

Best known test collections are provided by TREC.

Other measures involve logging of user behavior, for example clickthrough data (document clicks for one search session). This is often used in addition to relevance judgments, which are a more sturdy form of validation.

  1. Emphasis on users' information needs

The fundamental issue is that textual search queries "are often poor descriptions of what the user actually wants" (6). Cf. in database this is not the case because queries are very well-defined.

A main approach is therefore to develop ways of helping people express their information need, e.g. using:

  • Query suggestion
  • Query expansion
  • Relevance feedback

Search engines

Different search engines have different focuses for different needs. E.g. the main challenge for enterprise search is to deal with the variety of sources, whereas desktop search needs to index new files as they are made by the user.

Search engines deployed on large-scale need to score high in performance on:

  • Response time: time diff between query and return of result(s)
  • Query throughput: how many queries can be processed at a time
  • Indexing speed
    • Coverage indicates what fragment of the available information is indexed
    • Recency or freshness measures how recent a piece of stored information is.

The design of good indexes is one of the most important topics for making search engines faster.

Requirements for search engines:

  • Performance
  • Incorporating new data
  • Scalability
    • Usable whatever the scale
  • Adaptability
    • Usable what ever the specific focus of the application
  • Deal with spam; "spamdexing"
    • Irrelevant info for the purpose of commercial gain
    • Deal with spam words put in documents to make them rank higher

Chapter 2: Architecture of a Search Engine

Goal here is to identify the relevant components of a search engines, as well as the interfaces and relations between them.

Various search systems have slightly different requirements, but two common main goals are:

  • Effectiveness (quality): retrieve the most relevant documents
    • Process texts and store text statistics
  • Efficiency (speed): ... as quickly as possible.
    • Good indexing systems

There are two main processes:

  1. Indexing process
    • Structures to support searching
  2. Query process
    • Use those structures to retrieve ranked document lists

Building blocks of the indexing process

  1. Text acquisition
    • E.g. by crawling
    • Creates a document data store that contains the texts and their metadata.
  2. Text transformation
    • Documents -> Index terms or features a.k.a. the index vocabulary.
    • Not every word is a feature; they have to represent content (and also can be phrased rather than words)
  3. Index creation
    • Must allow fast updating
    • Inverted indexes are most common

Building blocks of the querying process

  1. User interaction
    • Transforming user query in usable index terms
    • Take the result (ranked document list) and present results
    • The document data store is accessed, e.g. to present snippets.
    • Refining queries
  2. Ranking
    • Takes the transformed query to generate a ranked list based on the retrieval model
  3. Evaluation
    • Mostly done through recording and analyzing user behavior with log data.
    • Mostly offline

A question in the first IR lecture was why the document data store is connected to user interaction. Now I see that the answer is that search engines work with index terms and not with the documents; only when presenting the results it becomes relevant to access the original document again.

Text acquisition

Topical web crawlers "use classification techniques to restrict the pages that are visited to those that are likely to be about a specific topic." (17) Mainly used for vertical or topical search.

Document web crawlers follow lings between different types of documents to discover new ones. Used for enterprise and desktop search.

Challenges for crawlers:

  • Efficiently handle huge volume
  • Keep already visited sites "fresh"

Alternatively, one may monitor a document feed (e.g. using RSS) to acquire new documents.

The conversion of media into a textual format (e.g. text -> pdf) can also belong to this phase. Further processing is in the "text transformation" phase.

Another thing is to deal with different document encodings.

Text transformation

  • Parsing
  • "Stopping": removing tokens to exclude them from being index terms
    • May use stopword lists, but there are downsides. E.g. "be" is common, but we do want to consider it for "to be or not to be" (cf. 20).
    • One could muse longer stopword list for queries, shorter one for full texts.
  • Stemming: increase likelihood of words matching in queries and documents.
    • Whether stemming is very effective depends on the language morphology. It's useful in English, very effective in Arabic, and not effective at all in Chinese.
    • Aggressive stemming may decrease performing by returning too wide (=less relevant) results.
  • Link extraction
    • "Extraction means that this information is recorded in the document data store, and can be indexed separately from the general text content." (21)
    • PageRank is a link analysis algorithm, provides indication of rating and also authority/importance.
    • I did not understand this sentence: "Anchor text, which is the clickable text of a web link, can be used to enhance the text content of a page that the link points to." (21)
  • Information extraction
    • If we want to use index terms/features that are more complex (e.g. phrases or company names) then single words, then we need further syntactic analysis e.g. with PoS-tagging.
  • Classifier
    • Documents are often classified with predefined labels.
    • Identify documents as spam
    • Identify the non-content part of documents
    • Clustering can also be done to create documents groups, if predefined categories are not useful.

Index creation

  • Document statistics (stored in lookup tables) include:
    • index term occurrences
    • positions of occurrence within the document for index terms
    • "counts of occurrences over groups of documents" (22)
      • Not sure if I understand this one.
    • document length (in tokens)
  • Weighting based on document statistics
    • Some weighting information is only known during the query process, but you want to do as much computation as possible in the indexing phase
    • E.g. tfidf weighting with log N/n.
  • Inversion
    • Format for quick query processing
    • Indexes are also compressed for efficiency
  • Index distribution
    • Improves efficiency
    • Document distribution: distribute the indexes "for a subset of the documents" so that "both indexing and query processing can be done in parallel" (23)
    • Term distribution: ibid. but then for a subset of terms
    • Replication: "copies of indexes or parts of indexes are stored in multiple sites so that query processing can be made more efficient by reducing communication delays." (23)

User interaction

  • Query input: interface and parser for a query language
    • Most search engines are designed for keyword-based queries and do not function well for longer sentences
  • Query transformation
    • Similar to text transformation: tokenizing, stopping, stemming
    • Spell checking
    • Query suggestion (using query logs)
    • Query expansion
      • Relevance feedback: expansion "based on term occurrences in documents that are identified as relevant by the user." (25)
  • Present results, may include
    • Summarization/snippet generation
    • Highlighting of result based on query
    • Clustering output to find similar documents
    • Determine relevant advertising (BOOOOOOOH)

Ranking

  • Scoring or "query processing"
    • "all ranking algorithms are based implicitly on a retrieval model" (25)
    • Default idea for document score: $\sum_i{q_i \cdot d_i}$
    • sum over vocabulary of the collection, query term weight x document term weight for term i
  • Performance optimization
    • Document-at-a-time scoring is faster then term-at-a-time scoring (is suggested at least, cf. 26)
    • Safe optimizers do not change the scoring w.r.t. unoptimized ranking.
  • Distribution of ranking
    • Query broker: "decides how to allocate queries to processors in a network and is responsible for assembling the final ranked list for the query." (26)
    • Caching: keep indexes or results from previous queries in local memory, so you don't have to redo them, especially when these queries are popular.

Evaluation

  • Logging
    • Query logs; clickthrough data, dwell time;
    • e.g. documents that are clicked on for a query can be deemed more relevant; this feedback may be incorporated in the ranking algorithm
  • Ranking analysis
    • Measuring the quality of the top-ranked documents is often more appropriate then evaluation the whole list
  • Performance analysis
    • In distributed networks, we care about traffic monitoring and analysis.
    • Can be done using simulations