Information Retrieval Module 1 IA Preparation

Fill-in-the-blank practice flashcards covering Module 1 of Information Retrieval, including Boolean retrieval, index construction (BSBI, SPIMI, MapReduce), index compression (gap, variable-byte), tokenization, stemming vs. lemmatization, skip pointers, and wildcard queries.

Information Retrieval mainly deals with __________ text, whereas Data Retrieval deals mainly with structured data.

unstructured or semi-structured

A term-document incidence matrix for $1,000,000$ documents and $500,000$ terms contains $500$ billion entries, but storing it directly is impractical because the matrix is extremely __________.

sparse

Under the Porter stemmer rules, the suffix replacement rule for SSES transforms it into __________.

SS

A stem produced by stemming does not necessarily have to be a valid English word, while a lemma produced by lemmatization is normally a valid __________ form.

dictionary

Removing stop words can harm retrieval quality in phrase queries such as "__________", where the exact phrase structure would otherwise be lost.

President of the United States

To process an AND query with multiple terms efficiently, terms should be processed in increasing order of __________.

postings-list length

As a dictionary data structure, a __________ is preferred over a hash table when the dictionary is stored on disk and ordered or prefix searching is required.

B-tree

In a permuterm index, the wildcard query he*o is rotated so that the wildcard symbol appears at the end, resulting in the search key __________.

o$he*

The Levenshtein edit distance between the strings "recieve" and "receive" is equal to __________.

$$2$$

A sequence of $k$ characters used to generate candidate spelling corrections by identifying shared segments is known as a __________.

k-gram

The phonetic encoding algorithm Soundex assigns the same code, __________, to both "Robert" and "Rupert".

R163

Unlike BSBI, the SPIMI index construction algorithm avoids the explicit sorting of term-document pairs by directly constructing __________ in memory.

postings lists

Applying gap encoding to the postings list [3, 7, 8, 20, 21, 25] transforms it into the sequence of gaps: __________.

[3, 4, 1, 12, 1, 4]

Storing the postings list [3, 7, 8, 20, 21, 25] as raw 32-bit integers requires $24$ bytes, whereas gap plus variable-byte encoding requires $6$ bytes, achieving a compression ratio of __________.

$$4 : 1$$

When dictionary terms are stored in lexicographic order, __________ reduces space by storing common prefixes once and recording only the differing suffixes.

front coding

The process of determining where one document begins and where it ends in a collection is called document __________.

delineation

In text processing, a distinct token instance before case normalization is called a type, whereas after normalization and processing it is referred to as a __________.

term

A grouping of different surface forms mapped to a single normalized representation (such as { USA, U.S.A. } ightarrow \text{usa}) is termed an __________.

equivalence class

A common heuristic strategy is to place skip pointers in a postings list at intervals of about __________, where $P$ is the length of the postings list.

$$\sqrt{P}$$

Skip pointers are useful for speeding up __________ queries, but are not generally useful for OR queries because every posting from both lists may be needed in the result.

AND

Unlike a biword index which stores consecutive pairs of words, a __________ stores the exact positions where each term occurs to support arbitrary-length phrase queries.

positional index

In MapReduce-based indexing, the __________ phase groups all occurrences of the same term together across mappers before passing them to the reducers.

shuffle