DE102021203300A1 - Computerimplementiertes Verfahren für Schlüsselwortsuche in einem Wissensgraphen - Google Patents

Abstract

Computerimplementiertes Verfahren (300), Einrichtung (200) und ein Computerprogramm für Schlüsselwortsuche in einer Datenmenge, wobei Daten der Datenmenge durch einen Wissensgraphen (100) dargestellt werden, wobei der Wissensgraph (100) Knoten, die Entitäten der Datenmenge darstellen, und Kanten, die Beziehungen zwischen den Entitäten darstellen, umfasst, wobei das Verfahren (300) die folgenden Schritte umfasst:Empfangen (302) einer Schlüsselwortabfrage, umfassend eine Menge von Schlüsselwörtern;Inrangfolgebringen (304) von Knoten des Wissensgraphen basierend auf einem kürzesten Pfad zu Schlüsselwortknoten, wobei ein Schlüsselwortknoten ein Knoten ist, der mit zumindest einem Schlüsselwort der Schlüsselwortabfrage übereinstimmt;Auswählen (306) der kleinsten Menge von Schlüsselwortknoten unter allen Mengen von Schlüsselwortknoten, umfassend zumindest einen Schlüsselwortknoten für jedes Schlüsselwort der Menge von Schlüsselwörtern.Bestimmen (308), basierend auf der kleinsten Menge von Schlüsselwortknoten und basierend auf einer Anzahl von in Rangfolge gebrachten Knoten, einer optimalen Pfadmenge, wobei die optimale Pfadmenge Pfade im Wissensgraphen (100) umfasst, die Knoten verbinden, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen und wobei die optimale Pfadmenge optimal bezüglich minimaler Kosten der Pfadmenge ist, wobei die Kosten auf einer Linearkombination des Gesamtgewichts von Knoten der optimalen Pfadmenge und paarweisen semantischen Abständen zwischen den Knoten der optimalen Pfadmenge basieren, undExtrahieren (310) einer Antwort auf die Schlüsselwortabfrage aus der optimalen Pfadmenge.

Description

• Hintergrund
• Die Erfindung bezieht sich auf eine Einrichtung und ein Verfahren für Schlüsselwortsuche in einer Datenmenge, wobei Daten der Datenmenge durch einen Wissensgraphen dargestellt werden. Ein Ergebnis der Suche kann automatisch bestimmt werden durch Finden eines Untergraphen, der eine Kostenfunktion optimiert.
• Offenbarung
• Eine Ausführungsform bezieht sich auf ein computerimplementiertes Verfahren für Schlüsselwortsuche in einer Datenmenge, wobei Daten der Datenmenge durch einen Wissensgraphen dargestellt werden, wobei der Wissensgraph Knoten, die Entitäten der Datenmenge darstellen, und Kanten, die Beziehungen zwischen den Entitäten darstellen, umfasst, wobei das Verfahren die folgenden Schritte umfasst:
• Empfangen einer Schlüsselwortabfrage, umfassend eine Menge von Schlüsselwörtern;
• Inrangfolgebringen von Knoten des Wissensgraphen basierend auf einem kürzesten Pfad zu Schlüsselwortknoten, wobei ein Schlüsselwortknoten ein Knoten ist, der mit zumindest einem Schlüsselwort der Schlüsselwortabfrage übereinstimmt;
• Auswählen der kleinsten Menge von Schlüsselwortknoten unter allen Mengen von Schlüsselwortknoten, umfassend zumindest einen Schlüsselwortknoten für jedes Schlüsselwort der Menge von Schlüsselwörtern;
• Bestimmen, basierend auf der kleinsten Menge von Schlüsselwortknoten und basierend auf einer Anzahl von in Rangfolge gebrachten Knoten, einer optimalen Pfadmenge, wobei die optimale Pfadmenge Pfade im Wissensgraphen umfasst, die Knoten verbinden, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen und wobei die optimale Pfadmenge optimal bezüglich minimaler Kosten der Pfadmenge ist, wobei die Kosten auf einer Linearkombination des Gesamtgewichts von Knoten der optimalen Pfadmenge und paarweisen semantischen Abständen zwischen den Knoten der optimalen Pfadmenge basieren, und
• Extrahieren einer Antwort auf die Schlüsselwortabfrage aus der optimalen Pfadmenge.
• Die kleinste Menge von Schlüsselwortknoten ist die kleinste Menge unter allen Mengen von Schlüsselwortknoten, die zumindest einen Schlüsselwortknoten für jedes Schlüsselwort der Menge von Schlüsselwörtern umfasst.
• Basierend auf der kleinsten Menge von Schlüsselwortknoten und basierend auf einer Anzahl von in Rangfolge gebrachten Knoten wird eine optimale Pfadmenge bestimmt. Die Anzahl von in Rangfolge gebrachten Knoten kann angegeben sein. Die Anzahl kann beispielsweise in Abhängigkeit von der Größe des Wissensgraphen variieren.
• Eine Pfadmenge wird als eine Menge von Pfaden betrachtet, die einen gemeinsamen Wurzelknoten mit Knoten verbinden, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen.
• Die optimale Pfadmenge wird als die Menge von Pfaden mit minimalen Kosten betrachtet.
• Die Antwort auf die Schlüsselwortabfrage basiert auf der optimalen Pfadmenge. Daher ist die Antwort selbst optimal hinsichtlich der minimalen Kosten.
• Die Kosten der optimalen Pfadmenge basieren auf einer Linearkombination des Gesamtgewichts von Knoten der optimalen Pfadmenge und paarweisen semantischen Abständen zwischen den Knoten der optimalen Pfadmenge.
• Durch Bestimmen der optimalen Pfadmenge basierend auf der kleinsten Menge von Schlüsselwortknoten und basierend auf einer Anzahl von in Rangfolge gebrachten Knoten verarbeitet das Verfahren nicht jeden Knoten im Wissensgraphen, sondern nur vielversprechende Knoten. Daher kann die Berechnung der Antwort effizient beschleunigt werden, während der Berechnungsaufwand verringert wird.
• Gemäß einer Ausführungsform stellt das Gesamtgewicht eines Knotens Salienz dar, und/oder der paarweise semantische Abstand zwischen zwei Knoten stellt eine semantische Zusammengehörigkeit dar. Gewichte werden in dem Wissensgraphen zu seinen Knoten und/oder Kanten zugeordnet. Semantische Abstände werden in dem Wissensgraphen zu Paaren seiner Knoten zugeordnet. Die Gewichte und semantischen Abstände werden vorzugsweise vorab berechnet und vorab gespeichert, beispielsweise in einem Hauptspeicher oder einer Datenbank, beispielsweise zusammen mit dem Wissensgraphen.
• Auffälligere (salientere) Graphenelemente umfassen kleinere Gewichte. Weniger auffällige Graphenelemente umfassen größere Gewichte. Semantischer Abstand sollte nicht mit Graphenabstand verwechselt werden. Tatsächlich können zwei Entitäten, die in der Graphenstruktur nahe beieinander sind, semantisch weit voneinander entfernt sein, z. B. zu nicht verwandten Themen im Wissensgraphen gehören. Stärker zusammengehörende Graphenelemente umfassen einen kleinen semantischen Abstand. Weniger zusammengehörende Graphenelemente umfassen einen größeren semantischen Abstand. Durch Einbeziehen des semantischen Abstands in das Verfahren kann die semantische Zusammengehörigkeit einer Antwort verbessert werden.
• Das Verfahren löst das Problem des Berechnens von semantisch zusammengehörenden Antworten auf Schlüsselwortabfragen in einer effizienten Weise.
• Gemäß einer Ausführungsform umfasst der Schritt des Bestimmens einer optimalen Pfadmenge einen iterativen Prozess basierend auf dem Bestimmen einer lokal optimalen Pfadmenge, wobei die lokal optimale Pfadmenge Pfade im Wissensgraphen umfasst, die den Wurzelknoten mit Knoten verbinden, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen, und wobei die lokal optimale Pfadmenge optimal hinsichtlich minimaler Kosten der Pfadmenge für den entsprechenden Wurzelknoten ist, wobei der iterative Prozess die folgenden Schritte umfasst:
• Bestimmen einer Gesamtmindestlänge eines Pfades der lokal optimalen Pfadmenge durch Bestimmen, für jeden Schlüsselwortknoten, des kürzesten Pfades vom entsprechenden Wurzelknoten;
• Bestimmen einer unteren Grenze der Kosten der lokal optimalen Pfadmenge; Bestimmen der Kosten jedes Pfades, der größer als die Gesamtmindestpfadlänge ist;
• Vergleichen der Kosten jedes Pfades, der größer als die Gesamtmindestpfadlänge ist, mit der unteren Grenze;
• Erhalten der Pfadmenge mit den minimalen Kosten als die lokal optimale Pfadmenge.
• Gemäß einer Ausführungsform umfasst der Schritt des Bestimmens einer optimalen Pfadmenge Folgendes:
• Erhalten der lokal optimalen Pfadmenge mit den minimalen Kosten als die optimale Pfadmenge.
• Gemäß einer Ausführungsform wird der Schritt des Bestimmens, für einen Wurzelknoten des Wissensgraphen, einer lokal optimalen Pfadmenge mit zumindest einer Kürzungsstrategie verbessert.
• Gemäß einer Ausführungsform umfasst der Schritt des Extrahierens einer Antwort aus der optimalen Pfadmenge Folgendes:
• Zusammenführen der Pfade der optimalen Pfadmenge in einen Untergraphen des Wissensgraphen.
• Gemäß einer Ausführungsform umfasst der Schritt des Extrahierens einer Antwort aus der optimalen Pfadmenge ferner Folgendes:
• Entfernen unnötiger Knoten und Kanten aus dem Untergraphen.
• Weitere Ausführungsformen beziehen sich auf eine Einrichtung zur Schlüsselwortsuche in einer Datenmenge, wobei Daten der Datenmenge durch einen Wissensgraphen dargestellt werden, wobei der Wissensgraph Knoten, die Entitäten der Datenmenge darstellen, und Kanten, die Beziehungen zwischen den Entitäten darstellen, umfasst, wobei die Einrichtung einen Eingang umfasst, der dazu ausgelegt ist, eine Schlüsselwortabfrage zu empfangen, die eine Menge von Schlüsselwörtern umfasst, und dazu ausgelegt ist, Schlüsselwörter auf Knoten des Wissensgraphen abzubilden,
  wobei die Einrichtung ferner einen Prozessor umfasst, wobei der Prozessor ausgelegt ist zum Inrangfolgebringen der Knoten des Wissensgraphen basierend auf einem kürzesten Pfad zu Schlüsselwortknoten, wobei ein Schlüsselwortknoten ein Knoten ist, der mit zumindest einem Schlüsselwort der Schlüsselwortabfrage übereinstimmt; Auswählen der kleinsten Menge von Schlüsselwortknoten unter allen Mengen von Schlüsselwortknoten, umfassend zumindest einen Schlüsselwortknoten für jedes Schlüsselwort der Menge von Schlüsselwörtern; Bestimmen, basierend auf der kleinsten Menge von Schlüsselwortknoten, einer optimalen Pfadmenge, wobei die optimale Pfadmenge Pfade im Wissensgraphen umfasst, die Knoten verbinden, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen, und wobei die optimale Pfadmenge optimal hinsichtlich minimaler Kosten der Pfadmenge ist, wobei die Kosten auf einer Linearkombination des Gesamtgewichts von Knoten der optimalen Pfadmenge und paarweisen semantischen Abständen zwischen den Knoten der optimalen Pfadmenge basieren, und Extrahieren einer Antwort auf die Schlüsselwortabfrage aus der optimalen Pfadmenge, und wobei die Einrichtung einen Ausgang umfasst, der dazu ausgelegt ist, die Antwort auf ein Ergebnis der Schlüsselwortabfrage abzubilden, und dazu ausgelegt ist, das Ergebnis auszugeben.
• Gemäß einer Ausführungsform ist die Einrichtung dazu ausgelegt, Schritte des Verfahrens entsprechend den beschriebenen Ausführungsformen auszuführen.
• Weitere Ausführungsformen beziehen sich auf ein Computerprogramm für Schlüsselwortsuche in einer Datenmenge, umfassend computerlesbare Anweisungen, die, wenn durch einen Computer ausgeführt, den Computer veranlassen, Schritte des beschriebenen Verfahrens auszuführen.
• Weitere Ausführungsformen sind aus der folgenden Beschreibung und der Zeichnung ableitbar. In der Zeichnung:
• 1 stellt einen beispielhaften Wissensgraphen dar;
• 2 stellt Aspekte einer Einrichtung für Schlüsselwortsuche dar, und
• 3 stellt Aspekte eines Verfahrens für Schlüsselwortsuche dar.
• 1 stellt einen beispielhaften Wissensgraphen, WG, 100 dar.
• Der WG 100 umfasst einen ersten Knoten 102, einen zweiten Knoten 104, einen dritten Knoten 106, einen vierten Knoten 108, einen fünften Knoten 110, einen sechsten Knoten 112, einen siebten Knoten 114, einen achten Knoten 116, einen neunten Knoten 118, einen zehnten Knoten 120, einen elften Knoten 122 und einen zwölften Knoten 124. Eine Kante 126 des WG 100 beginnt beim Knoten 104 und endet beim Knoten 102. Eine Kante 128 des WG 100 beginnt beim Knoten 106 und endet beim Knoten 104. Eine Kante 130 des WG 100 beginnt beim Knoten 106 und endet beim Knoten 108. Eine Kante 132 des WG 100 beginnt beim Knoten 108 und endet beim Knoten 110. Weitere Kanten des WG 100 sind Kante 134 zwischen dem Knoten 104 und dem Knoten 112, Kante 136 zwischen dem Knoten 108 und dem Knoten 114, Kante 138 zwischen dem Knoten 108 und dem Knoten 116, Kante 140 zwischen dem Knoten 118 und dem Knoten 112, Kante 142 zwischen dem Knoten 112 und dem Knoten 120, Kante 144 zwischen dem Knoten 114 und dem Knoten 122, die Kante 146 zwischen dem Knoten 114 und dem Knoten 124, Kante 148 zwischen dem Knoten 114 und dem Knoten 116 und Kante 150 zwischen dem Knoten 120 und dem Knoten 122.
• Der WG 100 kann mehr oder weniger Knoten und/oder mehr oder weniger Kanten umfassen. Im Beispiel stellt der WG 100 beispielhaftes Wissen dar. Zur Analyse von Daten aus anderen Gebieten, insbesondere technischen Gebieten, können entsprechende WGen verwendet werden.
• In dem Beispiel werden die Informationen auf die Knoten und die Kanten entsprechend der folgenden Abbildung von Knotenreferenznummern auf Schlüsselwort und der folgenden Abbildung von Kantenreferenzzeichen auf Schlüsselwort abgebildet.

102

Republican Party (Republikanische Partei)

104

George H. W. Bush

106

Anne Hutchinson

108

Franklin D. Roosevelt

110

John Aspinwall Roosevelt

112

Barbara Bush

114

James Roosevelt

116

Democratic Party (Demokratische Partei)

118

The After Party: The last Party 3

120

Mercedes

122

Germany (Deutschland)

124

World War II (Zweiter Weltkrieg)

126

party (Partei)

128

descendant (Nachfahre)

130

descendant (Nachfahre)

132

child (Kind)

134

grandchild (Enkelkind)

136

child (Kind)

138

party (Partei)

140

starring (Hauptrolle)

142

drives (fährt)

144

visited (besuchte)

146

battle (kämpfen)

148

party (Partei)

150

made in (hergestellt in)

• Der WG 100 wird in dem Beispiel als eine Datenmenge für Schlüsselwortsuche in der Datenmenge verwendet. Die Erfindung ist nicht auf Schlüsselwörter beschränkt, die für einen Menschen lesbar oder verstehbar sind. Allgemeiner bezieht sich der Begriff Schlüsselwort in diesem Kontext auf ein beliebiges Symbol oder Muster in den Daten, das mit einem entsprechenden WG analysiert werden kann.
• Ein erster Untergraph 152, der ein beispielhaftes Ergebnis der Schlüsselwortsuche darstellt, umfasst den zweiten Knoten 104, den dritten Knoten 106, den vierten Knoten 108, den sechsten Knoten 112, den siebten Knoten 114 und die Kanten zwischen diesen Knoten. Der erste Untergraph 152 in diesem Beispiel stellt eine Antwort auf eine Abfrage dar, die durch ein erstes Schlüsselwort „Barbara Bush“ und ein zweites Schlüsselwort „James Roosevelt“ dargestellt wird.
• Ein zweiter Untergraph 154, der ein weiteres beispielhaftes Ergebnis der Schlüsselwortsuche darstellt, umfasst den sechsten Knoten 112, den siebten Knoten 114, den zehnten Knoten 120 und den elften Knoten 122 und die Kanten zwischen diesen Knoten. Der zweite Untergraph 154 in diesem Beispiel stellt eine weitere Antwort auf die Abfrage dar, die durch die Schlüsselwörter „Barbara Bush“ und „James Roosevelt“ dargestellt wird.
• Aspekte einer Einrichtung 200 für Schlüsselwortsuche in der Datenmenge sind in 2 dargestellt.
• Die Einrichtung 200 umfasst einen Eingang 202, einen Prozessor 204 und einen Ausgang 206. Der Eingang 202 im Beispiel stellt eine Schnittstelle für Schlüsselwörter der Daten bereit, nach denen gesucht werden soll. Der Prozessor 204 ist ausgelegt zum Bestimmen des ersten Untergraphen 152 und/oder des zweiten Untergraphen 154. Der Ausgang 206 ist dazu ausgelegt, die Antwort auf ein Ergebnis der Schlüsselwortabfrage abzubilden und dazu ausgelegt, das Ergebnis der Schlüsselwortsuche auszugeben.
• Der WG 100 kann auf Speicher 208 in der Einrichtung 200 gespeichert sein. Der WG 100 kann auf Speicher gespeichert sein, der außerhalb der Einrichtung 200 ist. Datenverbindungen verbinden den Eingang 200 und den Prozessor 204, den Ausgang 206 und den Prozessor 204 und den Speicher 208 und den Prozessor 204. Computerlesbare Anweisungen können im Speicher 208 oder auf einem unterschiedlichen Speicher gespeichert sein. Der Prozessor 204 ist in dem Beispiel ausgelegt zum Ausführen der computerlesbaren Anweisungen zum Durchführen der Schlüsselwortsuche gemäß dem Verfahren, das nachfolgend Bezug nehmend auf 3 beschrieben wird.
• Das Verfahren für Schlüsselwortsuche wird für einen Wissensgraphen G = 〈V, E〉 beschrieben, wobei V eine Menge von n numerischen Darstellungen von Knoten v₁ ..., v_n ist und E ⊆ V × V eine Menge von m numerischen Darstellungen von gerichteten Kanten ist, die Beziehungen zwischen Entitäten darstellen, die durch die Knoten dargestellt werden. Entitäten und Beziehungen können mit Text, z. B. ihren Namen, bezeichnet werden. Die Kanten im Graphen können in unterschiedliche Richtungen ausgerichtet sein. Im beispielhaften WG 100 ist n = 12 und m = 13.
• Die Schlüsselwortsuche basiert auf einer Schlüsselwortabfrage Q = (k₁,...,k_g}, die die g Schlüsselwörter k₁, ..., k_g umfasst.
• In einem Schritt 302 wird eine Schlüsselwortabfrage Q, die eine Menge von Schlüsselwörtern k₁, ..., k_g umfasst, empfangen. Die Schlüsselwörter werden auf numerische Darstellungen von Knoten abgebildet. In dem Beispiel werden die g Schlüsselwörter k₁, ...,k_g auf g numerische Darstellungen von Knoten v₁...,v_g abgebildet. Ein Schlüsselwort kann auf mehrere Knoten abgebildet werden. In einem Aspekt wird zumindest eines der g Schlüsselwörter k₁,...,k_g auf zumindest eine numerische Darstellung von Knoten v₁,...,v_g abgebildet.
• Um ein Ergebnis für jedes der g Schlüsselwörter k₁,...,k_g zu erhalten, wird jedes der g Schlüsselwörter k₁,...,k_g auf zumindest eine numerische Darstellung von Knoten v₁...,v_g abgebildet. Wenn ein Schlüsselwort nicht auf irgendeinen Knoten im Wissensgraphen abgebildet werden kann, kann das Ergebnis leer sein.
• Eine Schlüsselwortabgleichsfunktion kann verwendet werden, um ein Schlüsselwort auf einen beliebigen Knoten des Wissensgraphen abzubilden. Beispielsweise kann die Abgleichsfunktion auf wörtlichen Bezeichnungen basieren, die ein Schlüsselwort umfassen. Allerdings ist die Erfindung nicht auf irgendeine spezifische Abbildungsfunktion beschränkt.
• Gemäß dem Beispiel umfasst die Abfrage g = 2 Schlüsselwörter, und das erste Schlüsselwort k₁ =„Barbara Bush“ wird auf die numerische Darstellung des Knotens 112 abgebildet, und das zweite Schlüsselwort k₂ =„James Roosevelt“ wird auf die numerische Darstellung von Knoten 114 abgebildet.
• In einem Aspekt können die Funktionstreffer: $$\mathbb{K}\to 2^V$$

  

  verwendet werden, um eine Menge IK von Schlüsselwörtern auf eine Untermenge der numerischen Darstellungen der Knoten des Wissensgraphen G abzubilden. Die konkrete Umsetzung von Treffern, d. h. die Art und Weise des Abgleichens von Schlüsselwörtern mit Bezeichnungen von Entitäten steht nicht im Fokus dieser Offenbarung. In diesem Aspekt werden Treffer(k_i) als K_i für 1 ≤ i ≤ g bezeichnet. Wobei K_i die numerischen Darstellungen einer Menge von Knoten sind, auf die das Schlüsselwort abgebildet wird, auch Schlüsselwortknoten genannt. Das Verfahren ist nicht auf diese Art und Weise der Abbildung beschränkt.
• In der Offenbarung wird Kantenabbildung ausgelassen, Kantenabbildung kann aber durch Unterteilen der Kanten in Knotenabbildung transformiert werden. Insbesondere ergibt die Unterteilung einer Kante (u, v) einen neuen Knoten w mit den Bezeichnungen der Kante (u, v) und ersetzt dann (u, v) durch zwei neue Kanten (u, w) und (w, v).
• Für ein gegebenes G = (V, E) ist eine Antwort auf Q definiert als ein Untergraph von G, bezeichnet durch T = 〈V_T, E_T〉, wobei der Untergraph T die folgenden Anforderungen erfüllt. (1) T ist zusammenhängend. (2) T enthält zumindest einen Schlüsselwortknoten aus jedem K_i für 1 ≤ i ≤ g, d. h. T_T n K_i ≠ Ø. (3) T ist strukturell minimal für (1) und (2), d. h. keiner seiner echten Untergraphen erfüllt sowohl (1) als auch (2). Strukturelle Minimalität zeigt an, dass T eine Baumstruktur aufweist, wobei Blattknoten Schlüsselwortknoten sind.
• Der Prozess des Berechnens der Antwort wird im Folgenden beschrieben.
• In einem Schritt 304 werden Knoten des Wissensgraphen basierend auf einem kürzesten Pfad zu Schlüsselwortknoten in eine Rangfolge gebracht, wobei ein Schlüsselwortknoten ein Knoten ist, der mit zumindest einem Schlüsselwort der Schlüsselwortabfrage übereinstimmt;
• In einem Schritt 306 wird eine kleinste Menge von Schlüsselwortknoten K_imin. unter allen Mengen von Schlüsselwortknoten, umfassend zumindest einen Schlüsselwortknoten für jedes Schlüsselwort der Menge von Schlüsselwörtern, ausgewählt.
• In einem Schritt 308 wird eine optimale Pfadmenge im Wissensgraphen G basierend auf der kleinsten Menge von Schlüsselwortknoten K_imin und basierend auf einer Anzahl von in eine Rangfolge gebrachten Knoten bestimmt.
• Die Anzahl von in Rangfolge gebrachten Knoten kann angegeben sein. Die Anzahl kann beispielsweise in Abhängigkeit von der Größe des Wissensgraphen variieren. Beispielsweise kann, für einen Wissensgraphen mit etwa 30.000 und 3.000.000 Knoten, diese Anzahl von 5 bis 20 reichen. Die Anzahl kann anhand von Experimenten angegeben werden. Es ist anzumerken, dass eine beliebige andere Anzahl ausgewählt werden kann.
• Die optimale Pfadmenge umfasst Pfade im Wissensgraphen, die Knoten verbinden, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen, und wobei die optimale Pfadmenge optimal hinsichtlich minimaler Kosten der Pfadmenge ist, wobei die Kosten auf einer Linearkombination des Gesamtgewichts von Knoten der optimalen Pfadmenge und paarweisen semantischen Abständen zwischen den Knoten der optimalen Pfadmenge basieren.
• Die optimale Pfadmenge ist optimal hinsichtlich minimaler Kosten der Pfadmenge, wobei die Kosten auf einer Linearkombination des Gesamtgewichts von Knoten der optimalen Pfadmenge und paarweisen semantischen Abständen zwischen den Knoten der optimalen Pfadmenge basieren.
• Für G = 〈V, E〉 bildet eine Gewichtungsfunktion Knoten auf nicht-negative reelle Zahlen ab, bezeichnet durch wt: V ↦ ℝ_≥0.
• Eine semantische Abstandsfunktion sd bildet Paare von Knoten auf nicht-negative reelle Zahlen ab, bezeichnet durch sd: V × V ↦ ℝ_≥0. Diese pseudometrische Funktion erfüllt, für alle u, v, w ∈ V: $$sd\left(v,v\right)=\mathrm{0,}$$

  

  d. h. Ununterscheidbarkeit von identischen Werten, $$sd\left(u,v\right)=sd\left(v,u\right),$$

  

  d. h. Symmetrie und $$sd\left(u,v\right)\le sd\left(u,w\right)+sd\left(w,v\right),$$

  

  d. h. Dreiecksungleichung.
• Die Messung des semantischen Abstands kann unabhängig von der Graphenstruktur und den Knotengewichten sein. Insbesondere unterscheidet er sich vom Graphenabstand, namentlich der Anzahl von Kanten eines kürzesten Pfades. Beispielsweise können angrenzende Knoten semantisch entfernt voneinander sein.
• Die Kosten einer Antwort T = 〈V_T, E_T〉 sind das Gesamtgewicht ihrer Knoten und ihrer paarweisen semantischen Abstände: $$cost\left(T\right)=\alpha {\displaystyle \sum _{v\in V_T}wt\left(v\right)}+\left(1-\alpha \right){\displaystyle \sum _{\begin{array}{l}{v}_i,v_j\in V_T\\ i<j\end{array}}sd\left(v_i,v_j\right)},$$

  

  wobei α ∈ [0,1] ein Parameter ist. In der Kostengleichung stellt das erste Element die Salienz der Knoten von T dar, und das zweite Element charakterisiert ihre semantische Zusammengehörigkeit. Das Verfahren erfordert keine spezifische Implementierung des Gewichts wt und des semantischen Abstands sd. Das Gewicht wt und die Art und Weise, wie der semantische Abstand sd bestimmt wird, kann so ausgewählt werden, dass die Relevanz der Abfrage, die Zentralität in der Graphenstruktur, die Semantik in den Bezeichnungen usw. berücksichtigt werden. Edmund Ihler, 1991, The Complexity of Approximating the Class Steiner Tree Problem, in WG 1991, 85-96; https://doi.org/10.1007/3-540-55121-2_8 bietet ein Beispiel für das Gewicht wt; Gaurav Bhalotia, Arvind Hulgeri, Charuta Nakhe, Soumen Chakrabarti und S. Sudarshan, 2002, Keyword Searching and Browsing in Databases using BANKS, in ICDE 2002, 431-440; https://doi.org/10.1109/ICDE.2002.994756 bietet ein Beispiel für den semantischen Abstand sd. Kleine Gewichte repräsentieren Salienz, und kleiner semantischer Abstand repräsentiert Zusammengehörigkeit. Die Berechnung des Gewichts wt und des semantischen Abstands sd können unabhängig voneinander sein. Im Wissensgraphen werden Gewichte zu ihren Knoten zugeordnet. Gewichte von Knoten werden beispielsweise vorab berechnet, z. B. unter Verwendung von normalisiertem pageRank.
• Im Wissensgraphen sind Kanten beispielsweise vorab berechnete Beziehungen zwischen Knoten.
• Im Wissensgraphen werden semantische Abstände beispielsweise für Paare seiner Knoten vorab berechnet.
• Ein Ziel des Verfahrens 300 ist, eine optimale Antwort zu bestimmen, wobei eine optimale Antwort eine Antwort ist, die die Kosten minimiert. Das Verfahren 300 erweitert das bekannte GST-Mindestgewichtsproblem, beispielsweise beschrieben in Edmund Ihler, 1991, The Complexity of Approximating the Class Steiner Tree Problem, durch Einführen von quadratischen Termen sd(v_i, v_j) in die Zielfunktion, die zusätzliche Kosten darstellen, die zu bezahlen sind, wenn zwei Knoten v_i und v_j beide in T enthalten sind.
• Gemäß einem Aspekt der Offenbarung können die Schritte 304 bis 308 durch den folgenden Algorithmus 1 implementiert werden, umfassend die Zeilen 1 bis 14: $$\text{Eingabe}:G=\langle V,E\rangle \text{ und }Q=\left\{k_1,\dots ,k_g\right\}$$

  

  
• Der Schritt 308 und der Algorithmus OptimizedRPS(G, Q, r) aus Zeile 10 werden im Folgenden ausführlich und Bezug nehmend auf Algorithmus 2 beschrieben:
• Der Schritt 308 des Bestimmens einer optimalen Pfadmenge umfasst einen iterativen Prozess 308a basierend auf dem Bestimmen einer lokal optimalen Pfadmenge, wobei die lokal optimale Pfadmenge Pfade im Wissensgraphen umfasst, die einen Wurzelknoten der kleinsten Menge von Schlüsselwortknoten mit Knoten verbinden, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen, und wobei die lokal optimale Pfadmenge optimal hinsichtlich minimaler Kosten der Pfadmenge für den entsprechenden Wurzelknoten ist, wobei der iterative Prozess 308a die folgenden Schritte umfasst:
  • Bestimmen einer Gesamtmindestpfadlänge der lokal optimalen Pfadmenge durch Bestimmen, für jeden Schlüsselwortknoten, des kürzesten Pfades aus dem entsprechenden Wurzelknoten;
  • Bestimmen einer unteren Grenze der Kosten der lokal optimalen Pfadmenge; Bestimmen der Kosten jedes Pfades, der größer als die
  • Gesamtmindestpfadlänge ist;
  • Vergleichen der Kosten jedes Pfades, der größer als die
  • Gesamtmindestpfadlänge ist, mit der unteren Grenze;
  • Erhalten der Pfadmenge mit minimalen Kosten als die lokal optimale Pfadmenge.
• Der Schritt 308 des Bestimmens einer optimalen Pfadmenge umfasst ferner Folgendes:
• Erhalten der lokal optimalen Pfadmenge mit den minimalen Kosten als die optimale Pfadmenge.
• In G = (V, E) ist eine RPS eine Menge von Pfaden, die relevant für eine Abfrage Q = {k₁, ... ,k_g} sind. Speziell ist, bei gegebenem r ∈ V, das Wurzelknoten genannt wird, eine lokal optimale Pfadmenge r-RPS, bezeichnet durch P_r = {P₁,...,P_g}, eine Menge von g Pfaden, sodass für 1 ≤ i ≤ g jedes P_i = (V_Pi , E_Pi ) ein r - K_i-Pfad ist, oder, noch spezieller, ein r - v_i-Pfad, der r mit einem Schlüsselwortknoten v_i ∈ K_i verbindet. Es ist anzumerken, dass es für i ≠ j möglich ist, dass K_i ∩ K_j ≠ 0 und P_i = P_j.
• Kosten einer r-RPS, bezeichnet durch P_r = {P₁,..., P_g} mit P_i = 〈V_Pi , E_Pi 〉 für 1 ≤ i ≤ g, ist durch die folgende Kostenfunktion gegeben: $$pcost\left(P_r\right)=\alpha \left(wt\left(r\right)+{\displaystyle \sum _{P_i\in P_r}{\displaystyle \sum _{v\in V_{P_i\left\{r\right\}}}wt\left(v\right)}}\right)+\left(1-\alpha \right)\frac{vnum\left(P_r\right)}{2}{\displaystyle \sum _{P_i\in P_r}{\displaystyle \sum _{v\in V_{P_i\left\{r\right\}}}sd\left(r,v\right)}}.$$

  
• Die Funktion vnum zählt die Knoten in einer RPS. Sie zählt den Wurzelknoten r absichtlich nur einmal: $$vnum\left(P_r\right)=1+{\displaystyle \sum _{P_i\in P_r}\left|V_{P_i}\backslash \left\{r\right\}\right|}.$$

  
• Für jeden Wurzelknoten r ∈ V wird eine lokal optimale Pfadmenge r-RPS, d. h. eine r-RPS, die pcost minimiert, wie folgt bestimmt: $$P_r^{min}=arg\underset{P_r}{\text{min}}pcost\left(P_r\right)$$

  
• Gemäß einem Aspekt der Offenbarung wird die folgende Variante von pcost definiert: $$pcost\text{'}\left(Pr\right)=pcost\left(Pr\right)-\alpha wt\left(r\right)$$

  
• Da αwt(r) in pcost jeder r-RPS auftaucht, ist Minimieren der pcost'-Funktion äquivalent zum Minimieren von pcost: $$P_r^{min}=arg\underset{P_r}{\text{min}}pcost\left(P_r\right)=arg\underset{P_r}{\text{min}}pcost\text{'}\left(P_r\right).$$

  
• Das Minimieren der pcost'-Funktion berechnet die Summe der Kosten einer Menge von Pfaden.
• pcost' enthält allerdings vnum(Pr), was von P_r abhängt und beim Berechnen eines Pfades mit minimalen Kosten unbekannt ist.
• Daher wird jeder mögliche Wert von vnum(Pr) berücksichtigt und wird daher in jedem Fall eine Konstante.
• P_r unterliegt beispielsweise vnum(P_r) = n. Für einen Pfad P = 〈V_P, E_p〉, der mit dem Wurzelknoten r beginnt, ist definiert: $$p{l}_n\left(P\right)={\displaystyle \sum _{v\in V_P\backslash \left\{r\right\}}\alpha wt\left(v\right)}+n\frac{1-\alpha }{2}sd\left(r,v\right).$$

  
• Für v ∈ V wird das Minimum pln von r-v-Pfaden, die exakt m Kanten umfassen, iterativ wie folgt berechnet: $$p{d}_n\left[v\right]\left[m\right]=\{\begin{array}{cc}0& m=\mathrm{0,}v=r,\\ \infty & m=\mathrm{0,}v\ne r\\ \underset{u\in N\left(v\right)}{\text{min}}p{d}_n\left[u\right]\left[m-1\right]+\alpha wt\left(v\right)+n\frac{1-\alpha }{2}sd\left(r,v\right)& m>0\end{array}$$

  

  wobei N(v) die Menge der Nachbarn von v in G ist. Das Minimum pln von r-K_i-Pfaden, die exakt m Kanten umfassen, wird bezeichnet durch $$pd{k}_n\left[i\right]\left[m\right]=\underset{v\in K_i}{\text{min}}p{d}_n\left[v\right]\left[m\right]$$

  
• Für 1 ≤ 1 ≤ g seien Q_I ⊆ Q die ersten I Schlüsselwörter in Q: $$Q_I=\left\{k_1,\dots ,k_I\right\}.$$

  
• Die minimalen pcost' von r-RPSen, die insgesamt exakt m Kanten enthalten und relevant für Q, sind (d. h. I Pfade umfassen - einen r-K_i -Pfad für jedes 1 ≤ i ≤ I) werden iterativ berechnet durch: $$p{c}_n\left[I\right]\left[m\right]=\{\begin{array}{cc}pd{k}_n\left[I\right]\left[m\right]& I=1\\ \underset{0\le x\le min\left\{m,\left|V\right|-1\right\}}{\text{min}}p{c}_n\left[I-1\right]\left[m-x\right]+pd{k}_n\left[I\right]\left[x\right]& I>1.\end{array}$$

  
• Da P_r mit vnum(P_r) = n insgesamt n - 1 Kanten enthält, wird pc_n [g] [n - 1] berücksichtigt. Schließlich wird über alle möglichen Werte von vnum(P_r), erhalten. $$\underset{P_r}{\text{min}}pcost\text{'}\left(P_r\right)=\underset{1\le n\le 1+g\left(\left|V\right|-1\right)}{\text{min}}p{c}_n\left[g\right]\left[n-1\right]$$

  
• Für jedes n wird pc_n [g] [n - 1] berechnet, und P_r - die r-RPS mit tatsächlich minimalem pcost' mit vnum = n - wird rekonstruiert. Die Rekonstruktion kann durch Nachschlagen von zusätzlichen Feldern implementiert werden, in denen berechnete Pfade mit minimalen Kosten und RPSen in einer Standardweise aufgezeichnet werden.
• Abschließend wird $P_r^{min}$

  

  aktualisiert, und die r-RPS mit lokal minimalem pcost wird als optimale Pfadmenge P^# zurückgegeben, wobei P^# die RPS mit global minimalem pcost bezeichnet.
• Dies erfolgt durch Schritt 308 des Erhaltens der lokal optimalen Pfadmenge r-RPS mit den minimalen Kosten als die optimale Pfadmenge P^#.
• Gemäß einem Aspekt der Offenbarung kann der Schritt 308, insbesondere der iterative Prozess 308a von Schritt 308, durch den folgenden Algorithmus 2 implementiert werden, umfassend die Zeilen 1 bis 27: $$\text{Eingabe}:G=\langle V,E\rangle ,Q=\left\{k_1,\dots ,k_g\right\},$$

  

  und r ∈ V Ausgabe: eine r-RPS $P_r^{min}$

  

  mit lokal minimalem pcost

  
• Zeilen 3 bis 5 des Algorithmus 2 beziehen sich auf den Schritt des Bestimmens einer Gesamtmindestlänge eines Pfades der lokal optimalen Pfadmenge durch Bestimmen, für jeden Schlüsselwortknoten, des kürzesten Pfades vom entsprechenden Wurzelknoten.
• Zeile 6 bezieht sich auf den Schritt des Bestimmens einer unteren Grenze der Kosten der lokal optimalen Pfadmenge. Dies ist eine Maßnahme, um große Werte von n zu kürzen, siehe Zeilen 1 bis 5. Im oben angezeigten beispielhaften Algorithmus für Schritt 306 endet die äußerste Schleife in Zeile 7 mit n = (|V| - 1), was ein großer Wert sein kann. Eine untere Grenze für pcost(P_r) mit vnum(P_r) = n zum Kürzen großer Werte von n wird berechnet. pcost(P_r) ist gegeben durch $$\begin{array}{c}pcost\left(Pr\right)=\alpha wt\left(r\right)+pcost\text{'}\left(Pr\right)\\ pcost\text{'}\left(Pr\right)={\displaystyle \sum _{P_i\in P_r}{\displaystyle \sum _{v\in V_{P_i}\backslash \left\{r\right\}}\alpha wt\left(v\right)}+n\frac{1-\alpha }{2}sd\left(r,v\right).}\end{array}$$

  
• Die Funktion pcost' berechnet die Summe der Kosten von g Pfaden - ein r-K_i-Pfad für jedes 1 ≤ i ≤ g.
• Durch Abbilden der Kosten eines r-K_i-Pfades in die Länge, d. h. das Gesamtkantengewicht, eines r-K_i-Pfades in einem kantengewichteten Graphen kann seine untere Grenze erhalten werden durch Berechnen der Länge eines kürzesten Pfades, d. h. eines r-K_i-Pfades mit minimalem Gewicht in diesem kantengewichteten Graphen. Dies kann implementiert werden, indem der Algorithmus wie folgt erweitert wird. Zum Beginn der äußersten Schleife wird ein kantengewichteter, gerichteter Graph G_r,n = 〈V_r,n,〉 E_r,n〉, wobei V_r,n = V und jede Kante (u, v) ∈ E zwei gerichteten Kanten (u, v), (v, u) ∈ E_r,n entspricht, erzeugt. Jede gerichtete Kante (u, v) ∈ E_r,n wird gewichtet durch $$\alpha wt\left(v\right)+n\frac{1-\alpha }{2}sd\left(r,v\right).$$

  
• Der Dijkstra-Algorithmus kann auf G_r,n verwendet werden, um einen r-K_i-Pfad mit minimalem Gewicht für jedes 1 ≤ i ≤ g zu berechnen, beeichnet durch P_r,n,i. Er hat das kleinste Gesamtkantengewicht unter r-K_i-Pfaden in G_r,n, bezeichnet durch d_r,n,i. Daher ist eine untere Grenze für pcost(P_r) mit vnum(P_r) = n gegeben durch $$D_{r,n}=\alpha wt\left(r\right)+{\displaystyle \sum _{1\le i\le g}{d}_{r,n,i}}.$$

  
• D_r,n erhöht sich, wenn sich n erhöht, daher kann die folgende Ungleichung geprüft werden: $$D_{r,n}\ge pcost\left(P_r^{min}\right).$$

  
• Wenn sie für die aktuellen n und $P_r^{min}$

  

  gilt, wird die äußerste Schleife unterbrochen, und das aktuelle $P_r^{min}$

  

  wird zurückgegeben, da es für die aktuellen und größeren Werte von n, d. h. vnum(Pr), kein P_r mit einem kleineren pcost gibt. In ähnlicher Weise kann die folgende Ungleichung geprüft werden: $$D_{r,n}\ge pcost\left(P^{\#}\right).$$

  
• Wenn sie für die aktuellen n und P^# gilt, was die aktuelle RPS mit global minimalem pcost in Algorithmus QO ist, wird die äußerste Schleife unterbrochen, und das aktuelle $P_r^{min}$

  

  wird zurückgegeben, siehe Zeilen 26 und 27.
• Zeilen 7 bis 22 beziehen sich auf den Schritt des Bestimmens der Kosten jedes Pfades, der größer als die Gesamtmindestpfadlänge ist. Die Schleife in Zeile 7 beginnt mit n = L_r. Dies ist eine Maßnahme, um kleine Werte von n zu kürzen, siehe Zeilen 1 bis 5. Eine untere Grenze für vnum(P_r) (d. h. n) zum Kürzen kleiner Werte von n wird berechnet. Zum Beginn des Algorithmus kann eine Breitensuche von G, beginnend mit r, zum Berechnen der kleinsten Anzahl von Kanten in r-K_i-Pfaden für jedes 1 ≤ i ≤ g, bezeichnet durch l_r,i, eingefügt werden. Eine untere Grenze für vnum(P_r) ist gegeben durch $$L_r=1+{\displaystyle \sum _{1\le i\le g}{l}_{r,i}}.$$

  
• Zeile 23 bezieht sich auf den Schritt des Vergleichens der Kosten jedes Pfades, der größer als die Gesamtmindestpfadlänge ist, mit der unteren Grenze.
• Zeile 24 bezieht sich auf den Schritt des Erhaltens der Pfadmenge mit den minimalen Kosten als die lokal optimale Pfadmenge.
• Der Schritt 308 des Bestimmens einer optimalen Pfadmenge umfasst ferner Folgendes:
• Erhalten der lokal optimalen Pfadmenge mit den minimalen Kosten als die optimale Pfadmenge. Dies wird durch die Zeilen 11 und 12 von Algorithmus 1 implementiert.
• Gemäß einer weiteren Kürzungsstrategie kann der r-K_i-Pfad mit minimalem Gewicht für jedes 1 ≤ i ≤ g, bezeichnet durch P_r,n,i, ausgenutzt werden. Die Anzahl von Kanten in P_r,n,i ist gegeben durch die Anzahl i_r,n,i.
• Es wird davon ausgegangen, dass eine r-RPS P_r mit vnum(P_r) = n für das aktuelle n eine r-RPS mit lokal minimalen Kosten ist. Wenn für irgendein 1 ≤ i ≤, der r-K_i-Pfad P_i ∈ P_r mehr als l_r,n,i Kanten enthält, wird P_i ersetzt durch P_r,n,i, um eine andere r-RPS P_r' zu erzeugen. Ihr definiertes Gesamtkantengewicht ist nicht größer als das von P_r, und ihr vnum ist kleiner. Daher ist pcost(P_r') ≤ pcost(P_r), d. h. P_r' ist auch eine r-RPS mit lokal minimalem pcost, die und/oder irgendeine andere r-RPS mit lokal minimalem pcost in vorherigen Iterationen der äußersten Schleife für kleinere Werte von n gefunden wurde. Es ist daher nicht notwendig, P_r für das aktuelle n zu berücksichtigen. Dies kann implementiert werden, indem der Algorithmus wie folgt erweitert wird: Einengen der Bereiche von m und x: $$m\text{ to }min\{n-\mathrm{1,}\left|V\right|-\mathrm{1,}{l}_{r,n,i},$$

  

  $$m\text{ to }min\{n-\mathrm{1,}{\displaystyle {\sum }_{1\le i\le I}{l}_{r,n,i}},$$

  

  $$\text{max}\left\{\mathrm{0,}m-{\displaystyle {\sum }_{1\le i\le I-1}{l}_{r,n,i}}\right\}\le x\le \text{min}\left\{m,\left|V\right|-\mathrm{1,}{l}_{r,n,I}\right\},$$

  

  $$\text{m to }min\{n-\mathrm{1,}\left|V\right|-\mathrm{1,}{l}_{r,n,i},$$

  

  $$\text{m to }min\left\{n-\mathrm{1,}\left|V\right|-\mathrm{1,}\underset{1\le i\le g}{\text{max}}{l}_{r,n,i}\right\}.$$

  
• Das Verfahren umfasst ferner einen Schritt 310 des Extrahierens einer Antwort auf die Schlüsselwortabfrage aus der optimalen Pfadmenge P^#.
• Die Antwort ist definiert als $$T^{\#}=\langle V_{T^{\#}},E_{T^{\#}}\rangle$$

  
• Der Schritt 310 wird ausführlicher bezüglich eines Schrittes 312 des Zusammenführens der Pfade der optimalen Pfadmenge in einem Untergraphen des Wissensgraphen und einen Schritt 314 des Entfernens unnötiger Knoten und Kanten aus dem Untergraphen beschrieben.
• Die optimale Pfadmenge P^# wird wie folgt in eine Antwort T^# umgewandelt. Alle r-vi-Pfade in P_r werden in einen Untergraphen T^# aus G zusammengeführt, der über einen Wurzelknoten r zusammenhängt und v_i e K_i für 1 ≤ i ≤ g enthält.
• Gemäß den oben beschriebenen Anforderungen für eine Antwort T, muss T die Anforderung erfüllen, strukturell minimal zu sein. Daher ist die Antwort T^# eine optimale Antwort, wenn sie strukturell minimal ist. Wenn nicht, wird der Schritt 314 des Entfernens von unnötigen Knoten und Kanten aus dem Untergraphen wiederholt verarbeitet, bis dieser strukturell minimal wird.
• Gemäß dem in 1 dargestellten beispielhaften Wissensgraphen 100 wird eine Antwort auf die Suchabfrage beispielsweise durch den Untergraphen 152 gegeben. Der Untergraph 152 ist semantisch zusammenhängend, verglichen mit dem anderen Untergraphen 154, der semantisch nicht zusammenhängend ist. Daher ist der Untergraph 152 die bevorzugte Antwort gemäß dieser Ausführungsform.
• In einem Schritt 316 kann die Antwort auf ein Ergebnis der Schlüsselwortabfrage abgebildet werden, und das Ergebnis der Schlüsselwortsuche kann ausgegeben werden.

Claims (11)

1. Computerimplementiertes Verfahren (300) für Schlüsselwortsuche in einer Datenmenge, wobei Daten der Datenmenge durch einen Wissensgraphen (100) dargestellt werden, wobei der Wissensgraph (100) Knoten, die Entitäten der Datenmenge darstellen, und Kanten, die Beziehungen zwischen den Entitäten darstellen, umfasst, wobei das Verfahren (300) die folgenden Schritte umfasst: Empfangen (302) einer Schlüsselwortabfrage, umfassend eine Menge von Schlüsselwörtern; Inrangfolgebringen (304) von Knoten des Wissensgraphen basierend auf einem kürzesten Pfad zu Schlüsselwortknoten, wobei ein Schlüsselwortknoten ein Knoten ist, der mit zumindest einem Schlüsselwort der Schlüsselwortabfrage übereinstimmt; Auswählen (306) der kleinsten Menge von Schlüsselwortknoten unter allen Mengen von Schlüsselwortknoten, umfassend zumindest einen Schlüsselwortknoten für jedes Schlüsselwort der Menge von Schlüsselwörtern; Bestimmen (308), basierend auf der kleinsten Menge von Schlüsselwortknoten und basierend auf einer Anzahl von in Rangfolge gebrachten Knoten, einer optimalen Pfadmenge, wobei die optimale Pfadmenge Pfade im Wissensgraphen (100) umfasst, die Knoten verbinden, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen, und wobei die optimale Pfadmenge optimal bezüglich minimaler Kosten der Pfadmenge ist, wobei die Kosten auf einer Linearkombination des Gesamtgewichts von Knoten der optimalen Pfadmenge und paarweisen semantischen Abständen zwischen den Knoten der optimalen Pfadmenge basieren, und Extrahieren (310) einer Antwort auf die Schlüsselwortabfrage aus der optimalen Pfadmenge.
2. Verfahren (300) nach Anspruch 1, wobei das Gesamtgewicht eines Knotens Salienz darstellt, und/oder der paarweise semantische Abstand zwischen zwei Knoten eine semantische Zusammengehörigkeit darstellt.
3. Verfahren (300) nach Anspruch 1 oder 2, wobei die Kosten einer Pfadmenge gegeben sind durch die Summe des Gesamtgewichts des Wurzelknotens und der Gesamtgewichte der Knoten, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen, und der paarweisen semantischen Abstände zwischen dem Wurzelknoten und den Knoten, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen.
4. Verfahren (300) nach einem der vorhergehenden Ansprüche, wobei der Schritt (308) des Bestimmens einer optimalen Pfadmenge einen iterativen Prozess (308a) basierend auf dem Bestimmen einer lokal optimalen Pfadmenge umfasst, wobei die lokal optimale Pfadmenge Pfade im Wissensgraphen (100) umfasst, die einen Wurzelknoten der kleinsten Menge von Schlüsselwortknoten mit Knoten verbinden, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen, und wobei die lokal optimale Pfadmenge optimal hinsichtlich minimaler Kosten der Pfadmenge für den entsprechenden Wurzelknoten ist, wobei der iterative Prozess (308a) die folgenden Schritte umfasst: Bestimmen einer Gesamtmindestpfadlänge der lokal optimalen Pfadmenge durch Bestimmen, für jeden Schlüsselwortknoten, des kürzesten Pfades vom entsprechenden Wurzelknoten; Bestimmen einer unteren Grenze der Kosten der lokal optimalen Pfadmenge; Bestimmen der Kosten jedes Pfades, der größer als die Gesamtmindestpfadlänge ist; Vergleichen der Kosten jedes Pfades, der größer als die Gesamtmindestpfadlänge ist, mit der unteren Grenze; Erhalten der Pfadmenge mit minimalen Kosten als die lokal optimale Pfadmenge.
5. Verfahren (300) nach Anspruch 4, wobei der Schritt (308) des Bestimmens einer optimalen Pfadmenge Folgendes umfasst: Erhalten der lokal optimalen Pfadmenge mit den minimalen Kosten als die optimale Pfadmenge.
6. Verfahren (300) nach einem der vorhergehenden Ansprüche, wobei der iterative Prozess (308a) des Schrittes (308) des Bestimmens einer optimalen Pfadmenge um zumindest eine Kürzungsstrategie erweitert wird.
7. Verfahren nach einem der vorhergehenden Ansprüche, wobei der Schritt des Extrahierens (310) der Antwort aus der optimalen Pfadmenge Folgendes umfasst: Zusammenführen (312) der Pfade der optimalen Pfadmenge in einen Untergraphen des Wissensgraphen (100).
8. Verfahren nach einem der vorhergehenden Ansprüche, wobei der Schritt (310) des Extrahierens der Antwort aus der optimalen Pfadmenge ferner Folgendes umfasst: Entfernen (314) unnötiger Knoten und Kanten aus dem Untergraphen.
9. Einrichtung (200) zur Schlüsselwortsuche in einer Datenmenge, wobei Daten der Datenmenge durch einen Wissensgraphen (100) dargestellt werden, wobei der Wissensgraph (100) Knoten (V), die Entitäten der Datenmenge darstellen, und Kanten (E), die Beziehungen zwischen den Entitäten darstellen, umfasst, wobei die Einrichtung einen Eingang umfasst, der dazu ausgelegt ist, eine Schlüsselwortabfrage (Q) zu empfangen, die eine Menge von Schlüsselwörtern umfasst, und dazu ausgelegt ist, Schlüsselwörter auf Knoten des Wissensgraphen (100) abzubilden, wobei die Einrichtung ferner einen Prozessor (204) umfasst, wobei der Prozessor (204) ausgelegt ist zum Inrangfolgebringen (304) der Knoten des Wissensgraphen basierend auf einem kürzesten Pfad zu Schlüsselwortknoten, wobei ein Schlüsselwortknoten ein Knoten ist, der mit zumindest einem Schlüsselwort der Schlüsselwortabfrage übereinstimmt; Auswählen (306) der kleinsten Menge von Schlüsselwortknoten unter allen Mengen von Schlüsselwortknoten, umfassend zumindest einen Schlüsselwortknoten für jedes Schlüsselwort der Menge von Schlüsselwörtern; Bestimmen (308), basierend auf der kleinsten Menge von Schlüsselwortknoten und basierend auf einer Anzahl von in Rangfolge gebrachten Knoten, einer optimalen Pfadmenge, wobei die optimale Pfadmenge Pfade im Wissensgraphen (100) umfasst, die Knoten verbinden, die mit den Schlüsselwörtern der Schlüsselwortabfrage übereinstimmen, und wobei die optimale Pfadmenge optimal hinsichtlich minimaler Kosten der Pfadmenge ist, wobei die Kosten auf einer Linearkombination des Gesamtgewichts von Knoten der optimalen Pfadmenge und paarweisen semantischen Abständen zwischen den Knoten der optimalen Pfadmenge basieren, und Extrahieren (310) einer Antwort auf die Schlüsselwortabfrage aus der optimalen Pfadmenge, und wobei die Einrichtung einen Ausgang (206) umfasst, der dazu ausgelegt ist, die Antwort auf ein Ergebnis der Schlüsselwortabfrage abzubilden, und dazu ausgelegt ist, das Ergebnis auszugeben.
10. Einrichtung (200) nach Anspruch 9, wobei die Einrichtung (200) ferner ausgelegt ist zum Ausführen von Schritten des Verfahrens (300) nach einem der Ansprüche 2 bis 8.
11. Computerprogramm zur Schlüsselwortsuche in einer Datenmenge, umfassend computerlesbare Anweisungen, die, wenn durch einen Computer ausgeführt, den Computer veranlassen, Schritte des Verfahrens (300) nach einem der Ansprüche 1 bis 8 auszuführen.

Images