Class Notes

Lab 01

Inverted Index and Boolean Queries

Incidence matrix Inverted index Index construction Boolean queries Phrase queries
Work in progress These notes are still being written and reviewed: content may change, and some parts may still contain mistakes.

Overview of the lab

Goal: build an inverted index for a collection of documents and answer Boolean queries with it. The lab goes with the lectures on Boolean retrieval and on the dictionary and postings (IIR, chapters 1–2).

  1. The task: Boolean retrieval: what we build, why, and the indexing pipeline.
  2. The direct index: a document as a list of terms, before we invert anything.
  3. Incidence matrices: the simplest index, on 14 news headlines.
  4. The inverted index: keep only the non-zero entries, as a dictionary and postings.
  5. From text to terms: tokenization, normalization, stop words, stemming.
  6. Dataset and the dictionary part: newsgroup posts, preprocess_document, document frequency.
  7. Building the full index: pairs, sort, merge, split.
  8. Boolean queries in the index: answering queries by merging postings lists.
  9. Faster query processing: term order by frequency, skip pointers.
  10. Phrase and proximity queries: biword and positional indexes.

The task: Boolean retrieval

Given a large collection of documents and a query such as wedding AND kills, return every document that satisfies the query.

  • Document: the unit we index and return. In this lab a document is first one news headline, and later one newsgroup post. What counts as a document is a design decision: a file? an e-mail? an e-mail with its 5 attachments?
  • Collection (corpus): all the documents we search.
  • Boolean query: terms combined with AND, OR and NOT. The answer is a set of documents. Each document either matches or not, and there is no ranking.
  • Why not just scan the text? Searching every document (like grep) takes time proportional to the whole collection, and we pay it again for every query. Instead, we build an index once, in advance. A query then reads only the small part of the index that is about its own terms.

The indexing pipeline

Every index in this lab goes through the same stages (the lecture calls them the basic indexing pipeline). Each card says where in the lab we build that stage.

Documents

Friends, Romans, countrymen.

14 BBC headlines, then 20 Newsgroups posts

Tokenizer

Friends Romans countrymen

NLTK's TweetTokenizer: Incidence matrices

Linguistic modules

friend roman countryman

lower-casing, dropping punctuation: From text to terms

Indexer

pairs → sort → merge → split

Building the full index

Inverted index

friend 2 → 4roman 1 → 2countryman 13 → 16

queried in Boolean queries and after

📐 Token and term

A token is one occurrence of a character sequence in a document (Friends). A term is the normalized form stored in the dictionary (friend). After the linguistic modules process it, every token can become an index entry.

We build the pipeline twice. First a toy version on 14 news headlines, to see the idea (incidence matrix, then inverted index). Then a real one on newsgroup posts (dictionary, postings, queries).

Foundation

The direct index

Before any indexing, a document is naturally just its list of terms: a direct (or forward) index, doc → terms. To answer a query like kills we would have to scan every document's list in turn — the per-query, whole-collection cost the task above ruled out.

Try it: a document's direct index

Pick a headline and see its direct-index entry: the document, tokenized and lower-cased, as a plain list of terms.

Incidence matrices

The simplest possible index: for every term and every document, record whether the term occurs in the document. Our toy collection is 14 BBC News headlines, one document each. Four steps turn them into this table, an incidence matrix: the tokenizer and one linguistic module (lower-casing) of the pipeline, then counting.

  1. Tokenize: split each sentence with NLTK's TweetTokenizer. Punctuation marks become tokens of their own: Istanbul. → Istanbul .
  2. Lower-case: The (doc 11) and the (docs 1, 13) become the same term the.
  3. Unique tokens: flatten the lists with sum(…, []) and put them in a set: 83 terms.
  4. Incidence matrix: one row per term, one column per document → shape (83, 14).

Try it: tokenize a headline

Pick a headline and see each step. Punctuation tokens are marked in red.

📐 Term-document incidence matrix

A matrix with one row per term \(t\) and one column per document \(d\). Entry \((t, d)\) is 1 if \(t\) occurs in \(d\) and 0 otherwise. The notebook stores the count sent.count(token) instead (term-document frequency), so the and in get a 2 in document 1.

Try it: answer a Boolean query with the matrix

Each term's row is a bit vector over the 14 documents. A Boolean query is a bitwise operation on rows: AND, OR, AND NOT. Rows are in alphabetical order here, because a Python set has no fixed order.

💡 The matrix has \(83 \times 14 = 1{,}162\) cells but only 93 are non-zero (8%). With a real collection (millions of documents, hundreds of thousands of terms) almost every cell is 0, so storing the full matrix wastes space. We store only the non-zero entries, and that is the inverted index.

incidence_matrix.py Python 
import numpy as np
from nltk.tokenize import TweetTokenizer

sample_bbc_news_sentences = [
    "China confirms Interpol chief detained",
    "Turkish officials believe the Washington Post writer was killed in the Saudi consulate in Istanbul.",
    "US wedding limousine crash kills 20",
    "Bulgarian journalist killed in park",
    "Kanye West deletes social media profiles",
    "Brazilians vote in polarised election",
    "Bull kills woman at French festival",
    "Indonesia to wrap up tsunami search",
    "Tina Turner reveals wedding night ordeal",
    "Victory for Trump in Supreme Court battle",
    "Clashes at German far-right rock concert",
    "The Walking Dead, actor dies aged 76",
    "Jogger in Netherlands finds lion cub",
    "Monkey takes the wheel of Indian bus"
]

# basic tokenization
tokenizer = TweetTokenizer()
sample_bbc_news_sentences_tokenized = [tokenizer.tokenize(sentence)
                                       for sentence in sample_bbc_news_sentences]
print(sample_bbc_news_sentences_tokenized[0])
# ['China', 'confirms', 'Interpol', 'chief', 'detained']

sample_bbc_news_sentences_tokenized_lower = [[_t.lower() for _t in _s]
                                             for _s in sample_bbc_news_sentences_tokenized]

# all unique tokens: flatten (sum), then put in a set
unique_tokens = set(sum(sample_bbc_news_sentences_tokenized_lower, []))
print(len(unique_tokens))   # 83

# incidence matrix (term-document frequency)
incidence_matrix = np.array([[sent.count(token)
                              for sent in sample_bbc_news_sentences_tokenized_lower]
                             for token in unique_tokens])
print(incidence_matrix.shape)   # (83, 14)
Data structure

The inverted index

For every term, keep only the documents it occurs in, that is, the non-zero cells of its row. The index is called inverted because it turns the natural view around. We usually see a document as a list of terms. The index stores, for each term, a list of documents. It has two parts.

  • Dictionary: the vocabulary of terms, each with its document frequency \(df_t\), the number of documents that contain \(t\).
  • Postings: for each term, the list of document ids that contain it (optionally with the term frequency in each). One entry is a posting.
  • ❗ Postings lists are kept sorted by document id. The query algorithms below depend on this.
  • Postings are usually stored as linked lists (or variable-length arrays), because they grow when we add documents.

See it with the headlines: from a matrix row to a postings list

Pick a term. The top row is its row in the incidence matrix. Below it is the same information as a dictionary entry and a postings list.

Before we build a real index, we have to decide which tokens become terms, and the next section does that.

Lecture

From text to terms: tokenization and normalization

These are the tokenizer and linguistic-module stages of the pipeline. They decide which terms end up in the dictionary. For the headlines we made two choices (TweetTokenizer and lower-casing). Here are the options from the lecture.

Tokenization

Splitting at spaces and punctuation is a start, but many cases are unclear. The last column shows what the notebook's TweetTokenizer does with the lecture's examples.

TextQuestionTweetTokenizer
Finland's capitalFinland? Finlands? Finland's?Finland's capital
Hewlett-Packard, co-educationsplit at the hyphen?Hewlett-Packard, co-education: one token each
San Franciscoone token or two?San Francisco: two
L'ensembleL? L'? Le? Should it match un ensemble?L'ensemble: one token
3/12/91, Mar. 12, 1991dates in several formats3/12 / 91: the date is broken up
B-52, 55 B.C.codes, abbreviationsB - 52; B . C .
100.2.86.144an IP address100.2 . 86.144
  • Numbers and codes are often not indexed as text, but they can be very useful, for example when you look up an error code. Meta-data, such as the creation date and the format, is often indexed separately.
  • Language: tokenization depends on the language. German writes noun compounds as one word (Lebens­versicherungs­gesellschafts­angestellter, 'life insurance company employee'). Chinese and Japanese have no spaces between words. Arabic and Hebrew are written right to left, but numbers left to right.
  • Parsing comes first: we have to detect the format (pdf, Word, html), language and character set of each document. One document can mix several, for example a French e-mail with a German pdf attachment.

Normalization

The terms in the documents and in the query must have the same form, so that U.S.A. matches USA.

  • Equivalence classes: the usual way, done implicitly. For example, delete periods, so U.S.A. and USA become one term.
  • Asymmetric expansion: expand the query instead. Query window → search window, windows; windows → Windows, windows; Windows → Windows. More powerful, but less efficient.
  • Accents: résumé vs resume, Tuebingen vs Tübingen. What matters is how users type their queries, and they often leave accents out.
  • Case folding: lower-case everything. There are exceptions (General Motors, Fed vs fed, SAIL vs sail), but lower-casing everything is often best, because users type in lower case anyway. In our headlines it turns the country US into us.
  • Thesauri and soundex: a thesaurus gives hand-built equivalence classes (car = automobile, color = colour). We apply them when indexing, or by expanding the query. Soundex expands names into variants that sound alike (chebyshev → tchebycheff).

Stop words

A stop list removes the most common words from the dictionary entirely.

  • For: they carry little meaning (the, a, and, to, be) and take a lot of space. About 30% of the postings belong to the 30 most common words. In sci.crypt, the occurs in 97 of the 100 posts, and of and to in 92.
  • Against: some queries need them, such as phrases ("King of Denmark"), titles ("Let it be", "To be or not to be") and relations (flights to London). With good compression and query optimization, keeping them costs little.
  • Stop lists keep getting shorter: from 200–300 words, to 7–12, to none. Web search engines usually do not use them.

Lemmatization and stemming

  • Lemmatization: reduce inflected forms to the dictionary headword: am, are, is → be; car, cars, car's, cars' → car.
  • Stemming: crudely chop off affixes. It depends on the language. The lecture's example: automate(s), automatic, automation → automat.
  • Porter's algorithm: the most common stemmer for English. It runs five phases, one after the other. Within a phase, it applies the rule with the longest matching suffix. Typical rules: sses → ss, ies → i, ational → ate, tional → tion. Some rules check the length of the stem (its measure \(m\)): (m>1) ement → turns replacement into replac but leaves cement alone.
  • Does it help? Results are mixed: stemming and other normalizations help recall for some queries and hurt precision for others.

Try it: which terms end up in the dictionary?

Switch the linguistic modules on and off. Each line is one document. Highlighted terms merge several tokens, and struck-out tokens are removed. The stop list is the 25-word example list from IIR, and the stemmer is Porter's original algorithm.

💡 The notebook's preprocess_document uses the first two modules: case folding and dropping punctuation, with no stop list and no stemming. Porter's stems don't have to be words (wedding → wed, bus → bu, monkey → monkei). They only have to be equal for words that should match. On the lecture's automate example Porter gives autom, autom, automat, autom (try More examples).

Dictionary

Dataset and the dictionary part (term and #docs)

Now the real collection: Usenet posts from the Twenty Newsgroups dataset. We build the index in two passes. First only the dictionary: each term with the number of documents that contain it. Then, in the next section, the postings.

  • 20 Newsgroups: 20,000 messages from 20 newsgroups (UCI, donated in 1999 by Tom Mitchell).
  • mini_newsgroups: the smaller version we use, one folder per newsgroup with 100 messages each (e.g. sci.crypt, sci.electronics, rec.autos).
  • Each file is a whole post, headers included (Path, From, Subject, Message-ID, …).

Preprocessing a document

preprocess_document is our tokenizer and linguistic modules in one function. It returns the tokens of a document, lower-cased and without punctuation. The steps: split into sentences (sent_tokenize), tokenize each sentence, drop punctuation, lower-case.

Try it: preprocess_document

The default text is the notebook's example, and the output matches its 12 tokens. Edit it, or load the start of a newsgroup post or the lecture's tokenization examples.

💡 _tok not in punctuation checks whether the token is a substring of the string string.punctuation (!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~). Single marks are dropped, but ... is not a substring, so it stays (try Punctuation quirks). The widget uses a simplified JavaScript copy of TweetTokenizer, so rare inputs may differ from NLTK.

Document frequency

prepare_dataset preprocesses every file in a folder. document_frequency counts, for each token, how many documents contain it. It loops over set(document), so a token counts only once per document.

  • Why document frequency? It is stored in the dictionary next to each term, and it equals the length of the term's postings list. Queries use it to decide the order in which to process the terms (Faster query processing). Later, ranked retrieval uses it to give rare terms more weight.
document_frequency.py Python 
import os
from collections import defaultdict, Counter
from string import punctuation
from nltk.tokenize import sent_tokenize, TweetTokenizer

tokenizer = TweetTokenizer()

def preprocess_document(content):
    """
    Returns a list of tokens for a document's content.
    Tokens should not contain punctuation and should be lower-cased.
    """
    sentences = sent_tokenize(content)
    tokens = []
    for _sent in sentences:
        sent_tokens = tokenizer.tokenize(_sent)
        sent_tokens = [_tok.lower() for _tok in sent_tokens if _tok not in punctuation]
        tokens += sent_tokens
    return tokens

def prepare_dataset(documents_dir):
    """
    Returns list of documents in the documents_dir, where each document is a list of its tokens.
    """
    tokenized_documents = []
    for document in os.listdir(documents_dir):
        with open(os.path.join(documents_dir, document), errors='ignore') as outf:
            tokenized_documents.append(preprocess_document(outf.read()))
    print("Found documents: ", len(tokenized_documents))
    return tokenized_documents

def document_frequency(tokenized_documents):
    """
    Returns a dictionary {token: number of documents containing the token}
    """
    doc_freq = defaultdict(lambda: 0)
    for _document in tokenized_documents:
        for _token in set(_document):
            doc_freq[_token] += 1
    return doc_freq

print(preprocess_document("US wedding limousine crash kills 20. Kanye West, deletes social media profiles!"))
# ['us', 'wedding', 'limousine', 'crash', 'kills', '20', 'kanye', 'west', 'deletes', 'social', 'media', 'profiles']

tokenized_dataset = prepare_dataset('data/mini_newsgroups/sci.crypt/')   # Found documents:  100
df = document_frequency(tokenized_dataset)
print(Counter(df).most_common(10))
# [('path', 100), ('sci.crypt', 100), ('apr', 100), ('cantaloupe.srv.cs.cmu.edu', 100), ('message-id', 100),
#  ('date', 100), ('from', 100), ('subject', 100), ('newsgroups', 100), ('lines', 99)]

Try it: the dictionary of sci.crypt

These are the real document frequencies from the notebook's run on the 100 sci.crypt posts. Search a term, or click a bar to list the terms in that range.

Number of terms by document frequency (out of 100 documents).

💡 The most common "words" come from the headers, which every post has. The least common are typos, e-mail addresses and rare words. Most terms in the dictionary appear in just one document.

Index construction

Building the full index: pairs, sort, merge, split

Now we add the postings. The main step of index construction is sorting. It brings all occurrences of a term together, so we can write out its postings list in one go. Four steps turn a folder of documents into a dictionary and postings lists. Together they are the indexer stage of the pipeline.

  1. Extract pairs of (token, document_id): go through every document and output one pair per token. Also keep a map doc_id → file name.
  2. Sort by token: sorted(token_docid, key=itemgetter(0)). Python's sort is stable, and we produced the pairs in document order. So for each token, the document ids stay in ascending order.
  3. Merge token occurrences in a single document: equal neighbours (token, doc_id) collapse into (token, doc_id, term_freq).
  4. Split into dictionary and postings: dictionary term → (doc_freq, total_freq), postings term → [(doc_id, term_freq), …]. total_freq is how often the term occurs in the whole collection. We keep the term frequency in each document because ranked retrieval will need it.

💡 This sorts everything in memory. For collections that don't fit in memory, we do the same sort block by block on disk (IIR, chapter 4).

Try it: build an index step by step

Four short documents: three BBC headlines and one we made up (doc 3), so that a term repeats inside a document. Edit any document and the index rebuilds. Click a term to follow it through the steps.

build_index.py Python 
import os
from operator import itemgetter
from collections import defaultdict

def get_token_doc_id_pairs(category_dir):
    """
    Iteratively goes through the documents in the category_dir and constructs/returns:
    1. A list of (token, doc_id) tuples
    2. A dictionary of doc_id:doc_name
    """
    tkn_docid = []
    docid_docnm = {}
    for i, document in enumerate(os.listdir(category_dir)):
        with open(os.path.join(category_dir, document), errors='ignore') as outf:
            tkn_docid += [(token, i) for token in preprocess_document(outf.read())]
        docid_docnm[i] = document
    return (tkn_docid, docid_docnm)

token_docid, doc_ids = get_token_doc_id_pairs('data/mini_newsgroups/rec.autos/')
print(token_docid[:3])   # [('path', 0), ('cantaloupe.srv.cs.cmu.edu', 0), ('das-news.harvard.edu', 0)]

# sort by token
sorted_token_docid = sorted(token_docid, key=itemgetter(0))

def merge_token_in_doc_v2(sorted_token_docid):
    """(token, doc_id) pairs -> (token, doc_id, term_freq) tuples"""
    merged_tokens_in_doc = []
    for token, doc_id in sorted_token_docid:
        if merged_tokens_in_doc:
            prev_tok, prev_doc_id, prev_freq = merged_tokens_in_doc[-1]
            if prev_tok == token and prev_doc_id == doc_id:
                merged_tokens_in_doc[-1] = (token, doc_id, prev_freq + 1)
            else:
                merged_tokens_in_doc.append((token, doc_id, 1))
        else:
            merged_tokens_in_doc.append((token, doc_id, 1))
    return merged_tokens_in_doc

merged_token_in_docs = merge_token_in_doc_v2(sorted_token_docid)
print(merged_token_in_docs[-4:])
# [('zip', 49, 2), ('zx', 79, 1), ('zx-r', 94, 1), ("|'8", 71, 1)]

# split into dictionary and postings
dictionary = defaultdict(lambda: (0, 0))   # term: (doc_freq, total freq)
postings = defaultdict(lambda: [])         # term: [(doc_id, term_freq), ...]

for token, doc_id, term_freq in merged_token_in_docs:
    dictionary[token] = (dictionary[token][0] + 1, dictionary[token][1] + term_freq)

# usually implemented as linked lists
for token, doc_id, term_freq in merged_token_in_docs:
    postings[token].append((doc_id, term_freq))

print(dictionary['zip'], dictionary['zaphod.mps.ohio-state.edu'])   # (1, 2) (51, 52)
print(postings['zip'], postings['zaphod.mps.ohio-state.edu'][:3])   # [(49, 2)] [(3, 1), (14, 1), (17, 1)]

The result on rec.autos

Termdictionary[term]
(doc_freq, total freq)		postings[term]
(doc_id, term_freq)
zip(1, 2)[(49, 2)]
zaphod.mps.ohio-state.edu(51, 52)[(3, 1), (14, 1), (17, 1), …] (51 postings)

💡 The notebook also has merge_token_in_doc (v1), which counts with a dictionary whose keys are token + '##' + str(doc_id), and then splits each key back into its parts. It gives the same counts, but split('##') returns the doc id as a string. Also, the order of os.listdir depends on the machine, so your doc ids may differ from the notebook's output.

Querying

Boolean queries in the index

Once the index is built, a query never reads the documents. It looks up the postings list of each query term in the dictionary and combines the lists. AND intersects them, OR takes their union, AND NOT subtracts one from the other.

AND query: documents that contain both living and dead

For conjunctive (AND) queries we use a merging algorithm. It walks through the postings of the two words at the same time.

  • Living: 1 → 2 → 5 → 17 → 30 → 31 → 44 → 45 → 47
  • Dead: 5 → 17 → 44
  • Intersection: 5 → 17 → 44
📐 Merging two postings lists

Keep one pointer per list and compare the two document ids. If they are equal, add the id to the result and move both pointers forward. Otherwise, move the pointer at the smaller id. The merge takes linear time in the lengths of the two lists, and it only works if the postings of each word are sorted by document id.

\[ O(x + y), \quad x = df_{\text{living}},\; y = df_{\text{dead}} \]

Try it: merge two postings lists

Step through the merge. Switch the operator to see how OR and AND NOT change it. The lists are editable.

Merge log
and_query.py Python 
def and_query(postings, word1, word2):
    """
    merging postings lists of two words
    """
    postings_word1 = postings[word1]
    postings_word2 = postings[word2]

    documents_results = []

    postings_ind1, postings_ind2 = 0, 0
    while postings_ind1 < len(postings_word1) and postings_ind2 < len(postings_word2):
        doc_id1, doc_id2 = postings_word1[postings_ind1][0], postings_word2[postings_ind2][0]
        if doc_id1 == doc_id2:
            documents_results.append(postings_word1[postings_ind1][0])
            postings_ind1 += 1
            postings_ind2 += 1
        elif doc_id1 < doc_id2:
            postings_ind1 += 1
        elif doc_id1 > doc_id2:
            postings_ind2 += 1
    return documents_results

print(postings['living'])   # [(30, 1), (36, 1), (78, 1)]
print(postings['dead'])     # [(29, 1), (36, 1), (65, 1)]
print(and_query(postings, 'living', 'dead'))   # [36]

Questions

1What if we want the documents that contain \(N\) words?

Intersect the lists two at a time: merge two lists, then merge the result with the next list, and so on. Start with the shortest lists (increasing \(df\)). The intermediate result is never longer than the shortest list so far, so every later merge gets cheaper. If some term has \(df = 0\), stop: the answer is empty.

Total time is still linear in the total length of the postings, \(O(\sum_i df_i)\). Try the query planner below.

2How long do queries with NOT, OR and their combinations take?

x OR y: a union merge, \(O(x + y)\). The result can hold up to \(x + y\) documents.

x AND NOT y: also a merge, \(O(x + y)\). Keep the ids of \(x\) that the pointer in \(y\) does not hit.

NOT x on its own: the complement of the list. We have to scan all \(N\) document ids, so it costs \(O(N)\).

Combinations such as (a OR b) AND (c OR d): every operator is one linear merge, so the whole query is linear in the total size of the postings involved. To choose an order, estimate the size of each subquery (e.g. \(df_a + df_b\) for an OR) and process the smallest first. Switch the operator in the merge widget to compare.

3What are the downsides of Boolean queries?

No ranking: a document either matches or not, so all results look equally good.

Feast or famine: an AND of many terms often returns nothing, and an OR returns far too much.

Exact matching: no synonyms, spelling variants or partial matches. It also ignores how often a term occurs and how rare it is.

Hard to write: good Boolean queries need expert users, and most people just type a few words. These problems are why we move on to ranked retrieval.

Optimization

Faster query processing

A merge is linear in the lengths of the postings lists. There are two ways to do less work: process the terms in a good order, and skip over parts of long lists.

Process terms in order of increasing frequency

For an AND of many terms, first merge the two terms with the smallest \(df\), then merge the result with the next rarest term, and so on. The intermediate result is never longer than the shortest list, so every later merge is cheaper.

Try it: query planner for sci.crypt

Type an AND query. Using the real \(df\) values of sci.crypt, the widget compares the largest possible intermediate result for two orders: the terms as you typed them, and the terms by increasing frequency.

as typed   increasing df

Skip pointers

Can we merge faster than \(O(x + y)\)? Yes, if the index does not change too often. At indexing time, add skip pointers to the postings lists. They are shortcuts over postings that cannot be in the result.

  • How they are used: when the current id on one list is the smaller one, check its skip pointer. If the skip target is still ≤ the current id on the other list, jump there and skip everything in between. Otherwise, move forward one posting as usual.
  • Where to place them: it is a tradeoff. More skips mean shorter spans, so we can take them more often, but they cost more comparisons (and space). Fewer skips mean fewer comparisons, but the spans are long and we can rarely use them.
  • Heuristic: for a list of length \(L\), use \(\sqrt{L}\) evenly spaced skip pointers. This ignores how the query terms are distributed. It is also easy only if the index is fairly static, because updates keep changing \(L\).
  • Only for AND: an OR has to visit every posting anyway. Skips exist only on the stored lists, not on intermediate results.
  • ❗ On modern hardware they may not help. Loading the bigger postings list can cost more than the faster merge in memory saves (the lecture cites Bahle et al., 2002).

Try it: intersect with skip pointers

The arcs above a list are its skip pointers, and a thick arc is a skip that the merge takes. Compare the steps with and without skips on the three examples.

Merge log

💡 On the lecture slide's lists, this algorithm never takes a skip. The slide says that the skip from 8 to 31 on the lower list lets us jump past 17 and 21. But after both lists match 8, both pointers move on (to 16 and 17), past the start of that skip. The slide reasons with a look-ahead to 32, the next id after 16. IIR notes that there are several variants, depending on when the skip pointer is checked. The book's version of the figure (IIR Fig. 2.9) shows a skip that this algorithm does take: at 16 vs 41 it jumps to 28, avoiding 19 and 23.

Phrases

Phrase and proximity queries

We want to answer "stanford university" as a phrase, so that "I went to university at Stanford" is not a match. Users find phrase queries easy to understand, and as many as 10% of web queries are phrase queries. To answer them, it is no longer enough to store only term → documents.

A first attempt: biword indexes

  • Biwords: index every pair of consecutive terms as one dictionary term. "Friends, Romans, Countrymen" gives friends romans and romans countrymen. A two-word phrase query is then a single lookup.
  • Longer phrases: stanford university palo alto becomes "stanford university" AND "university palo" AND "palo alto". Without looking at the documents, we cannot check that the whole phrase occurs, so there can be false positives.
  • Extended biwords: tag the text with parts of speech and group the terms into nouns (N) and articles/prepositions (X). Then index every sequence of the form N X* N as one term. For example, catcher in the rye is N X X N.
  • Issues: false positives, and a much bigger dictionary. Biword indexes are not the standard solution.

Solution 2: positional indexes

In the postings, store for each document the positions at which the term occurs:

<be: 993427;
  1: 7, 18, 33, 72, 86, 231;
  2: 3, 149;
  4: 17, 191, 291, 430, 434;
  5: 363, 367, …>
  • Phrase queries: get the entries of each distinct term (for "to be or not to be": to, be, or, not). Start from the rarest and merge their doc:position lists. Now it is not enough for a document to contain the terms: be must occur one position after to, and so on.
  • Proximity queries: LIMIT! /3 STATUTE /3 FEDERAL /2 TORT, where /k means "within \(k\) words of" (on either side). The same merge works with a positional index. A biword index cannot answer these queries.

Try it: phrase and proximity queries

These are the four documents from the index builder (edit them there). Compare what each kind of index returns for the same query. Positions start at 0.

2

Positional index size

A positional index needs an entry for every occurrence, not one per document, so its size depends on document length. An average web page has fewer than 1,000 terms, but SEC filings, books and even some epic poems easily reach 100,000. For a term with frequency 0.1%:

Document sizePostingsPositional postings
1,00011
100,0001100
  • Rules of thumb (English-like languages): a positional index is 2–4 times as large as a non-positional one. Compressed, it takes about 35–50% of the size of the original text.
  • It is still the standard, because phrase and proximity queries are so useful, whether users type them or a ranking system uses them implicitly.

Combination schemes

  • For frequent phrases such as "Michael Jackson" or "Britney Spears", merging the positional lists again and again wastes work. It is even worse for "The Who": its words are very common, but the phrase is rare. Keep such phrases in a biword (phrase) index, and use the positional index for the rest.
  • Williams et al. (2004) also add a next-word index. On a typical mix of web phrase queries, this ran in ¼ of the time of a positional index alone and used 26% more space.
  • Zones (from the notebook): restrict a term to one part of the document, e.g. the Subject or From header of a post, the title or the author.

Summary: key takeaways

  1. Boolean retrieval: the answer is the set of documents that satisfy the query. We build an index once, in advance, instead of scanning the text for every query.
  2. Pipeline: documents → tokenizer → linguistic modules → indexer → inverted index.
  3. Incidence matrix: terms × documents. Queries become bitwise operations on rows, but the matrix is almost all zeros.
  4. Inverted index: a dictionary of terms with their \(df\), each pointing to a postings list of document ids sorted by id.
  5. Tokens to terms: tokenization, normalization, case folding, stop words, stemming or lemmatization; each choice trades recall against precision. Our preprocess_document tokenizes, drops punctuation and lower-cases.
  6. Construction: collect (token, doc_id) pairs → sort by token → merge into (token, doc_id, tf) → split into dictionary and postings.
  7. Queries: AND, OR, AND NOT are linear merges of sorted postings lists, \(O(x + y)\). A lone NOT costs \(O(N)\).
  8. Faster merges: process terms by increasing \(df\). Skip pointers (\(\sqrt{L}\) per list, AND only) jump over parts of long lists.
  9. Phrases: biword indexes are fast for two words but give false positives. Positional indexes answer phrase and proximity queries, at 2–4 times the size.
Test yourselfLab 01 quiz

27 auto-graded questions, 100 points: the Boolean model, dictionary and postings, from text to terms, Boolean merges and query planning, skip pointers, phrase and positional indexes, and case scenarios.

Start the quiz →

Resources used