https://patents.google.com/patent/US7536408B2/pdf

Abstract

An information retrieval system uses phrases to index, retrieve, organize and describe documents. Phrases are identified that predict the presence of other phrases in documents. Documents are the indexed according to their included phrases. Related phrases and phrase extensions are also identified. Phrases in a query are identified and used to retrieve and rank documents. Phrases are also used to cluster documents in the search results, create document descriptions, and eliminate duplicate documents from the search results, and from the index.

Classifications

Typ	Klassifikation / Wert
International Patent Classification (IPC)	G06F 7/00 (2006.01) [Col. 1, Line 51]
U.S. Classification (USPC)	707/102; 707/1 [Col. 1, Line 52]
Cooperative Patent Classification (CPC)	G06F 17/3053; G06F 17/30554; G06F 17/30861 [Col. 1, Line 52]

Strukturelle Zusammenfassung

Das Patent offenbart eine Suchmaschinen-Architektur für großskalige Korpora, die von der traditionellen termbasierten (Einzelwort-) Indizierung auf ein phrasen basiertes System umstellt [Col. 2, Zeilen 25–48].

System-Architektur: Das System umfasst ein Indexierungssystem (110), ein Suchsystem (120), ein Präsentationssystem (130) und einen Front-End-Server (140), die auf einen Dokumentenindex (150) und eine Phrasen-Datenbank (160) zugreifen [Col. 6, Zeilen 1–15].

Phrasen-Identifikation: Mittels eines primären Phrasenfensters (Phrase Window, Länge $n=2$ bis $5$) werden Kandidaten-Phrasen im Text traversiert [Col. 6, Zeilen 55–65]. Statistiken wie Dokumentenhäufigkeit $P(p)$, Instanzhäufigkeit $S(p)$ und Formatierungsmarkierungen (Interesting Instances $M(p)$ wie HTML-Tags, Fettungen oder Links) bestimmen die Klassifikation in Good, Possible und Bad Phrases [Col. 7, Zeilen 25–45].

Co-Okkurrenz & Information Gain: Über ein sekundäres Fenster ($\pm K$ Terme, z. B. 30 Wörter) wird eine Ko-Okkurrenz-Matrix ($G$) gepflegt [Col. 7, Zeilen 43–67]. Das System berechnet den Information Gain ($I$) als prädiktives Maß zwischen Phrasen [Col. 10, Zeilen 39–44]. Phrasen mit einem $I$ unter einem Schwellenwert (typischerweise $1.5$) werden verworfen (pruning) [Col. 10, Zeilen 35–48]. Phrasen, die nur ihre eigenen Extensions vorhersagen, werden als Incomplete Phrases klassifiziert und für Query-Erweiterungen genutzt [Col. 10, Zeilen 11–35].

Indexierung & Bit-Vektoren: Dokument-IDs werden in Posting Lists gespeichert. Jedes Dokument enthält einen Related Phrase Bit Vector (Bi-Bit-Vektor), der das Vorkommen verwandter Phrasen abbildet [Col. 13, Zeilen 38–55]. Ankertexte (Anchor Text) von Hyperlinks werden zur Berechnung von Outlink- und Inlink-Scores herangezogen, um Suchmanipulationen (Google Bombing) zu verhindern [Col. 15, Zeile 1 – Col. 16, Zeile 25].

Such- und Ranking-Logik: Queries werden geparst, um gültige Phrasen ($Q_p$) und verwandte Phrasen ($Q_r$) zu ermitteln [Col. 17, Zeilen 1–44]. Das System nutzt Bit-Vektor-Vergleiche für Intersection Shortcuts, um Posting-Listen-Kreuzungen abzukürzen [Col. 18, Zeilen 10–50]. Das Ranking erfolgt über eine gewichtete Kombination aus Body- und Anchor-Hits [Col. 20, Zeilen 35–65]:
$$\text{Score} = 0.30 \cdot (\text{body hit score}) + 0.70 \cdot (\text{anchor hit score})$$

Präsentation & Personalisierung: Das Präsentationssystem generiert dynamische Taxonomien (Themen-Cluster) [Col. 23, Zeilen 15–35], personalisierte Snippets basierend auf Nutzerprofilen (User Models) [Col. 22, Zeilen 31–48] und eliminiert Duplikate mittels Sentence-Hashing [Col. 25, Zeile 35 – Col. 26, Zeile 10].

Claims

Das Patent umfasst 20 Ansprüche (Claims 1–20), aufgeteilt in methodische Schritte, Systemarchitekturen und computerlesbare Speichermedien:

Unabhängige Ansprüche: Claim 1 (Verfahren zur Dokumentenindizierung mittels Information-Gain-Schwellenwert), Claim 10 (Verfahren zur Indizierung basierend auf gültigen Phrasen), Claim 12 (Computersystem mit phrasenbasiertem Index), Claim 13 (Speichermedium mit Programmanweisungen), Claim 16 (Verfahren zur Dokumentenindizierung in einem Index), Claim 17 (Verfahren inklusive Anker-Text-Link-Score-Berechnung) und Claim 20 (Computersystem mit phrasenbasiertem Index und Posting Listen).

Abhängige Ansprüche: Präzisieren die Fenster-Traversierung (Claim 2), Schwellenwerte wie $100$ oder $1.5$ (Claims 3, 11), sekundäre verwandte Phrasen (Claim 5), Primär- und Sekundärtopics (Claim 7), sowie Inlink- und Outlink-Berechnungen (Claims 18–19).

1. ARCHITEKTUR & DATENFLUSS

Datenstrukturen:

Index (150): Speichert Dokument-IDs (URLs) in phrasenbasierten Posting-Listen [Col. 6, Zeilen 11–14].

Phrase Data Store / Repository (160): Hält statistische Zählwerte, Good/Possible/Bad/Incomplete Phrase Listen [Col. 6, Zeilen 12–14].

Co-Occurrence Matrix (212): $m \times m$-Matrix zur Erfassung roher ($R$), disjunktiver ($D$) und konjunktiver ($C$) Ko-Okkurrenzen [Col. 7, Zeilen 43–67].

Related Phrase Bit Vector: Bi-Bit-Vektor pro Dokument in einer Posting-List zur Kodierung der Präsenz verwandter Phrasen [Col. 13, Zeilen 38–55].

Cluster Bit Vector: Bit-Sequenz zur Abbildung von Orthogonalitäts- und Cluster-Beziehungen [Col. 11, Zeilen 58–66].

User Model: Profilstruktur aus historischen Queries und verknüpften Phrasen/Cluster-Zählern [Col. 22, Zeilen 31–48].

Hash Table: Speicherstruktur für verkettete Dokument-Sätze zur Duplikaterkennung [Col. 26, Zeilen 1–10].

Sequenzieller Datenfluss:

Input / Crawling: Traversierung des Textkorpus mit primärem Phrasenfenster ($n$-Terme) [Col. 6, Zeilen 50–65].

Statistik-Aggregat: Sammlung von $P(p)$, $S(p)$ und Formatierungsmarkierungen $M(p)$ [Col. 7, Zeilen 25–45].

Pruning: Berechnung des Information Gain $I(i,k)$ über die Ko-Okkurrenz-Matrix im sekundären Fenster ($\pm 30$ Wörter). Eliminierung von Phrasen unterhalb des Schwellenwerts [Col. 10, Zeilen 35–48].

Index-Population: Erstellung von Posting Lists und Zuweisung von Bit-Vektoren [Col. 13, Zeilen 1–15].

Query Input: Entgegennahme einer Suchanfrage vom Client [Col. 17, Zeilen 1–10].

Query Expansion: Erkennung von Phrasen und Ersetzung unvollständiger Phrasen durch Phrase Extensions [Col. 17, Zeilen 11–44].

Intersection Shortcuts: Direkte Nutzung von Bit-Vektoren zur Filterung von Dokumenten ohne vollständige Kreuzung der Posting Lists [Col. 18, Zeilen 10–50].

Scoring & Ranking: Berechnung der Dokument-Scores aus Body- und Anchor-Hits [Col. 20, Zeilen 35–65].

Output: Dynamische Cluster-Taxonomie, Snippet-Generierung und Duplikat-Bereinigung vor der Darstellung im Client [Col. 23, Zeile 1 – Col. 26, Zeile 10].

DIE FORMELN & METRIKEN (MATHEMATISCHES MODELL)

Bedingte Entitäten-Ko-Okkurrenz ($C$):
$$C(E, RE_j) = \frac{P(E, RE_j)}{P(E)}$$

$P(E)$: Wahrscheinlichkeit des Auftretens der Entitätsreferenz $E$ im Textkorpus [Col. 12, Zeilen 30–34].
$P(E, RE_j)$: Wahrscheinlichkeit des gemeinsamen Auftretens von $E$ und der verwandten Entität $RE_j$ [Col. 12, Zeilen 30–34].

Alternativer Ko-Okkurrenz-Koeffizient:
$$C(E, RE_j) = \frac{N(E, RE_j)}{N(E) + N(RE_j) – N(E, RE_j)}$$

$N(E)$: Anzahl Instanzen von $E$ [Col. 12, Zeilen 45–52].
$N(RE_j)$: Anzahl Instanzen von $RE_j$ [Col. 12, Zeilen 45–52].
$N(E, RE_j)$: Anzahl gemeinsamer Instanzen [Col. 12, Zeilen 45–52].

Notable Entity Type Metric ($N$):
$$N = \frac{G}{n}$$

$G$: Globale Popularitätsmetrik (basierend auf Nutzer-Auswahl, Klicks, Links) [Col. 13, Zeilen 1–4].
$n$: Rang des Entitätstyps in einer Domain (Notable Entity Type Rank) [Col. 13, Zeilen 1–4].

Contribution Metric ($C$):
$$C = \frac{\sum_{n=0}^{k} S_n \cdot \beta^n}{\sum_{n=0}^{k} \beta^n}$$

$S_n$: Review-Wert eines Beitrags $n$ aus einem Satz von $k$ Beiträgen [Col. 14, Zeilen 5–13].
$\beta$: Konstanter Gewichtungsfaktor im Wertebereich $[0, 1]$ [Col. 14, Zeilen 5–13].

Prize Metric ($P$):
$$P = \frac{\sum_{n=0}^{k} A_n \cdot \delta^n}{\sum_{n=0}^{k} \delta^n}$$

$A_n$: Quantifizierbarer Wert einer Auszeichnung $n$ (z. B. Oscar, Nobelpreis) [Col. 14, Zeilen 1–5].
$\delta$: Konstanter Gewichtungsfaktor im Wertebereich $[0, 1]$ [Col. 14, Zeilen 1–5].

Erwartete Ko-Okkurrenz-Rate ($E$):
$$E(j,k) = E(g_i) \cdot E(g_k) \quad \text{wobei } E(g_i) = \frac{N(g_i)}{T}$$

$N(g_i)$: Dokumentenanzahl mit Phrase $g_i$ [Col. 16, Zeilen 20–25].
$T$: Gesamtzahl gecrawlter Dokumente im Korpus [Col. 16, Zeilen 20–25].

Tatsächliche Ko-Okkurrenz-Rate ($A$):
$$A(j,k) = \frac{R(k)}{T}$$

$R(k)$: Rohe Ko-Okkurrenz-Zahl im sekundären Fenster [Col. 16, Zeilen 26–30].

Information Gain ($I$):
$$I(i,k) = \frac{A(j,k)}{E(j,k)}$$

Schwellenwert: $I(i,k) > 1.5$ (bevorzugt $1.1$ bis $1.7$) [Col. 16, Zeilen 39–52].

Dokument-Score (Scoring-Funktion):
$$\text{Score} = 0.30 \cdot (\text{body hit score}) + 0.70 \cdot (\text{anchor hit score})$$

$\text{body hit score}$: Numerischer Wert des höchstwertigen verwandten Phrasen-Bit-Vektors [Col. 20, Zeilen 35–40].
$\text{anchor hit score}$: Summiertes Produkt aus Outbound- und Inbound-Bit-Vektoren referenzierender Dokumente [Col. 20, Zeile 60 – Col. 21, Zeila 5].

LOGISCHE ARGUMENTATION & SCHALTUNGS-LOGIK

Bedingung für Phrasen-Validierung: Wenn $P(p) > 10 \land S(p) > 20$ (Dokumenten- und Instanzhäufigkeit) oder $M(p) > 5$ (Formatierungsmarkierungen wie Fettungen/Hyperlinks), wird ein Kandidat von der Possible Phrase List in die Good Phrase List verschoben [Col. 8, Zeilen 10–25].

Ausschlusslogik (Bad Phrase): Wenn $P(p) < 2 \land M(p) = 0$, wird die Phrase als irrelevant eingestuft [Col. 8, Zeilen 35–45].

Pruning-Logik für Incomplete Phrases: Wenn eine Phrase $g_i$ ausschließlich Super-Sequenzen (Phrase Extensions) vorhersagt, besitzt sie keine eigenständige semantische Abgeschlossenheit und wird in die Incomplete Phrase List ausgelagert [Col. 10, Zeilen 1–20]. Dies verhindert falsche Direkt-Treffer und optimiert die Abfrage-Vervollständigung [Col. 10, Zeilen 20–35].

Intersection Shortcut Logik: Bei Queries mit zwei Phrasen $Q_1$ und $Q_2$:

Fall 1 ($Q_2$ ist verwandte Phrase von $Q_1$): Das System scannt direkt den Bit-Vektor in $Q_1$s Posting List. Ist das Bit für $Q_2$ nicht gesetzt ($0$), wird das Dokument sofort eliminiert, ohne die Posting List von $Q_2$ zu laden [Col. 18, Zeilen 35–50].
Fall 2 (Unberührt/Unabhängig): Standard-Verschneidung der Posting Lists [Col. 18, Zeilen 51–60].
Fall 3 (Gemeinsame verwandte Phrase): Maskierung und Filterung über Bit-Masken-Operationen [Col. 18, Zeile 61 – Col. 19, Zeile 10].

Domänenspezifische Gewichtung: Die Gewichte ($a, b, c, d$) der Scoring-Formel werden dynamisch auf Basis der Entitäts-Domain (z. B. Movie, People, Book) angepasst [Col. 14, Zeilen 32–45].

CODE- / SCHEMA-ÜBERSETZUNG (PYTHON PSEUDO-CODE)

import numpy as np
from typing import List, Dict, Set, Tuple

class PhraseBasedRetrievalEngine:
    def __init__(self, ig_threshold: float = 1.5, secondary_window: int = 30):
        self.ig_threshold = ig_threshold
        self.window_size = secondary_window
        self.good_phrases: Set[str] = set()
        self.incomplete_phrases: Set[str] = set()
        self.posting_lists: Dict[str, Set[str]] = {}  # phrase -> set of doc_ids
        self.doc_frequencies: Dict[str, int] = {}     # phrase -> document count
        self.total_docs: int = 0

    def register_occurrence(self, phrase: str, doc_id: str):
        if phrase not in self.posting_lists:
            self.posting_lists[phrase] = set()
        self.posting_lists[phrase].add(doc_id)
        self.doc_frequencies[phrase] = len(self.posting_lists[phrase])

    def calculate_information_gain(self, p1: str, p2: str, actual_co_occurrence: int) -> float:
        df1 = self.doc_frequencies.get(p1, 0)
        df2 = self.doc_frequencies.get(p2, 0)

        if self.total_docs == 0 or df1 == 0 or df2 == 0:
            return 0.0

        prob_1 = df1 / self.total_docs
        prob_2 = df2 / self.total_docs
        expected_rate = prob_1 * prob_2

        actual_rate = actual_co_occurrence / self.total_docs

        if expected_rate == 0.0:
            return 0.0

        return actual_rate / expected_rate

    def evaluate_phrase_promotion(self, phrase: str, doc_count: int, total_instances: int, interesting_instances: int) -> bool:
        cond_a = (doc_count > 10) and (total_instances > 20)
        cond_b = (interesting_instances > 5)

        if cond_a or cond_b:
            self.good_phrases.add(phrase)
            return True
        return False

    def score_document(self, query_phrases: List[str], doc_bit_vector: List[int], anchor_hit_score: float) -> float:
        # Body Hit Score aus Bit-Vektor
        bit_string = "".join(map(str, doc_bit_vector))
        body_hit_score = float(int(bit_string, 2)) if bit_string else 0.0

        # Lineare Kombination gemäß Patent (0.30 Body + 0.70 Anchor)
        final_score = (0.30 * body_hit_score) + (0.70 * anchor_hit_score)
        return final_score

    def shortcut_intersection(self, q1: str, q2: str, q1_bit_vectors: Dict[str, List[int]]) -> Set[str]:
        # Shortcut-Logik (Fall 1): Prüft via Bit-Vektor, ob Q2 im Dokument von Q1 präsent ist
        valid_docs = set()
        if q1 not in self.posting_lists:
            return valid_docs

        for doc_id in self.posting_lists[q1]:
            bit_vector = q1_bit_vectors.get(doc_id, [])
            # Wenn Q2 im Bit-Vektor kodiert ist, Dokument direkt übernehmen
            if self._is_phrase_set_in_vector(q2, bit_vector):
                valid_docs.add(doc_id)
        return valid_docs

    def _is_phrase_set_in_vector(self, phrase: str, bit_vector: List[int]) -> bool:
        # Repräsentiert die Bit-Prüfung in der Posting List
        return len(bit_vector) > 0 and bit_vector[0] == 1