Q-Gram Index

Formula#

Size (total number of entries in all inverted lists) for a vocabulary $v_1, \dots, v_n$:

Using the index. For a query $x$, padded like the index:

1. compute $Q_q(x)$,
2. fetch the inverted list of each q-gram of $Q_q(x)$,
3. merge these $|Q_q(x)|$ lists and count how often each id occurs.

If $y$ occurs $k$ times in the merged result, then $\mathrm{comm}_q(x, y) = |Q_q(x) \cap Q_q(y)| = k$. Words absent from the result have $\mathrm{comm}_q(x, y) = 0$; they only matter if the filter threshold of the Q-Gram Lemma is $\le 0$.

Properties#

• A q-gram index is an Inverted Index with different objects: a document index maps each word to document ids, a q-gram index maps each q-gram to word ids. The construction code from Lecture 1 carries over almost unchanged.
• Store ids, not the strings themselves.
• The merge takes time linear in the total length of the fetched lists, typically far less than computing (P)ED for every $y \in D$ (ES8: $|D| \approx 1.7$ million Wikidata entities).
• Padding must match the distance: left only for PED, both sides for ED (see Q-Gram > Padding). The lecture code pads both sides; ES8 (PED) pads the left side only.

Construction (lecture code, padding = "$" * (q - 1)):

def q_grams(self, x: str) -> list[str]:
    x = self.padding + x + self.padding        # ED setting; for PED drop the right padding
    return [x[i : i + self.q] for i in range(len(x) - self.q + 1)]

def build_from_file(self, file_name: str):
    with open(file_name, "r") as file:
        word_id = 0
        for line in file:
            word_id += 1
            word = line.split("\t", 2)[0].lower()
            for q_gram in self.q_grams(word):
                if q_gram not in self.inverted_lists:
                    self.inverted_lists[q_gram] = []
                self.inverted_lists[q_gram].append(word_id)

Example#

Building (exam WS 18/19, Task 3.1): words abba, bab, aba, $q = 2$, one $ on the left: $abba (id 1), $bab (id 2), $aba (id 3).

Querying (lecture): $x = \text{brei}$, $q = 2$, $\delta = 1$, PED. Padded $brei has the 2-grams $b, br, re, ei ($|Q_2(x)| = 4$):

$b : bangalore, beijing, berlin, …
br : brisbane, brussels, gibraltar, …
re : bangalore, freiburg, singapore, …
ei : beijing, freiburg, marseille, …

The threshold is $4 - 2 \cdot 1 = 2$. Merging, bangalore, beijing and freiburg occur at least twice; only they are verified: $\mathrm{PED}(\text{brei}, \text{bangalore}) = 3$ ✗, $\mathrm{PED}(\text{brei}, \text{beijing}) = 1$ ✓, $\mathrm{PED}(\text{brei}, \text{freiburg}) = 1$ ✓.

Sources#

• Slides 08, p. 23 (motivation), p. 24 (definition), p. 25 (using the index), p. 26 (example)
• DBIS_VL08 > Q-Gram Index, DBIS_VL08 > Definition, DBIS_VL08 > Using the index
• Exams: DBIS Exam WS1617 (not published) (Task 6, size formula), DBIS Exam WS1819 (not published) (Tasks 3.1–3.3), DBIS Exam WS2324 (not published) (Task 4.1), DBIS Exam WS2324-2 (not published) (Task 4.1)