CS276

Information Retrieval and Web Search

Pandu Nayak and Prabhakar Raghavan

Lecture 1: Boolean retrieval

• Information Retrieval (IR) is finding material (usually documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers)

• Which plays of Shakespeare contain the words Brutus AND Caesar but NOT Calpurnia?

• One could grep all of Shakespeare’s plays for Brutus and Caesar, then strip out lines containing Calpurnia?

• Why is that not the answer?

• Slow (for large corpora)

• NOT Calpurnia is non-trivial

• Other operations (e.g., find the word Romans near countrymen) not feasible

• Ranked retrieval (best documents to return)

• Later lectures

• So we have a 0/1 vector for each term.

• To answer query: take the vectors for Brutus, Caesar and Calpurnia (complemented)  → bitwise AND.

• 110100 AND 110111 AND 101111 = 100100.

• So we have a 0/1 vector for each term.

• To answer query: take the vectors for Brutus, Caesar and Calpurnia (complemented)  → bitwise AND.

• 110100 AND 110111 AND 101111 = 100100.

• Collection: Fixed set of documents

• Goal: Retrieve documents with information that is relevant to the user’s information need and helps the user complete a task.

• Precision : Fraction of retrieved docs that are relevant to user’s information need

• Recall : Fraction of relevant docs in collection that are retrieved

• More precise definitions and measurements to follow in later lectures

• Consider N = 1 million documents, each with about 1000 words.

• Avg 6 bytes/word including spaces/punctuation

• 6GB of data in the documents.

• Say there are M = 500K distinct terms among these.

• 500K x 1M matrix has half-a-trillion 0’s and 1’s.

• But it has no more than one billion 1’s.                              ← Why? 

• matrix is extremely sparse.

• What’s a better representation?

• We only record the 1 positions.

• We need variable-size postings lists

• On disk, a continuous run of postings is normal and best

• In memory, can use linked lists or variable length arrays

• Some tradeoffs in size/ease of insertion                         Posting(below)

• How do we process a query?

• Later - what kinds of queries can we process?                ← Today’s focus 

• Consider processing the query: Brutus AND Caesar

• Locate Brutus in the Dictionary;

• Retrieve its postings.

• Locate Caesar in the Dictionary;

• Retrieve its postings.

• Merge” the two postings:

• What is the best order for query processing?

• Consider a query that is an AND of n terms.

• For each of the n terms, get its postings, then AND them together.

• Process in order of increasing freq:

• start with smallest set, then keep cutting further.

                                          ↑

  (This is why we kept document freq. in dictionary)

• The Boolean retrieval model is being able to ask a query that is a Boolean expression:

• Boolean Queries use AND, OR and NOT to join query terms

• Views each document as a set of words

• Is precise: document matches condition or not.

• Perhaps the simplest model to build an IR system on

• Primary commercial retrieval tool for 3 decades.

• Many search systems you still use are Boolean:

• Email, library catalog, Mac OS X Spotlight

• Exercise: Adapt the merge for the queries:

• Brutus AND NOT Caesar

• Brutus OR NOT Caesar

  
  

  Can we still run through the merge in time O(x+y)?

  What can we achieve?

• Exercise: Adapt the merge for the queries:

• Brutus AND NOT Caesar

• Brutus OR NOT Caesar

  
  

  Can we still run through the merge in time O(x+y)?

  What can we achieve?

• Largest commercial (paying subscribers) legal search service (started 1975; ranking added 1992)

• Tens of terabytes of data; 700,000 users

• Majority of users still use boolean queries

• Example query:

• What is the statute of limitations in cases involving the federal tort claims act?

• LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT /3 CLAIM

• /3 = within 3 words, /S = in same sentence

• Another example query:

• Requirements for disabled people to be able to access a workplace

• disabl! /p access! /s work-site work-place (employment /3 place)

• Note that SPACE is disjunction, not conjunction!

• Long, precise queries; proximity operators; incrementally developed; not like web search

• Many professional searchers still like Boolean search

• You know exactly what you are getting

• But that doesn’t mean it actually works better….

• e.g., (madding OR crowd) AND (ignoble OR strife)

• Get doc. freq.’s for all terms.

• Estimate the size of each OR by the sum of its doc. freq.’s (conservative).

• Process in increasing order of OR sizes.

• Recommend a query processing order for

• (tangerine OR trees) AND

• (marmalade OR skies) AND

• (kaleidoscope OR eyes)

  
  

  Term                            Freq

  eyes                              213312

  kaleidoscope                 87009

  marmalade                   107913

  skies                             271658

  tangerine                       46653

  trees                             316812

  
  

• Exercise: If the query is friends AND romans AND (NOT countrymen), how could we use the freq of countrymen?

• Exercise: Extend the merge to an arbitrary Boolean query. Can we always guarantee execution in time linear in the total postings size?

• Hint: Begin with the case of a Boolean formula query where each term appears only once in the query.

• Try the search feature at

  http://www.rhymezone.com/shakespeare/
  

• Write down five search features you think it could do better

• Beyond term search

• What about phrases?

• Stanford University

• Proximity: Find Gates NEAR Microsoft.

• Need index to capture position information in docs.

• Zones in documents: Find documents with
  (author = Ullman) AND (text contains automata).

• 1 vs. 0 occurrence of a search term

• 2 vs. 1 occurrence

• 3 vs. 2 occurrences, etc.

• Usually more seems better

• Need term frequency information in docs

• Boolean queries give inclusion or exclusion of docs.

• Often we want to rank/group results

• Need to measure proximity from query to each doc.

• Need to decide whether docs presented to user are singletons, or a group of docs covering various aspects of the query.

• Structured data tends to refer to information in “tables”

  Employee		Manager		Salary
  Smith		Jones		50000
  Chang		Smith		60000
  Ivy		Smith		50000

• Typically allows numerical range and exact match

• (for text) queries, e.g.,

• Salary < 60000 AND Manager = Smith.

• Typically refers to free-form text

• Allows

• Keyword queries including operators

• More sophisticated “concept” queries, e.g.,

• find all web pages dealing with drug abuse

• Classic model for searching text documents

• In fact almost no data is “unstructured”

• E.g., this slide has distinctly identified zones such as the Title and Bullets

• Facilitates “semi-structured” search such as

• Title contains data AND Bullets contain search

  
  

  … to say nothing of linguistic structure

• Title is about Object Oriented Programming AND Author something like stro*rup

• where * is the wild-card operator

• Issues:

• how do you process “about”?

• how do you rank results?

• The focus of XML search (IIR chapter 10)

• Clustering: Given a set of docs, group them into clusters based on their contents.

• Classification: Given a set of topics, plus a new doc D, decide which topic(s) D belongs to.

• Ranking: Can we learn how to best order a set of documents, e.g., a set of search results

• Unusual and diverse documents

• Unusual and diverse users, queries, information needs

• Beyond terms, exploit ideas from social networks

• link analysis, clickstreams ...

• How do search engines work?
  And how can we make them better?

• Cross-language information retrieval

• Question answering

• Summarization

• Text mining

• …

• Introduction to Information Retrieval, chapter 1

• Shakespeare:

• http://www.rhymezone.com/shakespeare/

• Try the neat browse by keyword sequence feature!

• Managing Gigabytes, chapter 3.2

• Modern Information Retrieval, chapter 8.2

                                                                                   

  Any questions?