VL01 Introduction, Inverted Index, Zipf's Law

Contents of the Course#

Two demos, both made in Freiburg (Slide 3):

• QLever, a graph database implementing the RDF and SPARQL standards (Lecture 6). RDF is a data model that is a variant of relational databases; SPARQL is its query language, a variant of SQL. See SPARQL and Knowledge Graphs.
• GRASP, a question answering system: an agentic AI, driven by a large language model, that interactively explores a graph database like a human would.

Research topics behind the demos, all covered in the course (Slide 4):

Keyword Search: Problem and Naive Solution#

For Exercise Sheet 1 the collection is 126,648 movie descriptions; queries have any number of keywords and at most three matching documents are returned. Ranking and documents that contain only some of the keywords follow in Lecture 2.

Naive solution (Slide 15): iterate over all documents and check each one, like grep. At about 1 GB/s this is fine for small collections, but not at web scale: Google indexes around $10^{12}$ pages; at about 10 kB of text per page that is about 10 PB $= 10^4$ TB $= 10^7$ GB of text.

Inverted Index#

spielberg   6, 22, 24, 53, 62, 102, 148, 194, 197, …
dinosaurs   62, 194, 404, 560, 582, 713, 838, 1053, …

For Exercise Sheet 1, each inverted list contains a record ID at most once, even if the record contains the word several times. Alternative: store pairs (record ID, count), which Lecture 2 uses for ranking (term frequency).

See Inverted Index and Ranking for how this index is extended with scores.

Query Processing#

One keyword (Slide 17): the inverted list of the keyword already is the answer, i.e. the IDs of all records containing it.

Two keywords (Slide 18): let $L_1, L_2$ be the inverted lists of the two keywords. The sorted list of IDs that match both keywords is the intersection $L_1 \cap L_2$. For sorted lists this takes linear time $O(|L_1| + |L_2|)$ with the zipper algorithm: keep one pointer per list, advance the pointer at the smaller ID, and output the ID when both pointers point to the same ID.

def intersect(l1: list[int], l2: list[int]) -> list[int]:
    """Zipper intersection of two sorted lists in time O(|l1| + |l2|)."""
    result, i, j = [], 0, 0
    while i < len(l1) and j < len(l2):
        if l1[i] < l2[j]:
            i += 1
        elif l1[i] > l2[j]:
            j += 1
        else:
            result.append(l1[i])
            i += 1
            j += 1
    return result

For the example, $L_1 \cap L_2 = 62, 194, \dots$

The same principle merges the two lists, i.e. computes the IDs that match any of the two keywords (union); Lecture 2 uses merging with scores.

$k > 2$ keywords (Slide 19): let $L_1, \dots, L_k$ be the inverted lists. Do a sequence of pairwise intersections (or merges): $L_1 \cap L_2 \to L_{12}$, then $L_{12} \cap L_3 \to L_{123}$, and so on. Possible optimizations (not needed for the sheet):

• Order the lists such that $|L_1| \le |L_2| \le \dots \le |L_k|$. This minimizes the lengths of the intermediate results.
• $k$-way intersect or merge in time $O(\log k \cdot \sum_i |L_i|)$.

Tokenization#

To build the index, the text has to be broken into words (Slide 20). Conceptually simple: define a set of word characters and a set of separator characters; words are the maximal sequences of word characters. For Exercise Sheet 1, a-z and A-Z are the word characters and everything else is a separator.

Construction of an Inverted Index#

Store the index in a map from strings (words) to arrays of ints (record IDs) (Slide 21). Construction algorithm:

1. Iterate over all records, keeping track of the record ID.
2. For each record, iterate over all the words it contains.
3. For each word occurrence, append the ID of the current record to the word’s inverted list (create an empty list first if the word is new).

Since record IDs are visited in increasing order, every inverted list is automatically sorted. Code written in the lecture (public/code/lecture-01/inverted_index.py):

import re

class InvertedIndex:
    def __init__(self):
        self.inverted_lists: dict[str, list[int]] = {}

    def build_from_file(self, file_name: str):
        """
        >>> ii = InvertedIndex()
        >>> ii.build_from_file("example.tsv")
        >>> ii.inverted_lists
        {'a': [1, 2], 'movie': [1, 1, 3], 'film': [2]}
        """
        with open(file_name, "r") as file:
            record_id = 0
            for line in file:
                record_id += 1
                title, description, _ = line.split("\t", 2)
                words = re.findall(r"[A-Za-z]+", description)
                for word in words:
                    word = word.lower()
                    if word not in self.inverted_lists:
                        self.inverted_lists[word] = []
                    self.inverted_lists[word].append(record_id)

Zipf’s Law#

This is an empirical observation that holds for most texts and languages, named after George Kingsley Zipf (1902–1950, American linguist). Plotting $n$ on the x-axis against $F_n$ on the y-axis gives a curve that looks like a hyperbola. In words: there are only a few very frequent words, and most words are rare.

With a constant $C > 0$, $F_n = C \cdot n^{-\alpha}$ is equivalent to

so in a log-log plot Zipf’s law shows up as a falling straight line with slope $-\alpha$ and intercept $\log C$.

References#

Manning, Raghavan, Schütze: Introduction to Information Retrieval (online at informationretrieval.org); Wikipedia: Merge algorithm, Inverted index, Zipf’s law (Slide 27).

Concepts#

• Inverted Index — central data structure: word → sorted list of record IDs, built in one linear pass
• List Intersection — zipper algorithm intersects two sorted inverted lists in linear time (AND queries); merging gives OR queries
• Zipf’s Law — empirical power law $F_n \sim 1/n^\alpha$ of word frequencies, a line in the log-log plot
• Keyword Search — problem setting: return all documents containing all query keywords
• Tokenization — splitting text into maximal sequences of word characters
• K-way Merge — intersect/merge $k$ lists at once in $O(\log k \cdot \sum_i |L_i|)$