DE102021203300A1 - Computer-implemented method for keyword searches in a knowledge graph - Google Patents

Abstract

Computer-implemented method (300), device (200) and a computer program for keyword searches in a dataset, data of the dataset being represented by a knowledge graph (100), the knowledge graph (100) having nodes representing entities of the dataset and edges representing Representing relationships between the entities, the method (300) comprising the steps of:receiving (302) a keyword query comprising a set of keywords;ranking (304) nodes of the knowledge graph based on a shortest path to keyword nodes, wherein a keyword node is a node that matches at least one keyword of the keyword query;selecting (306) the smallest set of keyword nodes among all sets of keyword nodes comprising at least one keyword node for each keyword of the set of keywords.determining (308) based on the smallest quantity of sc keyword nodes and based on a number of ranked nodes, an optimal path set, the optimal path set including paths in the knowledge graph (100) connecting nodes that match the keywords of the keyword query, and the optimal path set optimal in terms of minimum cost of the path set where the cost is based on a linear combination of the total weight of nodes of the optimal path set and pairwise semantic distances between the nodes of the optimal path set, and extracting (310) an answer to the keyword query from the optimal path set.

Description

background

The invention relates to a device and a method for keyword searches in a data set, data of the data set being represented by a knowledge graph. A result of the search can be automatically determined by finding a subgraph that optimizes a cost function.

epiphany

• 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.

One embodiment relates to a computer-implemented method for keyword searches in a dataset, data of the dataset being represented by a knowledge graph, the knowledge graph comprising nodes representing entities of the dataset and edges representing relationships between the entities, the method includes the following steps:

• receiving a keyword query comprising a set of keywords;
• ranking nodes of the knowledge graph based on a shortest path to keyword nodes, a keyword node being a node that matches at least one keyword of the keyword query;
• selecting the smallest set of keyword nodes among all sets of keyword nodes, comprising at least one keyword node for each keyword of the set of keywords;
• Determine, based on the smallest set of keyword nodes and based on a number of ranked nodes, an optimal path set, where the optimal path set includes paths in the knowledge graph connecting nodes that match the keywords of the keyword query and where the optimal path set is optimal with respect to the minimum cost of the path set, where the cost is based on a linear combination of the total weight of nodes of the optimal path set and pairwise semantic distances between the nodes of the optimal path set, and
• Extracting an answer to the keyword query from the optimal path set.

The smallest set of keyword nodes is the smallest set among all sets of keyword nodes that includes at least one keyword node for each keyword of the set of keywords.

An optimal path set is determined based on the smallest set of keyword nodes and based on a number of ranked nodes. The number of nodes ranked may be specified. The number can vary depending on the size of the knowledge graph, for example.

A path set is considered to be a set of paths connecting a common root node to nodes matching the keywords of the keyword query.

The optimal path set is considered to be the set of paths with minimum cost.

The answer to the keyword query is based on the optimal path set. Therefore, the answer itself is optimal in terms of minimum cost.

The cost of the optimal path set is based on a linear combination of the total weight of nodes of the optimal path set and pairwise semantic distances between the nodes of the optimal path set.

By determining the optimal path set based on the smallest set of keyword nodes and based on a number of ranked nodes, the method does not process every node in the knowledge graph, only promising nodes. Therefore, the calculation of the response can be speeded up efficiently while reducing the amount of calculation.

According to one embodiment, the total weight of a node represents salience and/or the pairwise semantic distance between two nodes represents semantic belonging. Weights are assigned in the knowledge graph to its nodes and/or edges. Semantic distances are associated in the knowledge graph with pairs of its nodes. The weights and semantic distances are preferably pre-computed and pre-stored, e.g. in a main memory or a database, e.g. together with the knowledge graph.

More conspicuous (salient) graph elements include smaller weights. Less conspicuous graph elements include larger weights. Semantic spacing should not be confused with graph spacing. In fact, two entities that are close to each other in the graph structure can be semantically far apart, e.g. B. belong to unrelated topics in the knowledge graph. Graph elements that belong more closely together include a small semantic distance. Fewer related graph elements encompass a larger semantic distance. By including semantic distance in the method, the semantic coherence of a response can be improved.

The method solves the problem of computing semantically related answers to keyword queries in an efficient manner.

• 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.

According to one embodiment, the step of determining an optimal path set comprises an iterative process based on determining a locally optimal path set, where the locally optimal path set includes paths in the knowledge graph that connect the root node to nodes that match the keywords of the keyword query, and where the locally optimal path set is optimal in terms of minimum cost of the path set for the corresponding root node, where the iterative process includes the following steps:

• determining an overall minimum length of a path of the locally optimal path set by determining, for each keyword node, the shortest path from the corresponding root node;
• determining a lower bound on the cost of the locally optimal path set; determining the cost of each path that is greater than the total minimum path length;
• comparing the cost of each path greater than the total minimum path length to the lower bound;
• Obtain the minimum cost path set as the locally optimal path set.

• Erhalten der lokal optimalen Pfadmenge mit den minimalen Kosten als die optimale Pfadmenge.

According to one embodiment, the step of determining an optimal path set includes:

• Obtain the locally optimal path set with the minimum cost as the optimal path set.

According to one embodiment, the step of determining, for a root node of the knowledge graph, a locally optimal set of paths is improved with at least one pruning strategy.

• Zusammenführen der Pfade der optimalen Pfadmenge in einen Untergraphen des Wissensgraphen.

According to one embodiment, the step of extracting an answer from the optimal path set includes:

• Merging the paths of the optimal path set into a subgraph of the knowledge graph.

• Entfernen unnötiger Knoten und Kanten aus dem Untergraphen.

According to one embodiment, the step of extracting an answer from the optimal path set further comprises:

• Remove unnecessary nodes and edges from the subgraph.

Further embodiments relate to a device for keyword searches in a data set, data in the data set being represented by a knowledge graph, the knowledge graph comprising nodes representing entities in the data set and edges representing relationships between the entities, the device comprising a comprises an input configured to receive a keyword query comprising a set of keywords and configured to map keywords to nodes of the knowledge graph,
the device further comprising a processor, the processor being configured to rank the nodes of the knowledge graph based on a shortest path to keyword nodes, a keyword node being a node associated with at least one keyword of the keywordab question matches; selecting the smallest set of keyword nodes among all sets of keyword nodes, comprising at least one keyword node for each keyword of the set of keywords; Determine, based on the smallest set of keyword nodes, an optimal path set, where the optimal path set includes paths in the knowledge graph that connect nodes that match the keywords of the keyword query, and where the optimal path set is optimal in terms of minimum cost of the path set, where the cost is based on a linear combination of the total weight of nodes of the optimal path set and pairwise semantic distances between the nodes of the optimal path set, and extracting an answer to the keyword query from the optimal path set, and wherein the facility comprises an output adapted to the answer to a result of the keyword query and is adapted to output the result.

According to one embodiment, the device is designed to carry out steps of the method according to the described embodiments.

Further embodiments relate to a computer program for keyword searching in a data set, comprising computer-readable instructions which, when executed by a computer, cause the computer to carry out steps of the described method.

• 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.

Further embodiments can be derived from the following description and the drawing. In the drawing:

• 1 depicts an example knowledge graph;
• 2 illustrates aspects of a keyword search facility, and
• 3 illustrates aspects of a method for keyword searching.

1 represents an example knowledge graph, WG, 100.

The WG 100 includes a first node 102, a second node 104, a third node 106, a fourth node 108, a fifth node 110, a sixth node 112, a seventh node 114, an eighth node 116, a ninth node 118, a tenth node 120, an eleventh node 122 and a twelfth node 124. An edge 126 of the WG 100 begins at node 104 and ends at node 102. An edge 128 of the WG 100 begins at node 106 and ends at node 104. An edge 130 of the WG 100 begins at node 106 and ends at node 108. An edge 132 of WG 100 begins at node 108 and ends at node 110. Other edges of WG 100 are edge 134 between node 104 and node 112, edge 136 between the node 108 and node 114, edge 138 between node 108 and node 116, edge 140 between node 118 and node 112, edge 142 between node 112 and node 120, edge 144 between node 114 and node 122, the Edge 146 between node 114 and node 124, edge 148 between node 114 and node 116, and edge 150 between node 120 and node 122.

The WG 100 may include more or fewer nodes and/or more or fewer edges. In the example, WG 100 represents exemplary knowledge. Corresponding WGs can be used to analyze data from other areas, in particular technical areas.

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)

In the example, the information is mapped onto the nodes and the edges according to the following mapping from node reference numbers to keyword and the following mapping from edge reference characters to keyword.

102

Republican Party

104

George HW Bush

106

Anne Hutchinson

108

Franklin D Roosevelt

110

John Aspinwall Roosevelt

112

Barbara Bush

114

James Roosevelt

116

Democratic Party

118

The After Party: The Last Party 3

120

Mercedes

122

Germany (Germany)

124

World War II

126

party

128

descendant

130

descendant

132

child

134

grandchild

136

child

138

party

140

starring (main role)

142

drives

144

visited

146

battle

148

party

150

made in

The WG 100 is used as a data set for keyword searches in the data set in the example. The invention is not limited to keywords that are human readable or understandable. More generally, the term keyword in this context refers to any symbol or pattern in the data that can be analyzed with a corresponding WG.

A first subgraph 152, representing an example keyword search result, comprises the second node 104, the third node 106, the fourth node 108, the sixth node 112, the seventh node 114 and the edges between these nodes. The first subgraph 152 in this example represents a response to a query represented by a first keyword "Barbara Bush" and a second keyword "James Roosevelt".

A second subgraph 154, representing another example keyword search result, includes the sixth node 112, the seventh node 114, the tenth node 120, and the eleventh node 122 and the edges between those nodes. The second subgraph 154 in this example represents another response to the query represented by the keywords "Barbara Bush" and "James Roosevelt".

Aspects of a facility 200 for keyword searches in the dataset are in 2 shown.

The device 200 includes an input 202, a processor 204 and an output 206. The input 202 in the example provides an interface for keywords of the data to be searched for. The processor 204 is arranged to determine the first subgraph 152 and/or the second subgraph 154. The output 206 is arranged to map the answer to a result of the keyword query and arranged to output the result of the keyword search.

WG 100 may be stored on memory 208 in device 200 . The WG 100 may be stored on storage external to the device 200 . Data links connect input 200 and processor 204, output 206 and processor 204, and memory 208 and processor 204. Computer-readable instructions may be stored in memory 208 or on a different memory. The processor 204 is configured in the example to execute the computer-readable instructions for performing the keyword search according to the method described below with reference to FIG 3 is described.

The method for keyword searching is described for a knowledge graph G = 〈V, E〉, where V is a set of n numeric representations of vertices v ₁ ..., v _n and E ⊆ V × V is a set of m numeric representations of directed ones Edges are the relationships between entities represented by the nodes. Entities and relationships can be tagged with text, e.g. B. their names are referred to. The edges in the graph can be oriented in different directions. In the exemplary WG 100, n = 12 and m = 13.

The keyword search is based on a keyword query Q=(k ₁ ,...,kg }, which includes the _g keywords k ₁ ,..., _kg .

In a step 302, a keyword query Q comprising a set of keywords k ₁ , ..., k _g is received. The keywords are mapped to numeric representations of nodes. In the example, the g keywords k ₁ ,...,k _g are mapped to g numeric representations of nodes v ₁ ...,v _g . A keyword can be mapped to multiple nodes. In one aspect, at least one of the g keywords k ₁ ,...,k _g is mapped to at least one numeric representation of nodes v ₁ ,...,v _g .

In order to obtain a result for each of the g keywords k ₁ ,...,k _g , each of the g keywords k ₁ ,...,k _g is mapped to at least one numeric representation of nodes v ₁ ...,v _g . If a keyword cannot be mapped to any node in the knowledge graph, the result can be empty.

A keyword matching function can be used to map a keyword to any node of the knowledge graph. For example, the matching function can be based on literal labels that include a keyword. However, the invention is not limited to any specific mapping function.

According to the example, the query includes g = 2 keywords, and the first keyword k ₁ ="Barbara Bush" maps to the numeric representation of node 112, and the second keyword k ₂ ="James Roosevelt" maps to the numeric representation of nodes 114 pictured.

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 one aspect, the function hits can: $$\mathbb{K}\to 2^V$$

be used to map a set IK of keywords to a subset of the numerical representations of the knowledge graph G nodes. The specific implementation of hits, ie the manner in which keywords are matched with designations of entities, is not the focus of this disclosure. In this aspect, Hits(k _i ) are denoted as K _i for 1≦i≦g. Where K _i are the numeric representations of a set of nodes to which the keyword maps, also called keyword nodes. The method is not limited to this way of mapping.

In the disclosure, edge mapping is omitted, but edge mapping can be transformed into node mapping by dividing the edges. In particular, subdividing an edge (u, v) gives a new node w with the labels of the edge (u, v) and then replaces (u, v) with two new edges (u, w) and (w, v).

Given G = (V, E), a response to Q is defined as a subgraph of G denoted by T = 〈V _T , E _T 〉, where the subgraph T satisfies the following requirements. (1) T is connected. (2) T contains at least one keyword node from each K _i for 1 ≤ i ≤ g, ie T _T n K _i ≠ Ø. (3) T is structurally minimal for (1) and (2), ie none of its proper subgraphs satisfies both (1) and (2). Structural minimality indicates that T has a tree structure, with leaf nodes being keyword nodes.

The process of calculating the answer is described below.

In a step 304, nodes of the knowledge graph are ranked based on a shortest path to keyword nodes, where a keyword node is a node that matches at least one keyword of the keyword query;

In a step 306, a smallest set of keyword nodes K _{i at least .} selected among all sets of keyword nodes comprising at least one keyword node for each keyword of the set of keywords.

In a step 308, an optimal path set in the knowledge graph G based on the smallest set of keyword nodes K _{i at least} and determined based on a number of ranked nodes.

The number of nodes ranked may be specified. The number can vary depending on the size of the knowledge graph, for example. For example, for a knowledge graph with about 30,000 and 3,000,000 nodes, this number can range from 5 to 20. The number can be given based on experiments. It should be noted that any other number can be selected.

The optimal path set includes paths in the knowledge graph that connect nodes that match the keywords of the keyword query, and where the optimal path set is optimal in terms of minimum cost of the path set, where the cost is based on a linear combination of the total weight of nodes of the optimal path set and pairwise semantic distances between the nodes of the optimal path set.

The optimal path set is optimal in terms of minimum cost of the path set, where the cost is based on a linear combination of the total weight of nodes of the optimal path set and pairwise semantic distances between the nodes of the optimal path set.

For G = 〈V, E〉, a weighting function maps nodes to non-negative real numbers, denoted by wt: V ↦ ℝ _≥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.A semantic distance function sd maps pairs of nodes to non-negative real numbers, denoted by sd: V × V ↦ ℝ _≥0 . This pseudometric function satisfies for all u, v, w ∈ V: $$s\mathrm{i.e}\left(v,v\right)=\mathrm{0,}$$

i.e. indistinguishability of identical values, $$s\mathrm{i.e}\left(\mathrm{and},v\right)=s\mathrm{i.e}\left(v,\mathrm{and}\right),$$

i.e. symmetry and $$s\mathrm{i.e}\left(\mathrm{and},v\right)\le s\mathrm{i.e}\left(\mathrm{and},w\right)+s\mathrm{i.e}\left(w,v\right),$$

ie triangle inequality.

The measurement of semantic distance can be independent of graph structure and node weights. In particular, it differs from graph distance, namely the number of edges of a shortest path. For example, adjacent nodes may be semantically distant from each other.

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.The cost of an answer T = 〈V _T , E _T 〉 is the total weight of its nodes and their pairwise semantic distances: $$cOst\left(T\right)=a{\displaystyle \sum _{v\in V_T}wt\left(v\right)}+\left(1-a\right){\displaystyle \sum _{\begin{array}{l}{v}_i,v_j\in V_T\\ i<j\end{array}}s\mathrm{i.e}\left(v_i,v_j\right)},$$

where α ∈ [0,1] is a parameter. In the cost equation, the first element represents the salience of the nodes of T, and the second element characterizes their semantic togetherness. The method does not require a specific implementation of the weight wt and the semantic distance sd. The weight wt and the way the semantic distance sd is determined can be chosen such that the relevance of the query, the centrality in the graph structure, the Semantics in the designations etc. are taken into account. Edmund Ihler, 1991, The Complexity of Approximating the Class Steiner Tree Prob lem, in WG 1991, 85-96; https://doi.org/10.1007/3-540-55121-2_8 provides an example of the weight wt; Gaurav Bhalotia, Arvind Hulgeri, Charuta Nakhe, Soumen Chakrabarti and S Sudarshan, 2002, Keyword Searching and Browsing in Databases using BANKS, in ICDE 2002, 431-440; https://doi.org/10.1109/ICDE.2002.994756 provides an example of the semantic distance sd. Small weights represent salience, and small semantic distance represents togetherness. The calculation of the weight wt and the semantic distance sd can be independent of each other. In the knowledge graph, weights are assigned to their nodes. For example, weights of nodes are precalculated, e.g. B. using normalized pageRank.

For example, in the knowledge graph, edges are precomputed relationships between nodes.

For example, in the knowledge graph, semantic distances are precomputed for pairs of its nodes.

A goal of the method 300 is to determine an optimal response, where an optimal response is a response that minimizes cost. The method 300 extends the well-known GST minimum weight problem, for example described in Edmund Ihler, 1991, The Complexity of Approximating the Class Steiner Tree Problem, by introducing quadratic terms sd(v _i ,v _j ) into the objective function that represent additional costs, to be paid when two vertices v _i and v _j are both contained in T.

In accordance with an aspect of the disclosure, steps 304 through 308 may be implemented by the following Algorithm 1, comprising lines 1 through 14: $$\text{input}:G=〈V,E〉\text{and}Q=\left\{k_1,...,k_G\right\}$$

• 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.

Step 308 and the OptimizedRPS(G,Q,r) algorithm of line 10 are described in detail below with reference to Algorithm 2:

• The step 308 of determining an optimal path set includes an iterative process 308a based on determining a locally optimal path set, where the locally optimal path set includes paths in the knowledge graph that connect a root node of the smallest set of keyword nodes with nodes associated with the keywords of the keyword query and where the locally optimal path set is optimal in terms of minimum cost of the path set for the corresponding root node, the iterative process 308a comprising the steps of:
  • determining an overall minimum path length of the locally optimal path set by determining, for each keyword node, the shortest path from the corresponding root node;
  • determining a lower bound on the cost of the locally optimal path set; Determine the cost of any path greater than the
  • total minimum path length is;
  • Compare the cost of each path greater than that
  • total minimum path length is, with the lower bound;
  • Obtain the minimum cost path set as the locally optimal path set.

• Erhalten der lokal optimalen Pfadmenge mit den minimalen Kosten als die optimale Pfadmenge.

The step 308 of determining an optimal path set further includes the following:

• Obtain the locally optimal path set with the minimum cost as the optimal path set.

In G = (V, E), an RPS is a set of paths relevant to a query Q = {k ₁ ,...,k _g }. In particular, given r ∈ V, called the root node, a locally optimal path set r-RPS, denoted by P _r = {P ₁ ,...,P _g }, is a set of g paths such that for 1 ≤ i ≤ g any P _i = (V _{P i} , E _{P i} ) is an r - K _i -path, or, more specifically, an r - vi _{i -path connecting r to a keyword node vi ∈ K i .} Note that for i ≠ j it is possible that K _i ∩ K _j ≠ 0 and P _i = P _j .

Cost of an r-RPS, denoted by P _r = {P ₁ ,..., P _g } with P _i = 〈V _{P i} , E _{P i} 〉 for 1 ≤ i ≤ g, is given by the following cost function: $$pcOst\left(P_{\mathrm{right}}\right)=a\left(wt\left(\mathrm{right}\right)+{\displaystyle \sum _{P_i\in P_{\mathrm{right}}}{\displaystyle \sum _{v\in V_{P_i\left\{\mathrm{right}\right\}}}wt\left(v\right)}}\right)+\left(1-a\right)\frac{vn\mathrm{and}m\left(P_{\mathrm{right}}\right)}{2}{\displaystyle \sum _{P_i\in P_{\mathrm{right}}}{\displaystyle \sum _{v\in V_{P_i\left\{\mathrm{right}\right\}}}s\mathrm{i.e}\left(\mathrm{right},v\right)}}.$$

The vnum function counts the nodes in an RPS. It intentionally counts the root node r only once: $$vn\mathrm{and}m\left(P_{\mathrm{right}}\right)=1+{\displaystyle \sum _{P_i\in P_{\mathrm{right}}}\left|V_{P_i}\backslash \left\{\mathrm{right}\right\}\right|}.$$

For each root node r ∈ V, a locally optimal path set r-RPS, i.e. an r-RPS that minimizes pcost, is determined as follows: $$P_{\mathrm{right}}^{min}=a\mathrm{right}G\underset{P_{\mathrm{right}}}{\text{at least}}pcOst\left(P_{\mathrm{right}}\right)$$

According to one aspect of the disclosure, the following variant of pcost is defined: $$pcOst\text{'}\left(P\mathrm{right}\right)=pcOst\left(P\mathrm{right}\right)-awt\left(\mathrm{right}\right)$$

Since αwt(r) appears in pcost of every r-RPS, minimizing the pcost' function is equivalent to minimizing pcost: $$P_{\mathrm{right}}^{min}=a\mathrm{right}G\underset{P_{\mathrm{right}}}{\text{at least}}pcOst\left(P_{\mathrm{right}}\right)=a\mathrm{right}G\underset{P_{\mathrm{right}}}{\text{at least}}pcOst\text{'}\left(P_{\mathrm{right}}\right).$$

Minimizing the pcost' function calculates the sum of the costs of a set of paths.

However, pcost' contains vnum(Pr), which depends on P _r and is unknown when computing a minimum cost path.

Therefore, every possible value of vnum(Pr) is considered and therefore becomes a constant in every case.

For example, P _r is subject to vnum(P _r ) = n. For a path P = 〈V _P , E _p 〉 starting with the root node r, we have defined: $$p{l}_n\left(P\right)={\displaystyle \sum _{v\in V_P\backslash \left\{\mathrm{right}\right\}}awt\left(v\right)}+n\frac{1-a}{2}s\mathrm{i.e}\left(\mathrm{right},v\right).$$

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]$$

For v ∈ V the minimum pln of rv-paths, which contain exactly m edges, is computed iteratively as follows: $$p{\mathrm{i.e}}_n\left[v\right]\left[m\right]=\{\begin{array}{cc}0& m=\mathrm{0,}v=\mathrm{right},\\ \infty & m=\mathrm{0,}v\ne \mathrm{right}\\ \underset{\mathrm{and}\in N\left(v\right)}{\text{at least}}p{\mathrm{i.e}}_n\left[\mathrm{and}\right]\left[m-1\right]+awt\left(v\right)+n\frac{1-a}{2}s\mathrm{i.e}\left(\mathrm{right},v\right)& m>0\end{array}$$

where N(v) is the set of neighbors of v in G. The minimum pln of rK _i paths spanning exactly m edges is denoted by $$p\mathrm{i.e}{k}_n\left[i\right]\left[m\right]=\underset{v\in K_i}{\text{at least}}p{\mathrm{i.e}}_n\left[v\right]\left[m\right]$$

For 1 ≤ 1 ≤ g let Q _I ⊆ Q be the first I keywords in Q: $$Q_I=\left\{k_1,...,k_I\right\}.$$

The minimum pcost' of r-RPSs that contain a total of exactly m edges and are relevant to Q i (i.e., comprise I paths - one rK _i -path for each 1 ≤ i ≤ I) are computed iteratively by: $$p{c}_n\left[I\right]\left[m\right]=\{\begin{array}{cc}p\mathrm{i.e}{k}_n\left[I\right]\left[m\right]& I=1\\ \underset{0\le x\le min\left\{m,\left|V\right|-1\right\}}{\text{at least}}p{c}_n\left[I-1\right]\left[m-x\right]+p\mathrm{i.e}{k}_n\left[I\right]\left[x\right]& I>1.\end{array}$$

Since P _r with vnum(P _r ) = n contains a total of n - 1 edges, pc _n [g] [n - 1] is considered. Finally, over all possible values of vnum(P _r ), is obtained. $$\underset{P_{\mathrm{right}}}{\text{at least}}pcOst\text{'}\left(P_{\mathrm{right}}\right)=\underset{1\le n\le 1+G\left(\left|V\right|-1\right)}{\text{at least}}p{c}_n\left[G\right]\left[n-1\right]$$

For each n, pc _n [g][n-1] is computed and P _r - the r-RPS with actual minimum pcost' with vnum = n - is reconstructed. The reconstruction can be implemented by looking up additional fields in which computed minimum cost paths and RPSs are recorded in a standard manner.

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.Finally will $P_{\mathrm{right}}^{min}$

updated, and the r-RPS with locally minimum pcost is returned as the optimal path set P ^# , where P ^# denotes the RPS with globally minimum pcost.

This is done by step 308 of obtaining the locally optimal path set r-RPS with the minimum cost as the optimal path set P ^# .

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

mit lokal minimalem pcost

In accordance with one aspect of the disclosure, step 308, particularly iterative process 308a of step 308, may be implemented by the following Algorithm 2, comprising lines 1 through 27: $$\text{input}:G=〈V,E〉,Q=\left\{k_1,...,k_G\right\},$$

and r ∈ V output: an r-RPS $P_{\mathrm{right}}^{min}$

with locally minimal pcost

Lines 3 to 5 of Algorithm 2 relate to the step of determining an overall minimum length of a path of the locally optimal path set by determining, for each keyword node, the shortest path from the corresponding root node.

Line 6 refers to the step of determining a lower bound on the cost of the locally optimal path set. This is a measure to truncate large values of n, see lines 1 through 5. In the exemplary algorithm for step 306 shown above, the outermost loop ends in line 7 with n = (|V| - 1), which can be a large value can. A lower bound on pcost(P _r ) with vnum(P _r ) = n for truncating large values of n is computed. pcost(P _r ) is given by $$\begin{array}{c}pcOst\left(P\mathrm{right}\right)=awt\left(\mathrm{right}\right)+pcOst\text{'}\left(P\mathrm{right}\right)\\ pcOst\text{'}\left(P\mathrm{right}\right)={\displaystyle \sum _{P_i\in P_{\mathrm{right}}}{\displaystyle \sum _{v\in V_{P_i}\backslash \left\{\mathrm{right}\right\}}awt\left(v\right)}+n\frac{1-a}{2}s\mathrm{i.e}\left(\mathrm{right},v\right).}\end{array}$$

The function pcost' calculates the sum of the costs of g paths - an rK _i -path for every 1 ≤ i ≤ g.

By mapping the cost of an rK _i -path into the length, i.e. the total edge weight, of an rK _i -path in an edge-weighted graph, its lower bound can be obtained by computing the length of a shortest path, i.e. an rK _i -path with minimum weight in this edge-weighted graph. This can be implemented by extending the algorithm as follows. At the beginning of the outermost loop, an edge-weighted directed graph G _r,n = 〈V _r,n ,〉 E _r,n 〉, where V _r,n = V and each edge (u, v) ∈ E two directed edges ( corresponds to u, v), (v, u) ∈ E _r,n . Each directed edge (u, v) ∈ E _r,n is weighted by $$awt\left(v\right)+n\frac{1-a}{2}s\mathrm{i.e}\left(\mathrm{right},v\right).$$

The Dijkstra algorithm can be used on Gr,n to compute a minimum weight rK _i -path for any 1 ≤ i ≤ g denoted by P _{r ,n,i} . It has the smallest total edge weight among rK _i -paths in G _r,n , denoted by d _r,n,i . Therefore a lower bound for pcost(P _r ) with vnum(P _r ) = n is given by $$D_{\mathrm{right},n}=awt\left(\mathrm{right}\right)+{\displaystyle \sum _{1\le i\le G}{\mathrm{i.e}}_{\mathrm{right},n,i}}.$$

D _r,n increases as n increases, so the following inequality can be checked: $$D_{\mathrm{right},n}\ge pcOst\left(P_{\mathrm{right}}^{min}\right).$$

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).$$

If they are for the current n and $P_{\mathrm{right}}^{min}$

holds, the outermost loop is broken, and the current one $P_{\mathrm{right}}^{min}$

is returned because for the current and larger values of n, ie vnum(Pr), there is no P _r with a smaller pcost. Similarly, the following inequality can be checked: $$D_{\mathrm{right},n}\ge pcOst\left(P^{\#}\right).$$

wird zurückgegeben, siehe Zeilen 26 und 27.If true for the current n and P ^# , which is the current RPS with global minimum pcost in algorithm QO, the outermost loop is broken, and the current one $P_{\mathrm{right}}^{min}$

is returned, see lines 26 and 27.

Lines 7 through 22 refer to the step of determining the cost of each path that is greater than the total minimum path length. The loop in line 7 starts with n = L _r . This is a measure to truncate small values of n, see lines 1 to 5. A lower bound on vnum(P _r ) (ie n) for truncating small values of n is computed. To start the algorithm, a breadth-first search of G starting with r can be inserted to compute the smallest number of edges in rK _i -paths for each 1 ≤ i ≤ g, denoted by l _r,i . A lower bound for vnum(P _r ) is given by $$L_{\mathrm{right}}=1+{\displaystyle \sum _{1\le i\le G}{l}_{\mathrm{right},i}}.$$

Line 23 refers to the step of comparing the cost of each path greater than the total minimum path length to the lower bound.

Line 24 refers to the step of obtaining the minimum cost path set as the locally optimal path set.

• 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.

The step 308 of determining an optimal path set further includes the following:

• Obtain the locally optimal path set with the minimum cost as the optimal path set. This is implemented by lines 11 and 12 of Algorithm 1.

According to a further pruning strategy, the minimum weight rK _i -path can be exploited for each 1 ≤ i ≤ g, denoted by P _r,n,i . The number of edges in P _r,n,i is given by the number i _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\}.$$

An r-RPS P _r with vnum(P _r ) = n for the current n is assumed to be a locally minimum cost r-RPS. If, for any 1 ≤ i ≤, the rK _i -path P _i ∈ P _r contains more than l _r,n,i edges, then P _i is replaced by P _r,n,i to get another r-RPS P _r ' to create. Its defined total edge weight is no larger than that of P _r , and its vnum is smaller. Hence pcost(P _r ') ≤ pcost(P _r ), ie P _r ' is also an r-RPS with locally minimum pcost which and/or any other r-RPS with locally minimum pcost in previous iterations of the outermost loop for smaller values of n were found. It is therefore not necessary to consider P _r for the current n. This can be implemented by expanding the algorithm as follows: narrowing the ranges of m and x: $$m\text{to}min\{n-\mathrm{1,}\left|V\right|-\mathrm{1,}{l}_{\mathrm{right},n,i},$$

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

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

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

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

The method further includes a step 310 of extracting an answer to the keyword query from the optimal path set P ^# .

The answer is defined as $$T^{\#}=〈V_{T^{\#}},E_{T^{\#}}〉$$

The step 310 is described in more detail in terms of a step 312 of merging the paths of the optimal path set into a subgraph of the knowledge graph and a step 314 of removing unnecessary nodes and edges from the subgraph.

The optimal path set P ^# is converted into an answer T ^# as follows. All r-vi paths in P _r are merged into a subgraph T ^# of G connected via a root node r and containing v _i e K _i for 1 ≤ i ≤ g.

According to the requirements for an answer T described above, T must satisfy the requirement to be structurally minimal. Therefore, the response T ^# is an optimal response if it is structurally minimal. If not, the step 314 of removing unnecessary nodes and edges from the subgraph is repeatedly processed until it becomes structurally minimal.

According to the 1 In the exemplary knowledge graph 100 shown, an answer to the search query is given, for example, by the subgraph 152. Subgraph 152 is semantically connected compared to the other subgraph 154 which is semantically discontinuous. Therefore, subgraph 152 is the preferred response according to this embodiment.

In a step 316, the response may be mapped to a keyword query result and the keyword search result may be output.

Claims (11)

Computer-implemented method (300) for keyword searches in a dataset, data of the dataset being represented by a knowledge graph (100), the knowledge graph (100) comprising nodes representing entities of the dataset and edges representing relationships between the entities, the method (300) comprising the steps of: receiving (302) a keyword query comprising a set of keywords; ranking (304) nodes of the knowledge graph based on a shortest path to keyword nodes, a keyword node being a node that matches at least one keyword of the keyword query; selecting (306) the smallest set of keyword nodes among all sets of keyword nodes, comprising at least one keyword node for each keyword of the set of keywords; determining (308) an optimal path set based on the smallest set of keyword nodes and based on a number of ranked nodes, the optimal path set including paths in the knowledge graph (100) connecting nodes that match the keywords of the keyword query , and wherein the optimal path set is optimal in terms of minimum cost of the path set, the cost being based on a linear combination of the total weight of nodes of the optimal path set and pairwise semantic distances between the nodes of the optimal path set, and extracting (310) a response to the keyword query from the optimal path set. Method (300) according to claim 1 , where the total weight of a node represents salience, and/or the pairwise semantic distance between two nodes represents semantic belonging. Method (300) according to claim 1 or 2 , where the cost of a path set is given by the sum of the total weight of the root node and the total weights of the nodes matching the keywords of the keyword query, and the pairwise semantic distances between the root node and the nodes matching the keywords of the keyword query. Method (300) according to any one of the preceding claims, wherein the step (308) of determining an optimal path set comprises an iterative process (308a) based on determining a locally optimal path set, the locally optimal path set comprising paths in the knowledge graph (100), connecting a root node of the smallest set of keyword nodes to nodes matching the keywords of the keyword query, and wherein the locally optimal path set is optimal in terms of minimum cost of the path set for the corresponding root node, the iterative process (308a) comprising the following steps: determining an overall minimum path length of the locally optimal path set by determining, for each keyword node, the shortest path from the corresponding root node; determining a lower bound on the cost of the locally optimal path set; determining the cost of each path that is greater than the total minimum path length; comparing the cost of each path greater than the total minimum path length to the lower bound; Obtain the minimum cost path set as the locally optimal path set. Method (300) according to claim 4 , wherein the step (308) of determining an optimal path set comprises: obtaining the locally optimal path set with the minimum cost as the optimal path set. Method (300) according to one of the preceding claims, wherein the iterative process (308a) of the step (308) of determining an optimal path set is extended by at least one shortening strategy. A method according to any one of the preceding claims, wherein the step of extracting (310) the answer from the optimal path set comprises: Merging (312) the paths of the optimal path set into a subgraph of the knowledge graph (100). The method of any preceding claim, wherein the step (310) of extracting the answer from the optimal path set further comprises: Remove (314) unnecessary vertices and edges from the subgraph. Device (200) for searching for keywords in a data set, data of the data set being represented by a knowledge graph (100), the knowledge graph (100) having nodes (V) representing entities of the data set and edges (E) representing relationships between the represent entities, wherein the device comprises an input which is designed to receive a keyword query (Q) comprising a set of keywords and is designed to map keywords to nodes of the knowledge graph (100), the facility further comprising a processor (204), the processor (204) being configured to rank (304) the nodes of the knowledge graph based on a shortest path to keyword nodes, a keyword node being a node associated with at least one keyword of the keyword query agrees; selecting (306) the smallest set of keyword nodes among all sets of keyword nodes, comprising at least one keyword node for each keyword of the set of keywords; determining (308) an optimal path set based on the smallest set of keyword nodes and based on a number of ranked nodes, the optimal path set including paths in the knowledge graph (100) connecting nodes that match the keywords of the keyword query , and wherein the optimal path set is optimal in terms of minimum cost of the path set, where the cost is based on a linear combination of the total weight of nodes of the optimal path set and pairwise semantic distances between the nodes of the optimal path set, and extracting (310) a response to the keyword query from the optimal path set, and wherein the means comprises an output (206) arranged to map the response to a result of the keyword query and arranged to output the result. Setup (200) after claim 9 , wherein the device (200) is further designed to carry out steps of the method (300) according to one of claims 2 until 8th . A computer program for searching for keywords in a data set, comprising computer-readable instructions which, when executed by a computer, cause the computer to perform steps of the method (300) according to any one of Claims 1 until 8th to execute.

Images