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.

• 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?

• 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?

CS276: Information Retrieval and Web Search 

Pandu Nayak and Prabhakar Raghavan

Lecture 2: The term vocabulary and postings lists

• Basic inverted indexes:

• Structure: Dictionary and Postings

• Key step in construction: Sortingli>

• Boolean query processing

• Intersection by linear time “merging”

• Simple optimizations

• Overview of course topics

Elaborate basic indexing

• Preprocessing to form the term vocabulary

• Documents

• Tokenization

• What terms do we put in the index?

• Postings

• Faster merges: skip lists

• Positional postings and phrase queries

• What format is it in?

• pdf/word/excel/html?

• What language is it in?

• What character set is in use?

  
  

   Each of these is a classification problem, which we will study later in the course.

   But these tasks are often done heuristically …

• Documents being indexed can include docs from many different languages

• A single index may have to contain terms of several languages.

• Sometimes a document or its components can contain multiple languages/formats

• French email with a German pdf attachment.

• What is a unit document?

• A file?

• An email? (Perhaps one of many in an mbox.)

• An email with 5 attachments?

• A group of files (PPT or LaTeX as HTML pages)

TOKEN AND TERMS

• Input: “Friends, Romans, Countrymen”

• Output: Tokens

• Friends

• Romans

• Countrymen

• A token is a sequence of characters in a document

• Each such token is now a candidate for an index entry, after further processing

• Described below

• But what are valid tokens to emit?

• Issues in tokenization:

• Finland’s capital → 

• Finland? Finlands? Finland’s?

• Hewlett-Packard → Hewlett and Packard as two tokens?

• state-of-the-art: break up hyphenated sequence.

• co-education

• lowercase, lower-case, lower case ?

• It can be effective to get the user to put in possible hyphens

• San Francisco: one token or two?

• How do you decide it is one token?

• 3/12/91                Mar. 12, 1991                     12/3/91

• 55 B.C.

• B-52

• My PGP key is 324a3df234cb23e

• (800) 234-2333

• Often have embedded spaces

• Older IR systems may not index numbers

• But often very useful: think about things like looking up error codes/stacktraces on the web

• (One answer is using n-grams: Lecture 3)

• Will often index “meta-data” separately

• Creation date, format, etc.

• French

• L'ensemble  →  one token or two?

• L ? L’ ? Le ?

• Want l’ensemble to match with un ensemble

• Until at least 2003, it didn’t on Google

• Internationalization!

• German noun compounds are not segmented

• Lebensversicherungsgesellschaftsangestellter

• ‘life insurance company employee’

• German retrieval systems benefit greatly from a compound splitter module

• Can give a 15% performance boost for German

• Chinese and Japanese have no spaces between words:

  • 莎拉波娃现在居住在美国东南部的佛罗里达。
  • Not always guaranteed a unique tokenization

• Further complicated in Japanese, with multiple alphabets intermingled

• Dates/amounts in multiple formats

  End-user can express query entirely in hiragana!

• Arabic (or Hebrew) is basically written right to left, but with certain items like numbers written left to right

• Words are separated, but letter forms within a word form complex ligatures

•                                        ← →    ← →                                  ← start

• ‘Algeria achieved its independence in 1962 after 132 years of French occupation.’

• With Unicode, the surface presentation is complex, but the stored form is straightforward

• With a stop list, you exclude from the dictionary entirely the commonest words. Intuition:

• They have little semantic content: the, a, and, to, be

• There are a lot of them: ~30% of postings for top 30 words

• But the trend is away from doing this:

• Good compression techniques (lecture 5) means the space for including stopwords in a system is very small

• Good query optimization techniques (lecture 7) mean you pay little at query time for including stop words.

• You need them for:

• Phrase queries: “King of Denmark”

• Various song titles, etc.: “Let it be”, “To be or not to be”

• “Relational” queries: “flights to London”

• We need to “normalize” words in indexed text as well as query words into the same form

• We want to match U.S.A. and USA

• Result is terms: a term is a (normalized) word type, which is an entry in our IR system dictionary

• We most commonly implicitly define equivalence classes of terms by, e.g.,

• deleting periods to form a term

• U.S.A., USA ⌊ USA

• deleting hyphens to form a term

• anti-discriminatory, antidiscriminatory ⌊ antidiscriminatory

• Accents: e.g., French résumé vs. resume.

• Umlauts: e.g., German: Tuebingen vs. Tübingen

• Should be equivalent

• Most important criterion:

• How are your users like to write their queries for these words?

• Even in languages that standardly have accents, users often may not type them

• Often best to normalize to a de-accented term

• Tuebingen, Tübingen, Tubingen  ⌊  Tubingen

• Normalization of things like date forms

  • 7月30日 vs. 7/30
  • Japanese use of kana vs. Chinese characters

• Tokenization and normalization may depend on the language and so is intertwined with language detection

• Crucial: Need to “normalize” indexed text as well as query terms into the same form

• Reduce all letters to lower case

• exception: upper case in mid-sentence?

  • e.g., General Motors
  • Fed vs. fed
  • SAIL vs. sail
• Often best to lower case everything, since users will use lowercase regardless of ‘correct’ capitalization

• An alternative to equivalence classing is to do asymmetric expansion

• An example of where this may be useful

• Enter: window Search: window, windows

• Enter: windows Search: Windows, windows, window

• Enter: Windows Search: Windows

• Potentially more powerful, but less efficient

• Reduce inflectional/variant forms to base form

• E.g.,

• am, are, is  → be

• car, cars, car's, cars'  →  car

• the boy's cars are different colors  the boy car be different color

• Lemmatization implies doing “proper” reduction to dictionary headword form

• Reduce terms to their “roots” before indexing

• “Stemming” suggest crude affix chopping

• language dependent

• e.g., automate(s), automatic, automation all reduced to automat.

  
  

• Commonest algorithm for stemming English

• Results suggest it’s at least as good as other stemming options

• Conventions + 5 phases of reductions

• phases applied sequentially

• each phase consists of a set of commands

• sample convention: Of the rules in a compound command, select the one that applies to the longest suffix.

• sses → ss

• ies →i

• ational  →  ate

• tional  →  tion

• Rules sensitive to the measure of words

• (m>1) EMENT →

• replacement → replac

• cement → cement

• Other stemmers exist, e.g., Lovins stemmer

• http://www.comp.lancs.ac.uk/computing/research/stemming/general/lovins.htm

• Single-pass, longest suffix removal (about 250 rules)

• Full morphological analysis – at most modest benefits for retrieval

• Do stemming and other normalizations help?

• English: very mixed results. Helps recall but harms precision

• operative (dentistry) ⇒ oper

• operational (research) ⇒ oper

• operating (systems) ⇒ oper

• Definitely useful for Spanish, German, Finnish, …

• 30% performance gains for Finnish!

• Do we handle synonyms and homonyms?

• E.g., by hand-constructed equivalence classes

• car = automobile      color = colour

• We can rewrite to form equivalence-class terms

• When the document contains automobile, index it under car-automobile (and vice-versa)

• Or we can expand a query

• When the query contains automobile, look under car as well

• What about spelling mistakes?

• One approach is soundex, which forms equivalence classes of words based on phonetic heuristics

• More in lectures 3 and 9

• Many of the above features embody transformations that are

• Language-specific and

• Often, application-specific

• These are “plug-in” addenda to the indexing process

• Both open source and commercial plug-ins are available for handling these

Faster postıngs merges:
Skıp poınters/Skıp lısts

• Why?

• To skip postings that will not figure in the search results.

• How?

• Where do we place skip pointers?

• Tradeoff:

• More skips →shorter skip spans ⇒more likely to skip. But lots of comparisons to skip pointers.

• Fewer skips → few pointer comparison, but then long skip spans  ⇒  few successful skips.

• Simple heuristic: for postings of length L, use √L evenly-spaced skip pointers.

• This ignores the distribution of query terms.

• Easy if the index is relatively static; harder if L keeps changing because of updates.

• This definitely used to help; with modern hardware it may not (Bahle et al. 2002) unless you’re memory-based

• The I/O cost of loading a bigger postings list can outweigh the gains from quicker in memory merging!

Phrase querıes and posıtıonal ındexes

• Want to be able to answer queries such as “stanford university” – as a phrase

• Thus the sentence “I went to university at Stanford” is not a match.

• The concept of phrase queries has proven easily understood by users; one of the few “advanced search” ideas that works

• Many more queries are implicit phrase queries

• For this, it no longer suffices to store only

• <term : docs> entries

• Index every consecutive pair of terms in the text as a phrase

• For example the text “Friends, Romans, Countrymen” would generate the biwords

• friends romans

• romans countrymen

• Each of these biwords is now a dictionary term

• Two-word phrase query-processing is now immediate.

• Longer phrases are processed as we did with wild-cards:

• stanford university palo alto can be broken into the Boolean query on biwords:

• stanford university AND university palo AND palo alto

• Without the docs, we cannot verify that the docs matching the above Boolean query do contain the phrase.

                                                                                  ↑   Can have false positives!

• Parse the indexed text and perform part-of-speech-tagging (POST).

• Bucket the terms into (say) Nouns (N) and articles/prepositions (X).

• Call any string of terms of the form NX*N an extended biword.

• Each such extended biword is now made a term in the dictionary.

• Example: catcher in the rye

                 N           X   X    N

• Query processing: parse it into N’s and X’s

• Segment query into enhanced biwords

• Look up in index: catcher rye

• False positives, as noted before

• Index blowup due to bigger dictionary

• Infeasible for more than biwords, big even for them

• Biword indexes are not the standard solution (for all biwords) but can be part of a compound strategy

• In the postings, store for each term the position(s) in which tokens of it appear:

  
  

  <term, number of docs containing term;

   doc1: position1, position2 … ;

   doc2: position1, position2 … ;

   etc.>

• For phrase queries, we use a merge algorithm recursively at the document level

• But we now need to deal with more than just equality

• Extract inverted index entries for each distinct term: to, be, or, not.

• Merge their doc:position lists to enumerate all positions with “to be or not to be”.

• to:

• 2:1,17,74,222,551; 4:8,16,190,429,433; 7:13,23,191; ...

• be:

• 1:17,19; 4:17,191,291,430,434; 5:14,19,101; ...

• Same general method for proximity searches

• LIMIT! /3 STATUTE /3 FEDERAL /2 TORT

• Again, here, /k means “within k words of”.

• Clearly, positional indexes can be used for such queries; biword indexes cannot.

• Exercise: Adapt the linear merge of postings to handle proximity queries. Can you make it work for any value of k?

• This is a little tricky to do correctly and efficiently

• See Figure 2.12 of IIR

• There’s likely to be a problem on it!

• You can compress position values/offsets: we’ll talk about that in lecture 5

• Nevertheless, a positional index expands postings storage substantially

• Nevertheless, a positional index is now standardly used because of the power and usefulness of phrase and proximity queries … whether used explicitly or implicitly in a ranking retrieval system.

• Need an entry for each occurrence, not just once per document

• Index size depends on average document size                    ←  Why?

• Average web page has <1000 _tmplitem="94" terms

• SEC filings, books, even some epic poems … easily 100,000 terms

• Consider a term with frequency 0.1%

• A positional index is 2–4 as large as a non-positional index

• Positional index size 35–50% of volume of original text

• Caveat: all of this holds for “English-like” languages

• These two approaches can be profitably combined

• For particular phrases (“Michael Jackson”, “Britney Spears”) it is inefficient to keep on merging positional postings lists

• Even more so for phrases like “The Who”

• Williams et al. (2004) evaluate a more sophisticated mixed indexing scheme

• A typical web query mixture was executed in ¼ of the time of using just a positional index

• It required 26% more space than having a positional index alone

• IIR 2

• MG 3.6, 4.3; MIR 7.2

• Porter’s stemmer:

  http://www.tartarus.org/~martin/PorterStemmer/

• Skip Lists theory: Pugh (1990)

• Multilevel skip lists give same O(log n) efficiency as trees

• H.E. Williams, J. Zobel, and D. Bahle. 2004. “Fast Phrase Querying with Combined Indexes”, ACM Transactions on Information Systems.

  http://www.seg.rmit.edu.au/research/research.php?author=4

• D. Bahle, H. Williams, and J. Zobel. Efficient phrase querying with an auxiliary index. SIGIR 2002, pp. 215-221.

CS276: Information Retrieval and Web Search 

Pandu Nayak and Prabhakar Raghavan

Lecture 3: Dictionaries and tolerant retrieval

• The type/token distinction

• Terms are normalized types put in the dictionary

• Tokenization problems:

• Hyphens, apostrophes, compounds, CJK

• Term equivalence classing:

• Numbers, case folding, stemming, lemmatization

• Skip pointers

• Encoding a tree-like structure in a postings list

• Biword indexes for phrases

• Positional indexes for phrases/proximity queries

• Dictionary data structures

• “Tolerant” retrieval

• Wild-card queries

• Spelling correction

• Soundex

• The dictionary data structure stores the term vocabulary, document frequency, pointers to each postings list … in what data structure?

• An array of struct:

                                     char[20]      int                           Postings *

                                     20 bytes      4/8 bytes                 4/8 bytes

• How do we store a dictionary in memory efficiently?

• How do we quickly look up elements at query time?

• Two main choices:

• Hashtables

• Trees

• Some IR systems use hashtables, some trees

• Each vocabulary term is hashed to an integer

• (We assume you’ve seen hashtables before)

• Pros:

• Lookup is faster than for a tree: O(1)

• Cons:

• No easy way to find minor variants:

• judgment/judgement

• No prefix search [tolerant retrieval]

• If vocabulary keeps growing, need to occasionally do the expensive operation of rehashing everything

• Definition: Every internal nodel has a number of children in the interval [a,b] where a, b are appropriate natural numbers, e.g., [2,4].

• Simplest: binary tree

• More usual: B-trees

• Trees require a standard ordering of characters and hence strings … but we typically have one

• Pros:

• Solves the prefix problem (terms starting with hyp)

• Cons:

• Slower: O(log M) [and this requires balanced tree]

• Rebalancing binary trees is expensive

• But B-trees mitigate the rebalancing problem

Wild-card queries 

• mon*: find all docs containing any word beginning with “mon”.

• Easy with binary tree (or B-tree) lexicon: retrieve all words in range:

  mon ≤ w < moo

• *mon: find words ending in “mon”: harder

• Maintain an additional B-tree for terms backwards.

• Can retrieve all words in range: nom ≤ w < non.

• Exercise: from this, how can we enumerate all terms

• meeting the wild-card query pro*cent ?

• At this point, we have an enumeration of all terms in the dictionary that match the wild-card query.

• We still have to look up the postings for each enumerated term.

• E.g., consider the query:

• se*ate AND fil*er

• This may result in the execution of many Boolean AND queries.

• How can we handle *’s in the middle of query term?

• co*tion

• We could look up co* AND *tion in a B-tree and intersect the two term sets

• Expensive

• The solution: transform wild-card queries so that the *’s occur at the end

• This gives rise to the Permuterm Index.

• For term hello, index under:

• hello$, ello$h, llo$he, lo$hel, o$hell

• where $ is a special symbol.

• Queries:

• X lookup on X$                    X* lookup on $X*

• *X lookup on X$*              *X* lookup on X*

• X*Y lookup on Y$X*           X*Y*Z ??? Exercise!

                                                    ↑

                                         Query = hel*o

                                             X=hel, Y=o

                                         Lookup o$hel*

• Rotate query wild-card to the right

• Now use B-tree lookup as before.

• Permuterm problem: ≈ quadruples lexicon size

                                         ↑

                            Empirical observation for English.

• Enumerate all k-grams (sequence of k chars) occurring in any term

• e.g., from text “April is the cruelest month” we get the 2-grams (bigrams)

• $ is a special word boundary symbol

• Maintain a second inverted index from bigrams to dictionary terms that match each bigram.

• $a,ap,pr,ri,il,l$,$i,is,s$,$t,th,he,e$,$c,cr,ru,

  ue,el,le,es,st,t$, $m,mo,on,nt,h$

• The k-gram index finds terms based on a query consisting of k-grams (here k=2).

• Query mon* can now be run as

• $m AND mo AND on

                                    ↓

• Gets terms that match AND version of our wildcard query.

• But we’d enumerate moon.

• Must post-filter these terms against query.

• Surviving enumerated terms are then looked up in the term-document inverted index.

• Fast, space efficient (compared to permuterm).

• As before, we must execute a Boolean query for each enumerated, filtered term.

• Wild-cards can result in expensive query execution (very large disjunctions…)

• pyth* AND prog*

• If you encourage “laziness” people will respond!

Spelling Correction 

• Two principal uses

• Correcting document(s) being indexed

• Correcting user queries to retrieve “right” answers

• Two main flavors:

• Isolated word

• Check each word on its own for misspelling

• Will not catch typos resulting in correctly spelled words

• e.g., from →form

• Context-sensitive

• Look at surrounding words,

• e.g., I flew form Heathrow to Narita.

• Especially needed for OCR’ed documents

• Correction algorithms are tuned for this: rn/m

• Can use domain-specific knowledge

• E.g., OCR can confuse O and D more often than it would confuse O and I (adjacent on the QWERTY keyboard, so more likely interchanged in typing).

• But also: web pages and even printed material have typos

• Goal: the dictionary contains fewer misspellings

• But often we don’t change the documents and instead fix the query-document mapping

• Our principal focus here

• E.g., the query Alanis Morisett

• We can either

• Retrieve documents indexed by the correct spelling, OR

• Return several suggested alternative queries with the correct spelling

• Did you mean … 

• Fundamental premise – there is a lexicon from which the correct spellings come

• Two basic choices for this

• A standard lexicon such as

• Webster’s English Dictionary

• An “industry-specific” lexicon – hand-maintained

• The lexicon of the indexed corpus

• E.g., all words on the web

• All names, acronyms etc.

• (Including the mis-spellings)

• Given a lexicon and a character sequence Q, return the words in the lexicon closest to Q

• What’s “closest”?

• We’ll study several alternatives

• Edit distance (Levenshtein distance)

• Weighted edit distance

• n-gram overlap

• Given two strings S1 and S2, the minimum number of operations to convert one to the other

• Operations are typically character-level

• Insert, Delete, Replace, (Transposition)

• E.g., the edit distance from dof to dog is 1

• From cat to act is 2 (Just 1 with transpose.)

• from cat to dog is 3.

• Generally found by dynamic programming.

• See http://www.merriampark.com/ld.htm for a nice example plus an applet.

• As above, but the weight of an operation depends on the character(s) involved

• Meant to capture OCR or keyboard errors
  Example: m more likely to be mis-typed as n than as q

• Therefore, replacing m by n is a smaller edit distance than by q

• This may be formulated as a probability model

• Requires weight matrix as input

• Modify dynamic programming to handle weights

• Given query, first enumerate all character sequences within a preset (weighted) edit distance (e.g., 2)

• Intersect this set with list of “correct” words

• Show terms you found to user as suggestions

• Alternatively,

• We can look up all possible corrections in our inverted index and return all docs … slow

• We can run with a single most likely correction

• The alternatives disempower the user, but save a round of interaction with the user

• Given a (mis-spelled) query – do we compute its edit distance to every dictionary term?

• Expensive and slow

• Alternative?

• How do we cut the set of candidate dictionary terms?

• One possibility is to use n-gram overlap for this

• This can also be used by itself for spelling correction.

• Enumerate all the n-grams in the query string as well as in the lexicon

• Use the n-gram index (recall wild-card search) to retrieve all lexicon terms matching any of the query n-grams

• Threshold by number of matching n-grams

• Variants – weight by keyboard layout, etc.

• Suppose the text is november

• Trigrams are nov, ove, vem, emb, mbe, ber.

• The query is december

• Trigrams are  dec, ece, cem, emb, mbe, ber.

• So 3 trigrams overlap (of 6 in each term)

• How can we turn this into a normalized measure of overlap?

• A commonly-used measure of overlap

• Let X and Y be two sets; then the J.C. is

• Equals 1 when X and Y have the same elements and zero when they are disjoint

• X and Y don’t have to be of the same size

• Always assigns a number between 0 and 1

• Now threshold to decide if you have a match

• E.g., if J.C. > 0.8, declare a match 

• Consider the query lord – we wish to identify words matching 2 of its 3 bigrams (lo, or, rd)

  
  

  lo ⇒ alone → lore → sloth

  or ⇒ border → lore → morbid

  rd ⇒ ardent → border → card

                              ↑

  Standard postings “merge” will enumerate … 

  Adapt this to using Jaccard (or another) measure.

• Text: I flew from Heathrow to Narita.

• Consider the phrase query “flew form Heathrow”

• We’d like to respond

  
  

  Did you mean “flew from Heathrow”?

  because no docs matched the query phrase.

• Need surrounding context to catch this.

• First idea: retrieve dictionary terms close (in weighted edit distance) to each query term

• Now try all possible resulting phrases with one word “fixed” at a time

• flew from heathrow

• fled form heathrow

• flea form heathrow

• Hit-based spelling correction: Suggest the alternative that has lots of hits.

• Suppose that for “flew form Heathrow” we have 7 alternatives for flew, 19 for form and 3 for heathrow.

• How many “corrected” phrases will we enumerate in this scheme?

• Break phrase query into a conjunction of biwords (Lecture 2).

• Look for biwords that need only one term corrected.

• Enumerate only phrases containing “common” biwords.

• We enumerate multiple alternatives for “Did you mean?”

• Need to figure out which to present to the user

• The alternative hitting most docs

• Query log analysis

• More generally, rank alternatives probabilistically

• argmaxcorr P(corr | query)

• From Bayes rule, this is equivalent to
  argmaxcorr P(query | corr) * P(corr)

                            ↑                 ↑

                Noisy channel     Language model

Soundex 

• Class of heuristics to expand a query into phonetic equivalents

• Language specific – mainly for names

• E.g., chebyshev → tchebycheff

• Invented for the U.S. census … in 1918

• Turn every token to be indexed into a 4-character reduced form
  

• Do the same with query terms

• Build and search an index on the reduced forms

• (when the query calls for a soundex match)

• http://www.creativyst.com/Doc/Articles/SoundEx1/SoundEx1.htm#Top

1. Retain the first letter of the word.

2. Change all occurrences of the following letters to '0' (zero):
     'A', E', 'I', 'O', 'U', 'H', 'W', 'Y'.

3. Change letters to digits as follows:

   • B, F, P, V →1

   • C, G, J, K, Q, S, X, Z →2

   • D,T →3

   • L →4

   • M, N →5

   • R →6

1. Remove all pairs of consecutive digits.

2. Remove all zeros from the resulting string.

3. Pad the resulting string with trailing zeros and return the first four positions, which will be of the form .

   • E.g., Herman becomes H655.

                         ↑

     Will hermann generate the same code?

• We have

• Positional inverted index with skip pointers

• Wild-card index

• Spell-correction

• Soundex

• Queries such as

• (SPELL(moriset) /3 toron*to) OR SOUNDEX(chaikofski)

• Soundex is the classic algorithm, provided by most databases (Oracle, Microsoft, …)

• How useful is soundex?

• Not very – for information retrieval

• Okay for “high recall” tasks (e.g., Interpol), though biased to names of certain nationalities

• Zobel and Dart (1996) show that other algorithms for phonetic matching perform much better in the context of IR

• Draw yourself a diagram showing the various indexes in a search engine incorporating all the functionality we have talked about

• Identify some of the key design choices in the index pipeline:

• Does stemming happen before the Soundex index?

• What about n-grams?

• Given a query, how would you parse and dispatch sub-queries to the various indexes?

• IIR 3, MG 4.2

• Efficient spell retrieval:

• K. Kukich. Techniques for automatically correcting words in text. ACM Computing Surveys 24(4), Dec 1992.

• J. Zobel and P. Dart.  Finding approximate matches in large lexicons.  Software - practice and experience 25(3), March 1995. http://citeseer.ist.psu.edu/zobel95finding.html

• Mikael Tillenius: Efficient Generation and Ranking of Spelling Error Corrections. Master’s thesis at Sweden’s Royal Institute of Technology. http://citeseer.ist.psu.edu/179155.html

• Nice, easy reading on spell correction:

• Peter Norvig: How to write a spelling corrector

• http://norvig.com/spell-correct.html

CS276: Information Retrieval and Web Search

Pandu Nayak and Prabhakar Raghavan

Lecture 4: Index Construction

• How do we construct an index?

• What strategies can we use with limited main memory?

• Many design decisions in information retrieval are based on the characteristics of hardware

• We begin by reviewing hardware basics

• Access to data in memory is much faster than access to data on disk.

• Disk seeks: No data is transferred from disk while the disk head is being positioned.

• Therefore: Transferring one large chunk of data from disk to memory is faster than transferring many small chunks.

• Disk I/O is block-based: Reading and writing of entire blocks (as opposed to smaller chunks).

• Block sizes: 8KB to 256 KB.

• Servers used in IR systems now typically have several GB of main memory, sometimes tens of GB.

• Available disk space is several (2–3) orders of magnitude larger.

• Fault tolerance is very expensive: It’s much cheaper to use many regular machines rather than one fault tolerant machine.

• symbol                   statistic                               value

•     s                   average seek time 5                    ms = 5 x 10⁻³ s

•     b                   transfer time per byte 0.02         μs = 2 x 10−8 s

•                          processor’s clock rate                10⁹ s⁻¹

•      p                  low-level operation 0.01             μs = 10⁻⁸ s

                          (e.g., compare & swap a word)

•                          size of main memory                    several GB

•                          size of disk space                          1 TB or more

• Shakespeare’s collected works definitely aren’t large enough for demonstrating many of the points in this course.

• The collection we’ll use isn’t really large enough either, but it’s publicly available and is at least a more plausible example.

• As an example for applying scalable index construction algorithms, we will use the Reuters RCV1 collection.

• This is one year of Reuters newswire (part of 1995 and 1996)

• symbol                        statistic                       value

•     N                           documents                      800,000

•      L                        avg. # tokens per doc            200

•      M                       terms (= word types)         400,000

•                                 avg. # bytes per token            6

                                  (incl. spaces/punct.)

•                                 avg. # bytes per token           4.5

                                  (without spaces/punct.)

•                                 avg. # bytes per term             7.5

•                                non-positional postings    100,000,000

  4.5 bytes per word token vs. 7.5 bytes per word type: why?

• After all documents have been parsed, the inverted file is sorted by terms.                 ↑

We focus on this sort step.We have 100M items to sort.

• In-memory index construction does not scale
  

• Can’t stuff entire collection into memory, sort, then write back

• How can we construct an index for very large collections?

• Taking into account the hardware constraints we just learned about . . .

• Memory, disk, speed, etc.

• As we build the index, we parse docs one at a time.

• While building the index, we cannot easily exploit compression tricks (you can, but much more complex)

• The final postings for any term are incomplete until the end.

• At 12 bytes per non-positional postings entry (term, doc, freq), demands a lot of space for large collections.

• T = 100,000,000 in the case of RCV1

• So … we can do this in memory in 2009, but typical collections are much larger. E.g., the New York Times provides an index of >150 years of newswire

• Thus: We need to store intermediate results on disk.

• Can we use the same index construction algorithm for larger collections, but by using disk instead of memory?

• No: Sorting T = 100,000,000 records on disk is too slow – too many disk seeks.

• We need an external sorting algorithm.

• Parse and build postings entries one doc at a time

• Now sort postings entries by term (then by doc within each term)

• Doing this with random disk seeks would be too slow

  – must sort T=100M records

• 12-byte (4+4+4) records (term, doc, freq).

• These are generated as we parse docs.

• Must now sort 100M such 12-byte records by term.

• Define a Block ~ 10M such records

• Can easily fit a couple into memory.

• Will have 10 such blocks to start with.

• Basic idea of algorithm:

• Accumulate postings for each block, sort, write to disk.

• Then merge the blocks into one long sorted order.

• First, read each block and sort within:

• Quicksort takes 2N ln N expected steps

• In our case 2 x (10M ln 10M) steps

• Exercise: estimate total time to read each block from disk and and quicksort it.

• 10 times this estimate – gives us 10 sorted runs of 10M records each.

• Done straightforwardly, need 2 copies of data on disk

• But can optimize this

• Can do binary merges, with a merge tree of log210 = 4 layers.

• During each layer, read into memory runs in blocks of 10M, merge, write back.

  
  

• But it is more efficient to do a multi-way merge, where you are reading from all blocks simultaneously

• Providing you read decent-sized chunks of each block into memory and then write out a decent-sized output chunk, then you’re not killed by disk seeks.

• Our assumption was: we can keep the dictionary in memory.

• We need the dictionary (which grows dynamically) in order to implement a term to termID mapping.

• Actually, we could work with term,docID postings instead of termID,docID postings . . .

• . . . but then intermediate files become very large. (We would end up with a scalable, but very slow index construction method.)

• Key idea 1: Generate separate dictionaries for each block – no need to maintain term-termID mapping across blocks.

• Key idea 2: Don’t sort. Accumulate postings in postings lists as they occur.

• With these two ideas we can generate a complete inverted index for each block.

• These separate indexes can then be merged into one big index.

• Merging of blocks is analogous to BSBI. 
  

• Compression makes SPIMI even more efficient.

• Compression of terms

• Compression of postings

• See next lecture

• For web-scale indexing (don’t try this at home!):
  

• must use a distributed computing cluster

• Individual machines are fault-prone

• Can unpredictably slow down or fail

• How do we exploit such a pool of machines?

• Web search data centers (Google, Bing, Baidu) mainly contain commodity machines.

• Data centers are distributed around the world.

• Estimate: Google ~1 million servers, 3 million processors/cores (Gartner 2007)

• If in a non-fault-tolerant system with 1000 nodes, each node has 99.9% uptime, what is the uptime of the system?

• Answer: 63%

• Exercise: Calculate the number of servers failing per minute for an installation of 1 million servers.

• Maintain a master machine directing the indexing job – considered “safe”.

• Break up indexing into sets of (parallel) tasks.

• Master machine assigns each task to an idle machine from a pool.

• We will use two sets of parallel tasks

• Parsers

• Inverters

• Break the input document collection into splits

• Each split is a subset of documents (corresponding to blocks in BSBI/SPIMI)

• Master assigns a split to an idle parser machine

• Parser reads a document at a time and emits (term, doc) pairs

• Parser writes pairs into j partitions

• Each partition is for a range of terms’ first letters

• (e.g., a-f, g-p, q-z) – here j = 3.

• Now to complete the index inversion

• An inverter collects all (term,doc) pairs (= postings) for one term-partition.

• Sorts and writes to postings lists

• The index construction algorithm we just described is an instance of MapReduce.

• MapReduce (Dean and Ghemawat 2004) is a robust and conceptually simple framework for distributed computing …

• … without having to write code for the distribution part.

• They describe the Google indexing system (ca. 2002) as consisting of a number of phases, each implemented in MapReduce.

• Index construction was just one phase.

• Another phase: transforming a term-partitioned index into a document-partitioned index.

• Term-partitioned: one machine handles a subrange of terms

• Document-partitioned: one machine handles a subrange of documents

• As we’ll discuss in the web part of the course, most search engines use a document-partitioned index … better load balancing, etc.

• Schema of map and reduce functions

• map: input → list(k, v) reduce: (k,list(v)) → output

• Instantiation of the schema for index construction

• map: collection → list(termID, docID)

• reduce: (, , …) → (postings list1, postings list2, …)

• Map:

• d1 : C came, C c’ed.

• d2 : C died. →

• (C,d1>, <came,d1>, <C,d1>, <c'ed, d1>, >C, d2>, <died, d2>

• Reduce:

• (<C,(d1,d2,d1)>, <died,(d2)>, <came, (d1)>, <c'ed,(d1)>) 

  → <C,(d1:2,d2:1)>, <died,(d2:1)>,  <came, (d1:1)>, <c'ed,(d1:1)>) 

• Up to now, we have assumed that collections are static.

• They rarely are:

• Documents come in over time and need to be inserted.

• Documents are deleted and modified.

• This means that the dictionary and postings lists have to be modified:

• Postings updates for terms already in dictionary

• New terms added to dictionary

• Maintain “big” main index

• New docs go into “small” auxiliary index

• Search across both, merge results

• Deletions

• Invalidation bit-vector for deleted docs

• Filter docs output on a search result by this invalidation bit-vector

• Periodically, re-index into one main index

• Problem of frequent merges – you touch stuff a lot

• Poor performance during merge

• Actually:

• Merging of the auxiliary index into the main index is efficient if we keep a separate file for each postings list.

• Merge is the same as a simple append.

• But then we would need a lot of files – inefficient for OS.

• Assumption for the rest of the lecture: The index is one big file.

• In reality: Use a scheme somewhere in between (e.g., split very large postings lists, collect postings lists of length 1 in one file etc.)

• Maintain a series of indexes, each twice as large as the previous one

• At any time, some of these powers of 2 are instantiated

• Keep smallest (Z0) in memory

• Larger ones (I0, I1, …) on disk

• If Z0 gets too big (> n), write to disk as I0

• or merge with I0 (if I0 already exists) as Z1

• Either write merge Z1 to disk as I1 (if no I1)

• Or merge with I1 to form Z2

• Auxiliary and main index: index construction time is O(T2) as each posting is touched in each merge.

• Logarithmic merge: Each posting is merged O(log T) times, so complexity is O(T log T)

• So logarithmic merge is much more efficient for index construction

• But query processing now requires the merging of O(log T) indexes

• Whereas it is O(1) if you just have a main and auxiliary index

• Collection-wide statistics are hard to maintain

• E.g., when we spoke of spell-correction: which of several corrected alternatives do we present to the user?

• We said, pick the one with the most hits

• How do we maintain the top ones with multiple indexes and invalidation bit vectors?

• One possibility: ignore everything but the main index for such ordering

• Will see more such statistics used in results ranking

• All the large search engines now do dynamic indexing
  

• Their indices have frequent incremental changes

• News items, blogs, new topical web pages

• Sarah Palin, …

• But (sometimes/typically) they also periodically reconstruct the index from scratch

• Query processing is then switched to the new index, and the old index is deleted

• Positional indexes

• Same sort of sorting problem … just larger                ← WHY?

• Building character n-gram indexes:

• As text is parsed, enumerate n-grams.

• For each n-gram, need pointers to all dictionary terms containing it – the “postings”.

• Note that the same “postings entry” will arise repeatedly in parsing the docs – need efficient hashing to keep track of this.

• E.g., that the trigram uou occurs in the term deciduous will be discovered on each text occurrence of deciduous

• Only need to process each term once

• Chapter 4 of IIR

• MG Chapter 5

• Original publication on MapReduce: Dean and Ghemawat (2004)

• Original publication on SPIMI: Heinz and Zobel (2003)

Pandu Nayak and Prabhakar Raghavan

Lecture 5: Index Compression

• Problem set 1 due Thursday

• Programming exercise 1 will be handed out today

• Sort-based indexing 

• Naïve in-memory inversion 

• Blocked Sort-Based Indexing

• Merge sort is effective for disk-based sorting (avoid seeks!)

• Single-Pass In-Memory Indexing

• No global dictionary

• Generate separate dictionary for each block

• Don’t sort postings

• Accumulate postings in postings lists as they occur

• Distributed indexing using MapReduce

• Dynamic indexing: Multiple indices, logarithmic merge

• Collection statistics in more detail (with RCV1)

• How big will the dictionary and postings be?

• Dictionary compression

• Postings compression

• Use less disk space
  

• Saves a little money

• Keep more stuff in memory

• Increases speed

• Increase speed of data transfer from disk to memory

• [read compressed data | decompress] is faster than [read uncompressed data]

• Premise: Decompression algorithms are fast

• True of the decompression algorithms we use

• Dictionary

• Make it small enough to keep in main memory

• Make it so small that you can keep some postings lists in main memory too

• Postings file(s)

• Reduce disk space needed

• Decrease time needed to read postings lists from disk

• Large search engines keep a significant part of the postings in memory.

• Compression lets you keep more in memory

• We will devise various IR-specific compression schemes

symbol                             statistic                                     value

•     N                               documents                                800,000

•      L                     avg. # tokens per doc                             200

•     M                     terms (= word types)                       ~400,000

•                             avg. # bytes per token                             6

                                 (incl. spaces/punct.)

•                             avg. # bytes per token                           4.5

                             (without spaces/punct.)

•                             avg. # bytes per term                             7.5

•                             non-positional postings                  100,000,000

• Lossless compression: All information is preserved.

• What we mostly do in IR.

• Lossy compression: Discard some information

• Several of the preprocessing steps can be viewed as lossy compression: case folding, stop words, stemming, number elimination.

• Chap/Lecture 7: Prune postings entries that are unlikely to turn up in the top k list for any query.

• Almost no loss quality for top k list.

• How big is the term vocabulary?

• That is, how many distinct words are there?

• Can we assume an upper bound?

• Not really: At least 70²⁰ = 10³⁷ different words of length 20

• In practice, the vocabulary will keep growing with the collection size

• Especially with Unicode :)

• Heaps’ law: M = kTb

• M is the size of the vocabulary, T is the number of tokens in the collection

• Typical values: 30 ≤ k ≤ 100 and b ≈ 0.5

• In a log-log plot of vocabulary size M vs. T, Heaps’ law predicts a line with slope about ½

• It is the simplest possible relationship between the two in log-log space

• An empirical finding (“empirical law”)

• What is the effect of including spelling errors, vs. automatically correcting spelling errors on Heaps’ law?
  

• Compute the vocabulary size M for this scenario:

• Looking at a collection of web pages, you find that there are 3000 different terms in the first 10,000 tokens and 30,000 different terms in the first 1,000,000 tokens.

• Assume a search engine indexes a total of 20,000,000,000 (2 × 1010) pages, containing 200 tokens on average

• What is the size of the vocabulary of the indexed collection as predicted by Heaps’ law?

• Heaps’ law gives the vocabulary size in collections.

• We also study the relative frequencies of terms.

• In natural language, there are a few very frequent terms and very many very rare terms.

• Zipf’s law: The ith most frequent term has frequency proportional to 1/i .

• cf_i ∝ 1/i = K/i where K is a normalizing constant

• cf_i is collection frequency: the number of occurrences of the term t_i in the collection.

• If the most frequent term (the) occurs cf1 times

• then the second most frequent term (of) occurs cf1/2 times

• the third most frequent term (and) occurs cf1/3 times …

• Equivalent: cfi = K/i where K is a normalizing factor, so

• log cfi = log K - log i

• Linear relationship between log cfi and log i

• Another power law relationship

• Now, we will consider compressing the space for the dictionary and postings

• Basic Boolean index only

• No study of positional indexes, etc.

• We will consider compression schemes

• Search begins with the dictionary
  

• We want to keep it in memory

• Memory footprint competition with other applications

• Embedded/mobile devices may have very little memory

• Even if the dictionary isn’t in memory, we want it to be small for a fast search startup time

• So, compressing the dictionary is important

• Array of fixed-width entries

• ~400,000 terms; 28 bytes/term = 11.2 MB.

                     ↓                        20 bytes                4 bytes each

• Most of the bytes in the Term column are wasted – we allot 20 bytes for 1 letter terms.

• And we still can’t handle supercalifragilisticexpialidocious or hydrochlorofluorocarbons.

• Written English averages ~4.5 characters/word.

• Exercise: Why is/isn’t this the number to use for estimating the dictionary size?

• Ave. dictionary word in English: ~8 characters

• How do we use ~8 characters per dictionary term?

• Short words dominate token counts but not type average.

• Store dictionary as a (long) string of characters:

• Pointer to next word shows end of current word

• Hope to save up to 60% of dictionary space.

• 4 bytes per term for Freq. 
  

• 4 bytes per term for pointer to Postings.                         → Now avg. 11 bytes/term,

• 3 bytes per term pointer                                                               ...Not 20

• Avg. 8 bytes per term in term string

• 400K terms x 19 ⇒7.6 MB (against 11.2MB for fixed width)

• Store pointers to every kth term string.

• Example below: k=4.

• Need to store term lengths (1 extra byte)

• Example for block size k = 4
  

• Where we used 3 bytes/pointer without blocking

• 3 x 4 = 12 bytes,

• now we use 3 + 4 = 7 bytes.

• Shaved another ~0.5MB. This reduces the size of the dictionary from 7.6 MB to 7.1 MB.

• We can save more with larger k.

• Why not go with larger k?

• Estimate the space usage (and savings compared to 7.6 MB) with blocking, for block sizes of k = 4, 8 and 16.

• Büinary search down to 4-term block;

• Then linear search through terms in block.

• Blocks of 4 (binary tree), avg. = (1+2∙2+2∙3+2∙4+5)/8 = 3 compares

• Estimate the impact on search performance (and slowdown compared to k=1) with blocking, for block sizes of k = 4, 8 and 16. 

• Front-coding:

• Sorted words commonly have long common prefix – store differences only

• (for last k-1 in a block of k)

• 8automata8automate9automatic10automation

                    → 8automat*a1♦e2♦ic3♦ion

                               ↑                        ↑
  

           Encodes automat          Extra length beyond automat.

• Begins to resemble general string compression.

• The postings file is much larger than the dictionary, factor of at least 10.

• Key desideratum: store each posting compactly.

• A posting for our purposes is a docID.

• For Reuters (800,000 documents), we would use 32 bits per docID when using 4-byte integers.

• Alternatively, we can use log2 800,000 ≈ 20 bits per docID.

• Our goal: use far fewer than 20 bits per docID.

• A term like arachnocentric occurs in maybe one doc out of a million – we would like to store this posting using log2 1M ~ 20 bits.

• A term like the occurs in virtually every doc, so 20 bits/posting is too expensive.

• Prefer 0/1 bitmap vector in this case

• We store the list of docs containing a term in increasing order of docID.

• computer: 33,47,154,159,202 …

• Consequence: it suffices to store gaps.

• 33,14,107,5,43 …

• Hope: most gaps can be encoded/stored with far fewer than 20 bits.

• Aim:

• For arachnocentric, we will use ~20 bits/gap entry.

• For the, we will use ~1 bit/gap entry.

• If the average gap for a term is G, we want to use ~log2G bits/gap entry.

• Key challenge: encode every integer (gap) with about as few bits as needed for that integer.

• This requires a variable length encoding

• Variable length codes achieve this by using short codes for small numbers

• For a gap value G, we want to use close to the fewest bytes needed to hold log2 G bits

• Begin with one byte to store G and dedicate 1 bit in it to be a continuation bit c

• If G ≤127, binary-encode it in the 7 available bits and set c =1

• Else encode G’s lower-order 7 bits and then use additional bytes to encode the higher order bits using the same algorithm

• At the end set the continuation bit of the last byte to 1 (c =1) – and for the other bytes c = 0.

• Instead of bytes, we can also use a different “unit of alignment”: 32 bits (words), 16 bits, 4 bits (nibbles).

• Variable byte alignment wastes space if you have many small gaps – nibbles do better in such cases.

• Variable byte codes:

• Used by many commercial/research systems

• Good low-tech blend of variable-length coding and sensitivity to computer memory alignment matches (vs. bit-level codes, which we look at next).

• There is also recent work on word-aligned codes that pack a variable number of gaps into one word

• Represent n as n 1s with a final 0.

• Unary code for 3 is 1110.

• Unary code for 40 is

• 11111111111111111111111111111111111111110 .

• Unary code for 80 is:

• 111111111111111111111111111111111111111111111111111111111111111111111111111111110

• This doesn’t look promising, but….

• We can compress better with bit-level codes

• The Gamma code is the best known of these.

• Represent a gap G as a pair length and offset

• offset is G in binary, with the leading bit cut off

• For example 13 → 1101 → 101

• length is the length of offset

• For 13 (offset 101), this is 3.

• We encode length with unary code: 1110.

• Gamma code of 13 is the concatenation of length and offset: 1110101

• G is encoded using 2  ⌊ log G⌋ + 1 bits

• Length of offset is  ⌊ log G ⌋  bits

• Length of length is ⌊log G ⌋ + 1 bits

• All gamma codes have an odd number of bits

• Almost within a factor of 2 of best possible, log₂ G

• Gamma code is uniquely prefix-decodable, like VB

• Gamma code can be used for any distribution

• Gamma code is parameter-free

• Machines have word boundaries – 8, 16, 32, 64 bits

• Operations that cross word boundaries are slower

• Compressing and manipulating at the granularity of bits can be slow

• Variable byte encoding is aligned and thus potentially more efficient

• Regardless of efficiency, variable byte is conceptually simpler at little additional space cost

• We can now create an index for highly efficient Boolean retrieval that is very space efficient

• Only 4% of the total size of the collection

• Only 10-15% of the total size of the text in the collection

• However, we’ve ignored positional information

• Hence, space savings are less for indexes used in practice

• But techniques substantially the same.

• IIR 5

• MG 3.3, 3.4.

• F. Scholer, H.E. Williams and J. Zobel. 2002. Compression of Inverted Indexes For Fast Query Evaluation. Proc. ACM-SIGIR 2002.

• Variable byte codes

• V. N. Anh and A. Moffat. 2005. Inverted Index Compression Using Word-Aligned Binary Codes. Information Retrieval 8: 151–166.

• Word aligned codes

Pandu Nayak and Prabhakar Raghavan

Lecture 6: Scoring, Term Weighting and the Vector Space Model

• Collection and vocabulary statistics: Heaps’ and Zipf’s laws

• Dictionary compression for Boolean indexes

• Dictionary string, blocks, front coding

• Postings compression: Gap encoding, prefix-unique codes

• Variable-Byte and Gamma codes

• Ranked retrieval

• Scoring documents

• Term frequency

• Collection statistics

• Weighting schemes

• Vector space scoring

• Thus far, our queries have all been Boolean.

• Documents either match or don’t.

• Good for expert users with precise understanding of their needs and the collection.

• Also good for applications: Applications can easily consume 1000s of results.

• Not good for the majority of users.

• Most users incapable of writing Boolean queries (or they are, but they think it’s too much work).

• Most users don’t want to wade through 1000s of results.

• This is particularly true of web search.

• feast or famine

• Boolean queries often result in either too few (=0) or too many (1000s) results.

• Query 1: “standard user dlink 650” → 200,000 hits

• Query 2: “standard user dlink 650 no card found”: 0 hits

• It takes a lot of skill to come up with a query that produces a manageable number of hits.

• AND gives too few; OR gives too many

• Rather than a set of documents satisfying a query expression, in ranked retrieval, the system returns an ordering over the (top) documents in the collection for a query

• Free text queries: Rather than a query language of operators and expressions, the user’s query is just one or more words in a human language

• In principle, there are two separate choices here, but in practice, ranked retrieval has normally been associated with free text queries and vice versa

• When a system produces a ranked result set, large result sets are not an issue

• Indeed, the size of the result set is not an issue

• We just show the top k ( ≈ 10) results

• We don’t overwhelm the user

• Premise: the ranking algorithm works

• We wish to return in order the documents most likely to be useful to the searcher

• How can we rank-order the documents in the collection with respect to a query?

• Assign a score – say in [0, 1] – to each document

• This score measures how well document and query “match”.

• We need a way of assigning a score to a query/document pair

• Let’s start with a one-term query 

• If the query term does not occur in the document: score should be 0

• The more frequent the query term in the document, the higher the score (should be)

• We will look at a number of alternatives for this.

• Recall from Lecture 3: A commonly used measure of overlap of two sets A and B

• jaccard(A,B) = |A ∩ B| / |A ∪ B|

• jaccard(A,A) = 1

• jaccard(A,B) = 0 if A ∩ B = 0 

• A and B don’t have to be the same size.

• Always assigns a number between 0 and 1.

• What is the query-document match score that the Jaccard coefficient computes for each of the two documents below?

• Query: ides of march

• Document 1: caesar died in march

• Document 2: the long march

• It doesn’t consider term frequency (how many times a term occurs in a document)

• Rare terms in a collection are more informative than frequent terms. Jaccard doesn’t consider this information

• We need a more sophisticated way of normalizing for length

• Later in this lecture, we’ll use 

• . . . instead of |A ∩ B|/|A ∪ B| (Jaccard) for length normalization.

• Each document is represented by a binary vector ∈ {0,1}|V|

• Consider the number of occurrences of a term in a document:

• Each document is a count vector in ℕv: a column below 

• Vector representation doesn’t consider the ordering of words in a document

• John is quicker than Mary and Mary is quicker than John have the same vectors

• This is called the bag of words model.

• In a sense, this is a step back: The positional index was able to distinguish these two documents.

• We will look at “recovering” positional information later in this course.

• For now: bag of words model

• The term frequency tft,d of term t in document d is defined as the number of times that t occurs in d.

• We want to use tf when computing query-document match scores. But how?

• Raw term frequency is not what we want:

• A document with 10 occurrences of the term is more relevant than a document with 1 occurrence of the term.

• But not 10 times more relevant.

• Relevance does not increase proportionally with term frequency.

• NB: frequency = count in IR

• The log frequency weight of term t in d is

• 0 → 0, 1 → 1, 2 → 1.3, 10 → 2, 1000 → 4, etc.

• Score for a document-query pair: sum over terms t in both q and d:

• The score is 0 if none of the query terms is present in the document.

  score :

• Rare terms are more informative than frequent terms

• Recall stop words

• Consider a term in the query that is rare in the collection (e.g., arachnocentric)

• A document containing this term is very likely to be relevant to the query arachnocentric

• → We want a high weight for rare terms like arachnocentric.

• Frequent terms are less informative than rare terms

• Consider a query term that is frequent in the collection (e.g., high, increase, line)

• A document containing such a term is more likely to be relevant than a document that doesn’t

• But it’s not a sure indicator of relevance.

• → For frequent terms, we want high positive weights for words like high, increase, and line

• But lower weights than for rare terms.

• We will use document frequency (df) to capture this.

• dft is the document frequency of t: the number of documents that contain t

• dft is an inverse measure of the informativeness of t

• df_t ≤ N

• We define the idf (inverse document frequency) of t by

• We use log (N/df_t) instead of N/df_t to “dampen” the effect of idf.

• Will turn out the base of the log is immaterial.

There is one idf value for each term t in a collection.

idf_{t =} log₁₀ = ( N/df_t)

• Does idf have an effect on ranking for one-term queries, like
  

• iPhone

• idf has no effect on ranking one term queries

• idf affects the ranking of documents for queries with at least two terms

• For the query capricious person, idf weighting makes occurrences of capricious count for much more in the final document ranking than occurrences of person.

• The collection frequency of t is the number of occurrences of t in the collection, counting multiple occurrences.

• Example:

• Which word is a better search term (and should get a higher weight)?
  

• The tf-idf weight of a term is the product of its tf weight and its idf weight.

  W_t,d = log(1+ tf_t,d) x log₁₀(N/df_t)

• Best known weighting scheme in information retrieval

• Note: the “-” in tf-idf is a hyphen, not a minus sign!

• Alternative names: tf.idf, tf x idf

• Increases with the number of occurrences within a document

• Increases with the rarity of the term in the collection

• There are many variants

• How “tf” is computed (with/without logs)

• Whether the terms in the query are also weighted

• … 

• Each document is now represented by a real-valued vector of tf-idf weights ∈ R^|V|

• So we have a |V|-dimensional vector space

• Terms are axes of the space

• Documents are points or vectors in this space

• Very high-dimensional: tens of millions of dimensions when you apply this to a web search engine

• These are very sparse vectors - most entries are zero.

• Key idea 1: Do the same for queries: represent them as vectors in the space
  

• Key idea 2: Rank documents according to their proximity to the query in this space

• proximity = similarity of vectors

• proximity ≈ inverse of distance

• Recall: We do this because we want to get away from the you’re-either-in-or-out Boolean model.

• Instead: rank more relevant documents higher than less relevant documents

• First cut: distance between two points

• ( = distance between the end points of the two vectors)

• Euclidean distance?

• Euclidean distance is a bad idea . . .

• . . . because Euclidean distance is large for vectors of different lengths.

• The Euclidean distance between q and d₂ is large even though the distribution of t terms in the query q and the distribution of terms in the document d₂ are very similar.

• Thought experiment: take a document d and append it to itself. Call this document d′.

• “Semantically” d and d′ have the same content

• The Euclidean distance between the two documents can be quite large

• The angle between the two documents is 0, corresponding to maximal similarity.

• Key idea: Rank documents according to angle with query.

• The following two notions are equivalent.

• Rank documents in decreasing order of the angle between query and document

• Rank documents in increasing order of cosine(query,document)

• Cosine is a monotonically decreasing function for the interval [0^o, 180^o]

• But how – and why – should we be computing cosines?

• A vector can be (length-) normalized by dividing each of its components by its length – for this we use the L₂ norm:

• Dividing a vector by its L2 norm makes it a unit (length) vector (on surface of unit hypersphere)

• Effect on the two documents d and d′ (d appended to itself) from earlier slide: they have identical vectors after length-normalization.

• Long and short documents now have comparable weights

• qi is the tf-idf weight of term i in the query

• di is the tf-idf weight of term i in the document

• cos(q,d) is the cosine similarity of q and d … or,

• equivalently, the cosine of the angle between q and d.

• For length-normalized vectors, cosine similarity is simply the dot product (or scalar product):

• for q, d length-normalized.

• How similar are the novels 
• SaS: Sense and Sensibility
•  PaP: Pride and  Prejudice, and  
• WH: Wuthering Heights?

• Term frequencies (counts)

• Note: To simplify this example, we don’t do idf weighting.

• cos(SaS,PaP) ≈

  0.789 × 0.832 + 0.515 × 0.555 + 0.335 × 0.0 + 0.0 × 0.0

  ≈ 0.94

  cos(SaS,WH) ≈ 0.79

  cos(PaP,WH) ≈ 0.69

• Why do we have cos(SaS,PaP) > cos(SaS,WH)?

• Columns headed ‘n’ are acronyms for weight schemes.

• Why is the base of the log in idf immaterial?

• Many search engines allow for different weightings for queries vs. documents

• SMART Notation: denotes the combination in use in an engine, with the notation ddd.qqq, using the acronyms from the previous table

• A very standard weighting scheme is: lnc.ltc

• Document: logarithmic tf (l as first character), no idf and cosine normalization

• Query: logarithmic tf (l in leftmost column), idf (t in second column), no normalization …

• A bad idea?

• Exercise: what is N, the number of docs?

• Score = 0+0+0.27+0.53 = 0.8

• Doc length =

• Represent the query as a weighted tf-idf vector

• Represent each document as a weighted tf-idf vector

• Compute the cosine similarity score for the query vector and each document vector

• Rank documents with respect to the query by score

• Return the top K (e.g., K = 10) to the user

• IIR 6.2 – 6.4.3

• http://www.miislita.com/information-retrieval-tutorial/cosine-similarity-tutorial.html

• Term weighting and cosine similarity tutorial for SEO folk!

Information Retrieval and Web Search

Pandu Nayak and Prabhakar Raghavan

Lecture 7: Scoring and results assembly

• In my anxiety to avoid taking the log of zero, I rewrote

• In fact this was unnecessary, since the zero case is treated

• specially above; net the FIRST version above is right.

• The tf-idf weight of a term is the product of its tf weight and its idf weight.

  w_t,d= (1+log₁₀ tf_t,d) x log₁₀(N/df_t)

• Best known weighting scheme in information retrieval

• Increases with the number of occurrences within a document

• Increases with the rarity of the term in the collection

  
  

• Key idea 1: Do the same for queries: represent them as vectors in the space

• Key idea 2: Rank documents according to their proximity to the query in this space

• proximity = similarity of vectors

• cos(q,d) is the cosine similarity of q and d … or,

• equivalently, the cosine of the angle between q and d.

• Speeding up vector space ranking

• Putting together a complete search system

• Will require learning about a number of miscellaneous topics and heuristics

• Find the K docs in the collection “nearest” to the query ⇒ K largest query-doc cosines.

• Efficient ranking:

• Computing a single cosine efficiently.

• Choosing the K largest cosine values efficiently.

• Can we do this without computing all N cosines?

• What we’re doing in effect: solving the K-nearest neighbor problem for a query vector

• In general, we do not know how to do this efficiently for high-dimensional spaces

• But it is solvable for short queries, and standard indexes support this well

• No weighting on query terms

• Assume each query term occurs only once

• Then for ranking, don’t need to normalize query vector

• Slight simplification of algorithm from Lecture 6

• Typically we want to retrieve the top K docs (in the cosine ranking for the query)

• not to totally order all docs in the collection

• Can we pick off docs with K highest cosines?

• Let J = number of docs with nonzero cosines

• We seek the K best of these J

• Binary tree in which each node’s value > the values of children

• Takes 2J operations to construct, then each of K “winners” read off in 2log J steps.

• For J=1M, K=100, this is about 10% of the cost of sorting.

• Primary computational bottleneck in scoring: cosine computation

• Can we avoid all this computation?

• Yes, but may sometimes get it wrong

• a doc not in the top K may creep into the list of K output docs

• Is this such a bad thing?

• User has a task and a query formulation

• Cosine matches docs to query

• Thus cosine is anyway a proxy for user happiness

• If we get a list of K docs “close” to the top K by cosine measure, should be ok

• Find a set A of contenders, with K < |A| << N

• A does not necessarily contain the top K, but has many docs from among the top K

• Return the top K docs in A

• Think of A as pruning non-contenders

• The same approach is also used for other (non-cosine) scoring functions

• Will look at several schemes following this approach

• Basic algorithm cosine computation algorithm only considers docs containing at least one query term

• Take this further:

• Only consider high-idf query terms

• Only consider docs containing many query terms

• For a query such as catcher in the rye

• Only accumulate scores from catcher and rye

• Intuition: in and the contribute little to the scores and so don’t alter rank-ordering much

• Benefit:

• Postings of low-idf terms have many docs  these (many) docs get eliminated from set A of contenders

• Any doc with at least one query term is a candidate for the top K output list

• For multi-term queries, only compute scores for docs containing several of the query terms

• Say, at least 3 out of 4

• Imposes a “soft conjunction” on queries seen on web search engines (early Google)

• Easy to implement in postings traversal

• Scores only computed for docs 8, 16 and 32.

• Precompute for each dictionary term t, the r docs of highest weight in t’s postings

• Call this the champion list for t

• (aka fancy list or top docs for t)

• Note that r has to be chosen at index build time

• Thus, it’s possible that r < K

• At query time, only compute scores for docs in the champion list of some query term

• Pick the K top-scoring docs from amongst these

• How do Champion Lists relate to Index Elimination? Can they be used together?

• How can Champion Lists be implemented in an inverted index?

• Note that the champion list has nothing to do with small docIDs

• Static quality scores

• We want top-ranking documents to be both relevant and authoritative

• Relevance is being modeled by cosine scores

• Authority is typically a query-independent property of a document

• Examples of authority signals

• Wikipedia among websites

• Articles in certain newspapers

• A paper with many citations

• Many bitly’s, diggs or del.icio.us marks

• (Pagerank)

• Assign to each document a query-independent quality score in [0,1] to each document d

• Denote this by g(d)

• Thus, a quantity like the number of citations is scaled into [0,1]

• Exercise: suggest a formula for this.

• Consider a simple total score combining cosine relevance and authority

• net-score(q,d) = g(d) + cosine(q,d)

• Can use some other linear combination

• Indeed, any function of the two “signals” of user happiness – more later

• Now we seek the top K docs by net score

• First idea: Order all postings by g(d)

• Key: this is a common ordering for all postings

• Thus, can concurrently traverse query terms’ postings for

• Postings intersection

• Cosine score computation

• Exercise: write pseudocode for cosine score computation if postings are ordered by g(d)

• Under g(d)-ordering, top-scoring docs likely to appear early in postings traversal

• In time-bound applications (say, we have to return whatever search results we can in 50 ms), this allows us to stop postings traversal early

• Short of computing scores for all docs in postings

• Can combine champion lists with g(d)-ordering

• Maintain for each term a champion list of the r docs with highest g(d) + tf-idf_td

• Seek top-K results from only the docs in these champion lists 

• For each term, we maintain two postings lists called high and low

• Think of high as the champion list

• When traversing postings on a query, only traverse high lists first

• If we get more than K docs, select the top K and stop

• Else proceed to get docs from the low lists

• Can be used even for simple cosine scores, without global quality g(d)

• A means for segmenting index into two tiers

• We only want to compute scores for docs for which wft,d is high enough

• We sort each postings list by wft,d

• Now: not all postings in a common order!

• How do we compute scores in order to pick off top K?

• Two ideas follow

• When traversing t’s postings, stop early after either

• a fixed number of r docs

• wft,d drops below some threshold

• Take the union of the resulting sets of docs

• One from the postings of each query term

• Compute only the scores for docs in this union

• When considering the postings of query terms

• Look at them in order of decreasing idf

• High idf terms likely to contribute most to score

• As we update score contribution from each query term

• Stop if doc scores relatively unchanged

• Can apply to cosine or some other net scores

• Pick √N docs at random: call these leaders

• For every other doc, pre-compute nearest leader

• Docs attached to a leader: its followers;

• Likely: each leader has ~ √N followers.

• Process a query as follows:

• Given query Q, find its nearest leader L.

• Seek K nearest docs from among L’s followers.

• Fast

• Leaders reflect data distribution

• Have each follower attached to b1=3 (say) nearest leaders.

• From query, find b2=4 (say) nearest leaders and their followers.

• Can recurse on leader/follower construction.