Fuzzy Search

Formula#

Filter-then-verify algorithm (fuzzy prefix search, fixed $q$):

1. Pad $x$ with $q - 1$ $ on the left (see Q-Gram > Padding) and compute its q-grams; with left-only padding $|Q_q(x)| = |x|$.
2. Fetch the inverted list of each q-gram from the Q-Gram Index, merge them, and count for each word $y$ how often it occurs: this is $\mathrm{comm}_q(x, y)$.
3. Filter with the q-gram lemma, Corollary 2: keep only words with $$\mathrm{comm}_q(x, y) \ge |Q_q(x)| - q \cdot \delta.$$
4. Verify: compute $\mathrm{PED}(x, y)$ only for the survivors (with the $|x| + \delta + 1$ column cut-off) and return those with $\mathrm{PED}(x, y) \le \delta$.

For fuzzy search (ED), pad on both sides and filter with $\mathrm{comm}_q(x, y) \ge \max\{|Q_q(x)|, |Q_q(y)|\} - q \cdot \delta$ (Corollary 1).

def fuzzy_prefix_search(x, index, q, delta=1):
    x_padded = "$" * (q - 1) + x
    counts = {}
    for i in range(len(x_padded) - q + 1):
        qgram = x_padded[i:i + q]
        for word_id in index.get(qgram, []):
            counts[word_id] = counts.get(word_id, 0) + 1
    threshold = len(x_padded) - q + 1 - q * delta    # = |Q_q(x)| - q * delta = |x| - q * delta
    return [word_id for word_id, count in counts.items()
            if count >= threshold]                   # candidates; verify each with PED

Properties#

• Two challenges (as for keyword search in Lectures 1–2): a model of relevance, here (P)ED, and an index that finds the matches fast, here the q-gram index.
• Linear scan (compute (P)ED for every $y \in D$, as grep/agrep do) takes time linear in $|D|$: fine for medium-sized, too slow for large dictionaries.
• Correctness: the filter has no false negatives, because every match satisfies the bound of the q-gram lemma. If the threshold is $\le 0$, words not in any fetched list must be verified as well.
• Running time of the filter phase is linear in the total length of the fetched inverted lists, typically much smaller than verifying every word.
• Dictionary origins: popular queries from a query log (basis of query suggestions), words and common phrases of a text collection, entities of a knowledge graph (ES8: 1,736,613 Wikidata entities with popularity and synonyms).
• Application: context-sensitive autocompletion of entity names when writing SPARQL queries (QLever UI, see SPARQL and Knowledge Graphs); in ES9/ES10 the fuzzy prefix search becomes the backend of a search-as-you-type web app.

Example#

Exam WS 18/19, Task 3.2: index over abba (1), bab (2), aba (3), $q = 2$, one $ on the left; query $x = \text{aaab}$, $\delta = 1$.

1. $aaab → 2-grams $a, aa, aa, ab, so $|Q_2(x)| = 4$.
2. $a → {1, 3}, aa → (no list), ab → {1, 2, 3}: counts abba 2, bab 1, aba 2.
3. Threshold $4 - 2 \cdot 1 = 2$: candidates abba, aba.
4. $\mathrm{PED}(\text{aaab}, \text{abba}) = 2$, $\mathrm{PED}(\text{aaab}, \text{aba}) = 2$: no word matches.

Sources#

• Slides 08, p. 5 (problem), p. 6 (dictionaries), p. 7 (linear scan), p. 21 (filter algorithms), pp. 25–26 (with the q-gram index)
• Slides 07, p. 26 (autocompletion in QLever)
• DBIS_VL08 > Problem setting, DBIS_VL08 > Simple solution: linear scan, DBIS_VL08 > Filter algorithms, DBIS_VL08 > Using the index
• Exams: DBIS Exam WS1819 (not published) (Tasks 3.2, 3.3), DBIS Exam WS2324 (not published) (Task 4)