Search in knowledge graphs

The present disclosure relates to a method for searching a graph representing content of digital objects. A set of operations for traversing the graph may be determined according to a search request. The set of operations may be executed, resulting in intermediate result vectors of nodes and a result vector of nodes, wherein the result vector of nodes is associated with a result set of one or more object units of the digital objects. Intermediate result vectors may be selected from of the intermediate result vectors. A set of result entities may be identified. The set of result entities are entities which are part of the object units and part of entities represented by nodes of said selected intermediate result vectors. The set of result entities and the result set of object units may be provided as a result of the search request.

BACKGROUND

The present disclosure relates to the field of digital computer systems, and more specifically, to a method for searching a graph representing content of digital objects.

Knowledge graphs (KGs) from large document collections are an important research strategy, e.g., for the oil and gas industry, or for Covid-19 literature. The KG may be assembled or built using natural-language processing (NLP). The NLP enables to identify entities and relationships. Results are stored as graph nodes, with edges to their sources.

SUMMARY

In certain embodiments, a computer-implemented method is provided for searching a graph representing content of digital objects, the graph comprising nodes representing entities and edges representing relationships between the entities, the entities being descriptive of the content of the digital objects. The method comprises: receiving a search request; determining a set of operations for traversing the graph according to the search request, wherein each operation of the set of operations receives an input and provides, as output, a vector of nodes; executing the set of operations, resulting in intermediate result vectors of nodes and a result vector of nodes, the result vector of nodes being associated with a result set of one or more object units of the digital objects; retrieving at least part of the result set of object units of the digital objects; selecting intermediate result vectors of the intermediate result vectors; identifying a set of result entities as entities which are part of the retrieved object units and part of entities represented by nodes of said selected intermediate result vectors; providing the set of result entities of the result set of object units and the result set of object units as a result of the search request.

In certain embodiments, a computer program product is provided comprising a computer-readable storage medium having computer-readable program code embodied therewith, the computer-readable program code configured to implement all of the steps of the method according to preceding embodiments.

In certain embodiments, a computer system is provided for searching a graph representing content of digital objects, the graph comprising nodes representing entities and edges representing relationships between the entities, the entities being descriptive of the content of the digital objects. The computer system is configured for: receiving a search request; determining a set of operations for traversing the graph according to the search request, wherein each operation of the set of operations receives an input and provides, as output, a vector of nodes; executing the set of operations, resulting in intermediate result vectors of nodes and a result vector of nodes, the result vector of nodes being associated with a result set of one or more object units of the digital objects; retrieving at least part of the result set of object units of the digital objects; selecting intermediate result vectors of the intermediate result vectors; identifying a set of result entities as entities which are part of the retrieved object units and part of entities represented by nodes of said selected intermediate result vectors; providing the set of result entities of the result set of object units and the result set of object units as a result of the search request.

It should be noted that the exemplary embodiments are described with reference to different subject-matters. In particular, some embodiments are described with reference to method type claims whereas other embodiments may be described with reference to apparatus, system, or computer program product type claims. However, a person skilled in the art will gather from the above and the following description that, unless otherwise notified, in addition to any combination of features belonging to one type of subject-matter, also any combination between features relating to different subject-matters, in particular, between features of the method type claims, and features of the apparatus, system or computer program product type claims, is considered as to be described within this document.

DETAILED DESCRIPTION

Computer data storage is one of the core functions of a general-purpose computer. It enables the recording of information of digital objects. The digital object may include text, still images, audio, video, electronic documents, or other digital media formats. The digital objects may be advantageous as they can, for example, be stored in much less space than paper documents. The digital object may comprise object units. An object unit may be a portion of the digital object. For example, in case the digital object is an electronic document, the object unit may be a document unit such as a paragraph, chapter etc. In case the digital object is an image, the object unit may be a portion of the image. In case the digital object is a video, the object unit may be a frame of the video or a sequence of frames of the video.

In addition to storing digital objects, storage systems allow for searching and retrieving of the content contained in the digital objects. Although the notion of retrieving a particular object or part of an object may be simple, retrieval in the electronic context can be quite complex and powerful. This may particularly be challenging as the size of stored digital objects may be very high. For that, graphs may advantageously be used according to the present subject matter to enable an efficient access to the digital objects. The graph may represent content of the digital objects. The graph comprises nodes that represent entities and edges that represent relationships between the entities. The entities are descriptive of the content of the digital objects. The graph may be built or assembled by identifying entities and their relationships in the stored digital objects. The entity may be a real-world object, such as persons, locations, organizations, products, an object unit etc., that can be denoted with a proper name. The entity can be abstract or have a physical existence. Entities may be viewed as entity instances (e.g., New York City is an instance of a city). The entities may, for example, be determined according to an annotation method. The annotation method may, for example, process a digital object in order to identify entities present in the digital object. The annotation method may locate and classify entities mentioned in the digital object into predefined categories such as person names, organizations, locations, medical codes, time expressions, quantities, monetary values, percentages, etc. Distinct entities may be assigned unique identifiers respectively. In case of electronic documents, the annotation method may, for example, use a natural language processing (NLP) technique for the identification of the entities and their relationships. In case of images, the annotation method may use an image analysis to identify certain entities and store their name and position in the image (e.g., the position may be defined like a bounding box in millimeters relative to lower left image, or even a more complex contour), similar to how the NLP identifies entities by name and span (like “from character 42 to 46”). Then if it has been decided that an entity should be marked in this image, a marking procedure may be applied to this name and position. For example, a colored rectangle along the bounding box may be drawn and the colors may be explained, or the name could be next to the bounding box. The graph may further comprise extra nodes which represent extra data. The extra nodes may, for example, be obtained from a data catalogue.

The built graph may refer to a property graph where data values are stored as properties on nodes and edges. Property graphs may be managed and processed by a graph database management system. The graph may, for example, be a directed graph. The graph may be a collection of nodes (also called as vertices) and edges. The edge of the graph connects any two nodes of the graph. The edge may be represented by an ordered pair (v1, v2) of nodes and that can be traversed from node v1 toward node v2. A node of the graph may represent an entity. The entity may refer to a company, user etc. The entity (and the corresponding node) may have one or more entity attributes or properties which may be assigned values. For example, the entity attributes of the user may comprise a user ID, location of the user etc. The attribute values that represent the node are values of the entity attributes of the entity represented by the node. The edge may be assigned one or more edge attribute values indicative of at least a relationship between the two nodes connected to the edge. The attribute values that represent the edge are values of the edge attributes. The relationship may, for example, comprise an inheritance (e.g., parent and child) relationship and/or associative relationship in accordance with a certain hierarchy. For example, the inheritance relationship between nodes v1 and v2 may be referred to as a “is-a relationship” between v1 and v2 e.g., “v2 is-a parent of v1”. The associative relationship between nodes v1 and v2 may be referred to as a “has-a relationship” between v1 and v2 e.g., “v2 has a has-a relationship with v1” means that v1 is part or is a composition of or associated with v2.

The present subject matter may represent the graph in a format that enables an efficient access to the content of the digital objects. The graph may be represented in the computer in different ways. For example, the graph may be represented by an adjacency matrix. For example, in the adjacency matrix format, the graph-traversals can be directly translated into matrix vector multiplication operations. This may enable that most graph operations can be translated into matrix-operations using linear algebra.

Once built and stored, the present subject matter may use the graph to allow a user to specify search terms and return one or more object units which match the user's search terms. The term “user” may refer to an entity e.g., an individual, a computer, or an application executing on a computer that issues search requests. The returned object units may, for example, further indicate portions of the object units that are relevant for the search. This may particularly be advantageous as users expect that result mark-up relates to their queries—in particular business users who do not build query workflows themselves. The search results may be obtained by performing the set of operations on the graph. The set of operations may be operations of a workflow. The set of operations comprises an operation that provides the result of the search request; that operation may, thus, be named result operation. The set of operations may further comprise one or more operations that provide intermediate results; the one or more operations may thus be named intermediate operations. The intermediate results may be used to obtain the result of the search request. Each operation of the set of operations may receive one or more inputs and provide an output as a result of processing the inputs. The output may be a vector of nodes. The vector may, for example, comprise a number of elements that corresponds to the number of nodes in the graph. The elements of a given vector may be set to predefined values to indicate the nodes that belong to the given vector. For example, if a given node belongs to a vector, the vector element that is associated with the given node may have value 1, otherwise that vector element may have value 0. The output vector may be named result vector if it is output by the result operation. The output vector may be named intermediate result vector if it is output by an intermediate operation. The intermediate result vectors may be stored. The result vector may comprise nodes that represent object units such as paragraphs. Those object units may contain search results that the user is looking for. These object units may be named result object units. However, the result object units may contain much more content than what the user is searching for. The present subject matter may solve this issue by further providing the set of result entities that are of interest for the user. For example, in case the result object unit is a paragraph, the set of result entities may be highlighted in the paragraph before providing (e.g., displaying) the paragraph to the user. The set of result entities may be obtained by comparing the entities of the result object units and entities of selected intermediate result vectors. In one example, the selected intermediate result vectors may be selected a priori or posteriori. With the a priori approach, the intermediate result vectors may be selected before performing the set of operations. With the posterior approach, a backward processing of the intermediate search results and/or of the set of operations may be performed in order to select the intermediated result vectors that can be of interest for the user. Using different approaches may be advantageous as it may enable a flexible implementation of the present subject matter (e.g., different and refined selection techniques may be used). According to one embodiment, the method further comprises selecting the intermediate result vectors based on a selection criterion requiring any one of: a selection based on the type of operations that precedes or follows the result operation, a random selection of a subset of intermediate result vectors, a selection of intermediate result vectors of operations succeeding an initial operation of the set of operations, a selection of an intermediate result vector of an operation immediately preceding the operation that resulted in the result vector, and a user selection of intermediate result vectors. According to one embodiment, the selected intermediate result vectors are all intermediate result vectors.

The present embodiments may enable execution of advanced graph-analytics as well as evaluate deep queries with multi-hop traversals on large graphs (e.g., with more than 1B edges) extremely fast. The speed at which the data is generated and processed may meet the demands and challenges that lie in the path of growth and development. The present subject matter may provide accurate search results. The users may interpret results better, and thus take better decisions on them. Compared with plain searches, the graphs may offer much better performance, and a much wider range of possible query workflows.

According to certain embodiments, the graph is stored in a first storage device and the digital objects are stored in a second storage device, wherein the first storage device has higher data access performance than the second storage device. Data access performance may comprise speed of the data access and/or Input/Output operations per time interval and/or a latency for each of the read operations. For example, hard disk data access performance is low or much lower (e.g., slower) than the memory access. The first storage device comprises a memory such as RAM. The second storage device comprises disk-based storage such as hard disk. Storing the graph in memory may enable to traverse it with efficient vector arithmetic. Using the second storage device may be advantageous as larger data fields of nodes, e.g., the texts or PDF versions of underlying articles, may be stored on disks. They may only be retrieved when search results are viewed. Search queries can be workflows using graph structures. For example, they contain edge traversal, intersection, or union of results from different paths, etc. According to certain of the present embodiments, if one views results like paragraphs, not only general annotations from assembly time can be marked up (e.g., underlined in colors) but also specific results from the current search may be marked.

According to certain embodiments, the method further comprises associating each node of the graph with an identifier for identifying the entity represented by said each node, wherein the identifying of the set of result entities comprises: comparing the identifiers of entities of the object units with the identifiers of nodes of the selected intermediate result vectors; wherein the set of result entities are the matching entities. For example, the identifiers may be assigned to the nodes at the assembly time of the graph. That is, each identified entity that may be added as a node to the graph may be assigned a unique identifier. For example, if the entity “Company X” appears in 3 document units, one node representing “Company X” may be added to the graph and may have identity “12341234”. Then in all 3 document units, the mention of “Company X” is associated with this same identity “12341234”. The identifiers may be stored in the second storage device in association with the digital objects. For example, each digital object may be associated with a file such as a JSON file that contains the distinct entities identified in the digital object. Each entity in the file may be associated with its identifier. The identifier of an entity may also be provided as a property of the node that represents the entity in the graph. That is, the identifier of an entity may be stored in the second storage device and may be provided as part of the graph in the first storage device. The result set of object units may be retrieved in association with their associated files from the second storage device, where identifiers of each retrieved file may be compared with the identifiers in the nodes of the selected intermediate result vectors. This embodiment may provide searchable terms in paragraphs with identities during the graph assembly phase. This may enable to evaluate, when a result paragraph is viewed, which entities to mark in it, by referring back to the workflow and intermediate workflow execution results.

According to certain embodiments, the set of operations comprises at least two distinct subsets of operations comprising a first subset of intermediate operations and a second subset of intermediate operations, wherein the execution of the first and second subsets of intermediate operations result respectively in a first intermediate result vector and a second intermediate result vector. The first and second intermediate result vectors are associated respectively with a first set of object units and second set of object units of the digital objects. The result vector is a result of a combination of the first and second intermediate result vectors. The combination may, for example, be an intersection or union operation. The method further comprises: selecting intermediate result vectors of the first subset, identifying a first set of intermediate result entities as entities which are part of the retrieved object units and part of entities represented by nodes of said selected intermediate result vectors of the first intermediate result vector, selecting intermediate result vectors of the second subset, identifying a second set of intermediate result entities as entities which are part of the retrieved object units and part of entities represented by nodes of said selected intermediate result vectors of the second subset, wherein the set of result entities is a combination of the two sets of intermediate result entities.

According to certain embodiments, the method of the last embodiment is performed in response to determining that the first and second sets of documents units comprise the result set of object units.

According to certain embodiments, the result vector is a result of an operation on one intermediate result vector associated with respective set of object units of the digital objects. The method further comprises: selecting intermediate result vectors that precede the one intermediate result vector, identifying a set of intermediate result entities as entities which are part of the retrieved object units and part of entities represented by nodes of said selected intermediate result vectors, wherein the set of result entities is the set of intermediate result entities.

According to certain embodiments, the result vector comprises nodes representing the result set of object units.

According to certain embodiments, the method further comprises upon receiving the search request, selecting one of predefined search workflows, wherein the determined set of operations are operations of the selected search workflow.

According to certain embodiments, the set of operations comprises a node retrieval operation and at least one traversal operation, wherein the node retrieval operation receives the search request as input and provides an initial vector of nodes that fulfils the search request, wherein the traversal operation provides a result vector of nodes that fulfil a traversal condition and are reachable after one step traversal starting from an input vector, wherein the input vector is the initial vector of nodes in case the node retrieval operation is the operation immediately preceding the traversal operation, otherwise the input vector is an intermediate result vector of another immediately preceding operation.

According to certain embodiments, the set of operations further comprises logical operations and transformation operations.

According to certain embodiments, providing the set of result entities and the one or more object units comprises displaying the units and highlighting the set of result entities.

According to certain embodiments, the object unit is any one of: a paragraph, section, chapter, a sequence of video frames, an image portion.

According to certain embodiments, the entity is a word or combination of words of a digital object, or an object such as a person or car identified in an image or video.

FIG.1is a block diagram of an information retrieval system100in accordance with certain embodiments. The information retrieval system100may comprise a graph assembly system101and a server106. The information retrieval system100may further comprise a first storage device104and a second storage device103. The first storage device104may, for example, be a memory device. The second storage device may be a persistent storage device. The graph assembly system101may be configured to assemble or build a graph105that represents content of digital objects110such as electronic documents and/or videos and/or images. The graph105may be a knowledge graph (KG). The graph105may be stored in the second storage device103in association with object units and identifiers of the entities of the object units e.g., paragraphs. As indicated inFIG.1, the graph105may be loaded into the first storage device104for enabling an efficient search in the graph105. The graph105may thus be provided as an in-memory graph. The server106may be configured to perform searches in the in-memory graph105according to workflows112. Each of the workflows112may comprise a set of operations whose intermediate results111are stored by the server106. Alternatively, or additionally, the intermediate results111may advantageously be stored in the first storage device104. The result of a workflow may be a set of nodes of the graph105, wherein each node of the set of nodes may represent an object unit e.g., paragraph, that is stored in the second storage device103. Thus, for providing the result of the search, details of the result may be fetched (113) from the second storage device103. For example, object units represented by the set of nodes may be fetched. In addition, entities of the fetched object units may be marked. The marked entities may be determined according to the present embodiments. The result of the workflow112including the fetched object units may be displayed on a user interface108. In addition, the displayed object units show the marked entities. The user interface108may be a user interface of the server106or may be an interface of another server (UI server) that is not part of the server106. The server106may be configured to use the UI server to display the result of the search request. The UI server may enable a user120to access the content of the user interface108via a browser121.

FIG.2is a flowchart of a method for searching a graph representing content of digital objects in accordance with certain embodiments. For the purpose of explanation, the method described inFIG.2may be implemented in the information retrieval system100illustrated inFIG.1, but it is not limited to this implementation. The method ofFIG.2may, for example, be performed by the server106. In another example, the method ofFIG.2may be performed by the server106and the UI server.

A search request may be received in operation201. The search request may be received from a user. The search request may, for example, be received via a user interface of the server106. The search request may require the access to (e.g., by displaying) digital objects or object units that satisfy the search request. The search request may indicate the domain of interest of the user. The domain may represent concepts or categories which belong to a part of the world, such as biology or politics. The domain typically models domain-specific definitions of terms. For example, a domain can refer to healthcare, advertising, commerce, medical, chemical, physical, computer science, oil-and-gas, transportation, financial and/or biomedical-specific field. The domain of interest of the user may be one of the domains covered by the digital objects110. Having a request that has one of the domains covered by the digital objects may be advantageous as it may enable to obtain accurate results of the search request.

In a first request example, the search request may comprise search terms of the user that would satisfy the information needs of the user. For example, the search request may comprise the search terms “vaccine for coronavirus.” The server106may, for example, perform a lexical search by looking for literal matches of the search terms or variant of them. The server106may, in another example, perform a semantic search based on an understanding of the overall meaning of the search request.

In a second request example, graph queries may be defined in a declarative format named workflow. For that, the user may indicate an existing workflow by providing a workflow identifier or may build a new workflow. The existing workflows may, for example, be predefined based on customer requests. Following the above example, the workflow may be adapted to perform a search for the terms “vaccine for coronavirus.” The workflow may, for example, be built by representing as a directed acyclic graph (DAG) of operations. The nodes of DAG may represent specific graph operations which mutate an input (or intermediate) set of nodes into another set. The user may, for example, be provided with different types of nodes (i.e., different types of operations) and different types of edges such that the user can build a DAG of operations that would satisfy the search request. This second query example may be advantageous as it may avoid imposing a complex query language onto the user. In one example, the workflow may further be configured to prompt the user for further inputs while the set of operations being executed. Those inputs may enable to refine the search.

A set of operations may be determined in operation203for traversing the graph according to the search request, wherein each operation of the set of operations receives an input and provides, as output, a vector of nodes. The input may, for example, be a vector of nodes or initial search terms of the user.

Following the first request example, the set of operations may, automatically, be determined by the server106based, for example, on the meaning of the search request. The server may, in another example, determine variants of the search terms and search for literal matches of the search terms and the variants. Following the second request example, the determined set of operations may be the operations of the workflow that is built by the user or the workflow that is selected by the user from the predefined workflows.

In one first workflow example, the set of operations may comprise one result operation. In this case, the set of operations OP1, OP2. . . OPN, where N≥2 may be provided as one sequence of operations OP1, OP2. . . OPN. The operation OPNmay be the result operation or final operation of the sequence of operations. The other operations OP1, OP2. . . OPN-1may be intermediate operations. In a base case, N=2 because the set of operations may comprise an operation OP1for performing a search with user input (e.g., a regex search) followed by an operation OP2which may be an edge traversal to nodes that represent object units. In another example, the set of operations OP1, OP2. . . OPNmay be provided as multiple subsets of operations whose results are provided as input to a final operation of the set of operations in order to obtain the final or overall result of the set of operations. For example, the set operations may comprise one sequence of operations OP1, OP3. . . OPN-1and another sequence of operations OP2, OP4. . . OPN-2, wherein the result vectors of the operations OPN-1and OPN-2are provided as input to the result operation OPN. For example, in case the user requests information about vaccine for coronavirus, the set of operations may comprise one sequence of operations that enable a search in a science domain represented by scientific papers e.g., the set operations may comprise one node retrieval operation OP1to obtain from the graph105first nodes that match the “coronavirus” search term, a filter operation OP2that filters the first nodes that are, for example, linked with an edge category “vaccines” to obtain second nodes that represent “vaccines” and a result operation OP3which is a traversal operation that traverses the graph (starting from the second nodes) to identify nodes that represent relevant paragraphs of the scientific papers.

In one second workflow example, the set of operations may comprise more than one result operation. For example, the set of operations may comprise multiple independent sequences of operations e.g., one sequence of N1 operations OP11, OP21. . . OPN11, where N1≥2 and another sequence of N2 operations OP12, OP22. . . OPN22, N2≥2. This may, for example, enable to perform alternative searches for the same search terms. In another example, the two sequences of operations may have one or more common operations. For example, in case the user requests information about “vaccine for coronavirus,” the set of operations may comprise two sequences of operations, wherein the first sequence of operations may enable a search of “vaccines” associated with “coronavirus” in the graph and the second sequence of operations may enable to search for another variant such as “prevention methods for coronavirus.” In this case, the first operation of the two sequences may be the same node retrieval operation that would obtain all nodes related to “coronavirus,” and the remaining operations may be different e.g., the second operation of the first sequence may be a filter operation for filtering nodes that represent “vaccines” while the second operation of the second sequence may be a filter operation for filtering nodes that represent “prevention methods.” In an alternative example of two result operations, the two sequences of operations may be completely independent using different data sources and different levels of details of the search, wherein the first sequence of operations may enable a search in a science domain represented by scientific papers etc. and the second sequence of operations may enable to search newspapers and videos for general information such as statistics about vaccines of “coronavirus.”

The set of operations may be executed in operation205. This may result in intermediate result vectors of nodes and at least one result vector of nodes. The at least one result vector of nodes is associated with a result set of one or more object units of the digital objects. In case the set of operations comprises multiple sequences of operations, the execution of the set of operations may result in multiple result vectors of nodes respectively. The nodes of the multiple result vectors may represent the result set of object units.

Following the first workflow example, intermediate operations OP1, OP2. . . , OPN-1may result in intermediate result vectors respectively, while the result operation OPNmay result in a result vector. Following the “coronavirus” example, the set of operations may result in a result set of object units such as paragraphs of scientific articles. The result vector of the set of operations may comprise nodes that represent these paragraphs. The intermediate result vector of the filtering operation may comprise nodes that, for example, represent instances of the entity vaccine and other entities related to “vaccines” such as entities representing “doses” etc.

Following the second workflow example, intermediate operations OP11, OP21. . . OPN1-11may result in intermediate result vectors respectively, intermediate operations OP12, OP22. . . OP2-12may result in intermediate result vectors respectively while the result operations OPN11and OPN22may result in two result vectors respectively. Following the “coronavirus” example, the two sequences of operations may result in object units such as paragraphs of scientific articles, sequences of videoframes and passages of newspapers. The two result vectors of the two sequences of operations may comprise nodes that represent these paragraphs, sequences of videoframes and passages.

The result set of object units of the digital objects may be retrieved or fetched in operation207e.g., from the second storage device103. For example, all paragraphs and video frames that have been found relevant for the “coronavirus” search term may be retrieved from their persistent storage. Alternatively, the user may select among the result set of object units the desired object units. In this case, only those selected object units may be retrieved from the persistent storage. However, those retrieved object units may comprise a huge amount of text of information that the user may not all need. For example, paragraphs may include texts about viruses in general that may not be relevant for the user. To solve this, operations209to213may be performed.

Intermediate result vectors of the intermediate result vectors may be selected in operation209. This selection may, for example, be performed based on the type of operations that are involved in the set of operations. The selection of the intermediate result vectors may be performed by selecting the associated intermediate result operations. That is, the selection of the intermediate operations implicitly involves the selection of the intermediate result vectors that resulted from said selected intermediate operations. This selection may enable to identify parts of the object units (e.g., document units) that may be relevant for the user.

Following the first workflow example, the selected intermediate result vector may be a result vector of any one of the intermediate operations intermediate operations OP1, OP2. . . , OPN-1. In another example, the selected intermediate result vector may be a result vector of the intermediate operation OPN-1that precedes the result operation OPN. Following the example of “vaccines for coronavirus” search term, the user may only be interested in the intermediate result vector of the filter operation that filters nodes that represent “vaccines” related nodes.

A set of result entities may be identified in operation211. The set of result entities may be entities which are part of the retrieved object units and part of entities represented by nodes of said selected intermediate result vectors. For example, the identifiers of entities present in the retrieved objects units may be compared with identifiers of entities represented by nodes of the selected intermediate result vectors. This comparison may comprise performing an intersection between the compared identifiers to find the identifiers that are common between the retrieved object units and the selected intermediate result vectors. Following the “coronavirus” example, and if the intermediate result vector of the filtering operation is selected, the identifiers of the entities representing vaccines may be compared with identifiers of entities present in the result set of object units.

The set of result entities of the result set of object units and the result set of object units may be provided in operation213because of the search request. Following the “coronavirus” example, the paragraphs of the scientific papers may be displayed, wherein the set of result entities such as “vaccines” etc. are highlighted.

FIG.3is a flowchart of a method for identifying a set of result entities in accordance with certain embodiments. For the purpose of explanation, the method described inFIG.3may be implemented in the system illustrated inFIG.1, but it is not limited to this implementation. The method ofFIG.3may, for example, be performed by the server106. The method ofFIG.3provides an example implementation of operations209to213, in case the set of operations comprises two subsets of operations e.g., in accordance with the first workflow example, OP1, OP3. . . OPN-1and OP2, OP4. . . OPN-2, wherein the result operation OPNreceives as input the intermediate result vectors of the intermediate operations OPN-1and OPN-2. In this example, the intermediate operations OPN-1and OPN-2may result in intermediate result vectors which comprise nodes that represent object units e.g., they represent paragraphs or frames stored in the second storage device103.

Intermediate result vectors (excluding the intermediate result vector of operation OPN-1) of the first subset of operations OP1, OP3. . . OPN-1may be selected in operation301. A first set of intermediate result entities may be identified in operation303. The first set of intermediate result entities may be entities which are part of the retrieved object units (which are the result of result operation OPN) and part of entities represented by nodes of said selected intermediate result vectors of the first subset.

Intermediate result vectors (excluding the intermediate result vector of operation OPN-2) of the second subset of operations OP2, OP4. . . OPN-2may be selected in operation305. A second set of intermediate result entities may be identified in operation307. The second set of intermediate result entities may be entities which are part of the retrieved object units (which are the result of result operation OPN) and part of entities represented by nodes of said selected intermediate result vectors of the second subset.

The set of result entities identified in operation211may be obtained in operation309as a combination of the two sets of intermediate result entities. The combination may, for example, be an intersection or union operation between the identifiers of the two sets of intermediate result entities. Although described as second last operations, the intersections may in another example occur in any position within the workflow (e.g., in the middle of the workflow).

FIG.4is a flowchart of a method for identifying a set of result entities in accordance with certain embodiments. For the purpose of explanation, the method described inFIG.4may be implemented in the system illustrated inFIG.1, but is not limited to this implementation. The method ofFIG.4may, for example, be performed by the server106. The method of FIG.4provides an example implementation of operations209to213, in case the set of operations comprises one sequence of operations e.g., in accordance with the first workflow example, OP1, OP2. . . OPN, wherein the intermediate operation OPN-1provides an intermediate result vector that comprises nodes representing object units e.g., they represent paragraphs or frames stored in the second storage device103.

Intermediate result vectors (excluding the intermediate result vector of operation OPN-1) of the set of operations OP1, OP2. . . OPNmay be selected in operation401. A set of intermediate result entities may be identified in operation403. The set of intermediate result entities may be entities which are part of the retrieved object units (which are the result of result operation OPN) and part of entities represented by nodes of said selected intermediate result vectors. The set of result entities identified of operation211may be provided in operation405as the set of intermediate result entities identified in operation403.

FIG.5Ais a flowchart of a method for searching a graph representing content of electronic documents in accordance with certain embodiments. The graph may, for example, be built based on the ontology defined inFIG.5B.FIG.5Bshows an example of an ontology510descriptive of relations between companies. The ontology510includes concepts and roles. The concepts and roles can be expressed in various ways.FIG.5Billustrates the concepts and roles in a graph form. For the purpose of explanation, the method described inFIG.5Amay be implemented in the system illustrated inFIG.1, but it is not limited to this implementation. The method ofFIG.5Amay, for example, be performed by the server106.

The graph may be assembled or built, in operation501. The ontology510may be used to create the graph. For that, data about companies may be collected. The collected data may comprise, for example, existing electronic documents. With this collected data, as well as the ontology510, specific instances of the terms of the ontology510may be created and values of the properties of the terms may be determined, resulting in the graph. For example, entities such as company names, their business area, and paragraphs present in the electronic documents may be identified to build the graph accordingly. The graph may comprise nodes representing entities and edges representing relationships between the entities.FIG.5Cshows an example paragraph520that is represented by a node in the graph. Example entities present in the paragraph520are stored in a JSON file530shown inFIG.5D. The JSON file530, lists the entities and associated identifiers. For example, the entity “ABC” is associated with the identifier 12345abc.

A search request may be received in operation503. As indicated inFIG.5E, the search request may, for example, specify user inputs “IBM” and “Hybrid cloud” and a workflow540of operations. The workflow540comprises a set of operations OP1, OP2OP9. The set of operations comprises a first subset of operations OP1, OP2and OP3and an independent second subset of operations OP4, OP5and OP6. The set of operations comprises a result operation OP9. Each of the intermediate operations OP1, OP2. . . OP8provides, when executed, a respective intermediate result vector D1, D2. . . D8. The intermediate result vectors D3and D6may be provided as input to the intermediate operation OP7that performs an intersection of the intermediate result vectors D3and D6to obtain the intermediate result vector D7. The result operation OP9provides, when executed, a result vector D9. The result vector comprises nodes such as instances of the node named “Paragraph” in the graph. Assuming for simplification of the description, that the result vector D9comprises one node that represents the paragraph520ofFIG.5C.

The set of operations OP1, OP2. . . OP9may be executed in operation505. This may result in nine vectors D1, D2. . . and D9. The paragraph520may be retrieved in operation506from the second storage device103.

One or more intermediate result vectors may be selected in operation507from the intermediate result vectors D1, D2. . . D8. Assuming for simplification of the description that the intermediate result vectors D7and D8have been selected in operation507.

The set of result entities may be identified in operation509. This is illustrated inFIG.5F, where the identifiers of the JSON file530associated with the paragraph520are compared with the identifiers of the selected intermediate result vector D7. The same comparison may be performed between the identifiers of the JSON file530and the identifiers of the selected result vector D8. The set of result entities may be entities which are present in both the JSON file and in the entities of the intermediate result vector D7or D8.

The result paragraph520may be displayed in operation511, wherein the identified set of result entities are marked in the paragraph. This is indicated with the displayed paragraph550ofFIG.5G, where the highlighted entity “ABC” represents an entity of D7or D8. The marking further indicates result entities from D8. The set of result entities of D8may represent an acquisition event defined by 4 components, Acquisition term “acquired”, Year 2018, Buyer “ABC”, Bought “CompanyX”.

FIG.6Ais a flowchart of a method for determining a workflow in accordance with certain embodiments. For the purpose of explanation, the method described inFIG.6Amay be implemented in the information retrieval system100illustrated inFIG.1, but is not limited to this implementation. The method ofFIG.6Amay, for example, be performed by the server106. The method ofFIG.6Amay be performed a priori for preparing workflows among which the user may select one that suits his or her search. In another example, the method ofFIG.6Amay be performed by the user as part of defining or determining his or her search request.

Elements of workflows as shown inFIG.6Bmay be provided in operation601. For example, the workflow elements may be provided as user interface elements that may be displayed on the user interface108. As shown inFIG.6B, the elements of the workflows comprise elements that represent different types of operations. The elements of the workflows further comprise elements representing different types of result nodes. For example, a result vector may provide nodes that represent paragraphs or entities or other nodes, wherein the other nodes may represent entities which are not part of the digital objects being processed but may represent a data catalogue.

The user may for example build a workflow such as the workflow540ofFIG.5Eusing the elements ofFIG.6B. The built workflow may be received as a search request in operation603.FIG.6Cprovides an example workflow. The workflow620ofFIG.6Ccomprises a set of operations OP1, OP2and OP3. The first intermediate operation OP1may be a node retrieval operation that determines the nodes D1of the graph that satisfy a user search request. The second intermediate operation OP2may be a filter operation that selects nodes D2that belong to a certain category e.g., software category. The result operation OP3may receive as input the intermediate result vector D2and provide a result vector D3that comprise nodes representing paragraphs of electronic documents. The paragraphs may be the result of the user search. In addition, the intermediate result vector D2may be selected so that entities which are present in the paragraphs and in D2may be highlighted or marked when the paragraphs are displayed to the user.

FIG.7represents a general computerized system700suited for implementing at least part of method operations as involved in the disclosure.

It will be appreciated that the methods described herein are at least partly non-interactive, and automated by way of computerized systems, such as servers or embedded systems. In exemplary embodiments though, the methods described herein can be implemented in a (partly) interactive system. These methods can further be implemented in software712(including firmware722), hardware (processor)705, or a combination thereof. In exemplary embodiments, the methods described herein are implemented in software, as an executable program, and are executed by a special or general-purpose digital computer, such as a personal computer, workstation, minicomputer, or mainframe computer. The most general system700therefore includes a general-purpose computer701.

In exemplary embodiments, in terms of hardware architecture, as shown inFIG.7, the computer701includes a processor705, memory (main memory)710coupled to a memory controller715, and one or more input and/or output (I/O) devices (or peripherals)10,745that are communicatively coupled via a local input/output controller735. The input/output controller735can be, but is not limited to, one or more buses or other wired or wireless connections, as is known in the art. The input/output controller735may have additional elements, which are omitted for simplicity, such as controllers, buffers (caches), drivers, repeaters, and receivers, to enable communications. Further, the local interface may include address, control, and/or data connections to enable appropriate communications among the aforementioned components. As described herein the I/O devices10,745may generally include any generalized cryptographic card or smart card known in the art.

The processor705is a hardware device for executing software, particularly that stored in memory710. The processor705can be any custom made or commercially available processor, a central processing unit (CPU), an auxiliary processor among several processors associated with the computer701, a semiconductor-based microprocessor (in the form of a microchip or chip set), or generally any device for executing software instructions.

The memory710can include any one or combination of volatile memory elements (e.g., random access memory (RAM, such as DRAM, SRAM, SDRAM, etc.)) and nonvolatile memory elements (e.g., ROM, erasable programmable read only memory (EPROM), electronically erasable programmable read only memory (EEPROM), programmable read only memory (PROM). Note that the memory710can have a distributed architecture, where various components are situated remote from one another, but can be accessed by the processor705.

The software in memory710may include one or more separate programs, each of which comprises an ordered listing of executable instructions for implementing logical functions, notably functions involved in certain embodiments. In the example ofFIG.7, software in the memory710includes instructions or software712e.g., instructions to manage databases such as a database management system.

The software in memory710shall also typically include a suitable operating system (OS)711. The OS711essentially controls the execution of other computer programs, such as possibly software712for implementing methods as described herein.

The methods described herein may be in the form of a source program, executable program, or software712(object code), script, or any other entity comprising a set of instructions to be performed. When a source program, then the program needs to be translated via a compiler, assembler, interpreter, or the like, which may or may not be included within the memory710, so as to operate properly in connection with the OS711. Furthermore, the methods can be written as an object-oriented programming language, which has classes of data and methods, or a procedure programming language, which has routines, subroutines, and/or functions.

In exemplary embodiments, a conventional keyboard750and mouse755can be coupled to the input/output controller735. Other output devices such as the I/O devices745may include input devices, for example but not limited to a printer, a scanner, microphone, and the like. Finally, the I/O devices10,745may further include devices that communicate both inputs and outputs, for instance but not limited to, a network interface card (NIC) or modulator/demodulator (for accessing other files, devices, systems, or a network), a radio frequency (RF) or other transceiver, a telephonic interface, a bridge, a router, and the like. The I/O devices10,745can be any generalized cryptographic card or smart card known in the art. The system700can further include a display controller725coupled to a display730. In exemplary embodiments, the system700can further include a network interface for coupling to a network765. The network765can be an IP-based network for communication between the computer701and any external server, client and the like via a broadband connection. The network765transmits and receives data between the computer701and external systems30, which can be involved to perform part, or all of the steps/operations of the methods discussed herein. In exemplary embodiments, network765can be a managed IP network administered by a service provider. The network765may be implemented in a wireless fashion, e.g., using wireless protocols and technologies, such as WiFi, WiMax, etc. The network765can also be a packet-switched network such as a local area network, wide area network, metropolitan area network, Internet network, or other similar type of network environment. The network765may be a fixed wireless network, a wireless local area network W(LAN), a wireless wide area network (WWAN) a personal area network (PAN), a virtual private network (VPN), intranet or other suitable network system and includes equipment for receiving and transmitting signals.

If the computer701is a PC, workstation, intelligent device or the like, the software in the memory710may further include a basic input output system (BIOS)722. The BIOS is a set of essential software routines that initialize and test hardware at startup, start the OS711, and support the transfer of data among the hardware devices. The BIOS is stored in ROM so that the BIOS can be executed when the computer701is activated.

When the computer701is in operation, the processor705is configured to execute software712stored within the memory710, to communicate data to and from the memory710, and to generally control operations of the computer701pursuant to the software. The methods described herein and the OS711, in whole or in part, but typically the latter, are read by the processor705, possibly buffered within the processor705, and then executed.

When the systems and methods described herein are implemented in software712, as is shown inFIG.7, the methods can be stored on any computer readable medium, such as storage720, for use by or in connection with any computer related system or method. The storage720may comprise a disk storage such as HDD storage.

The present subject matter may comprise the following clauses.

Clause 1. A computer-implemented method for searching a graph representing content of digital objects, the graph comprising nodes representing entities and edges representing relationships between the entities, the entities being descriptive of the content of the digital objects, the method comprising: receiving a search request; determining a set of operations for traversing the graph according to the search request, wherein each operation of the set of operations receives an input and provides, as output, a vector of nodes; executing the set of operations, resulting in intermediate result vectors of nodes and a result vector of nodes, the result vector of nodes being associated with a result set of one or more object units of the digital objects; retrieving the result set of object units of the digital objects; selecting intermediate result vectors of the intermediate result vectors; identifying a set of result entities as entities which are part of the retrieved object units and part of entities represented by nodes of said selected intermediate result vectors; providing the set of result entities of the result set of object units and the result set of object units as a result of the search request.

Clause 2. The method of clause 1, the digital objects comprising at least one of: electronic documents, video files and images.

Clause 3. The method of any of the preceding clauses 1 to 2, wherein the graph is stored in a first storage device and the digital objects are stored in a second storage device, wherein the first storage device has higher data access performance than the second storage device.

Clause 4. The method of any of the preceding clauses 1 to 3, further comprising selecting the intermediate result vectors based on a selection criterion requiring any one of: a selection based on the type of operations that precedes a result operation that provides the result vector; a random selection of a subset of intermediate result vectors; a selection of intermediate result vectors of operations succeeding an initial operation of the set of operations; a selection of an intermediate result vector of an operation immediately preceding the operation that resulted in the result vector; a user selection of intermediate result vectors.

Clause 5. The method of any of the preceding clauses 1 to 4, wherein the selected intermediate result vectors are all intermediate result vectors.

Clause 6. The method of any of the preceding clauses 1 to 5, wherein the set of operations comprises at least two distinct subsets of operations comprising a first subset of operations and a second subset of operations, wherein the execution of the first and second subsets of operations result respectively in a first intermediate result vector and a second intermediate result vector, the first and second intermediate result vectors being associated respectively with a first set of object units and second set of object units of the digital objects; wherein the result vector is a result of a combination of the first and second intermediate result vectors; the method further comprising: selecting intermediate result vectors of the first subset; identifying a first set of intermediate result entities as entities which are part of the retrieved object units and part of entities represented by nodes of said selected intermediate result vectors of the first subset; selecting intermediate result vectors of the second subset; identifying a second set of intermediate result entities as entities which are part of the retrieved object units and part of entities represented by nodes of said selected intermediate result vectors of the second subset; wherein the set of result entities is a combination of the two sets of intermediate result entities.

Clause 7. The method of clause 6, being performed in response to determining that the first and second sets of objects units comprise the result set of object units.

Clause 8. The method of any of the preceding clauses 1 to 7, wherein the result vector is a result of an operation on one intermediate result vector associated with respective set of object units of the digital objects, the method further comprising: selecting intermediate result vectors that precedes the one intermediate result vector; identifying a set of intermediate result entities as entities which are part of the retrieved object units and part of entities represented by nodes of said selected intermediate result vectors; wherein the set of result entities is the set of intermediate result entities.

Clause 9. The method of any of the preceding clauses 1 to 8, wherein the result vector comprises: nodes representing the result set of object units.

Clause 10. The method of any of the preceding clauses 1 to 9, further comprising: associating each node of the graph with an identifier for identifying the entity represented by said each node; wherein the identifying of the set of result entities comprises: comparing the identifiers of entities of the object units with the identifiers of nodes of the selected intermediate result vectors; wherein the set of result entities are the matching entities.

Clause 11. The method of any of the preceding clauses 1 to 10, further comprising upon receiving the search request, selecting one of predefined search workflows, wherein the determined set of operations are operations of the selected search workflow.

Clause 12. The method of any of the preceding clauses 1 to 11, wherein the set of operations comprises a node retrieval operation and at least one traversal operation, wherein the node retrieval operation receives the search request as input and provides an initial vector of nodes that fulfils the search request, wherein the traversal operation provides a result vector of nodes that fulfil a traversal condition and are reachable after one step traversal starting from an input vector, wherein the input vector is the initial vector of nodes in case the node retrieval operation is the operation immediately preceding the traversal operation, otherwise the input vector is an intermediate result vector of another immediately preceding operation.

Clause 13. The method of clause 12, the set of operations further comprising logical operations and transformation operations.

Clause 14. The method of any of the preceding clauses 1 to 13, wherein providing the set of result entities and the one or more object units comprises displaying the object units and highlighting the set of result entities.

Clause 15. The method of any of the preceding clauses 1 to 14, the object unit being any one of: a paragraph, section or chapter, a sequence of video frame, image portion.

Clause 16. The method of any of the preceding clauses 1 to 15, wherein the entity is a word or combination of words of a digital object or an object that can be represented in an image or video.

Characteristics are as follows:

Service Models are as follows:

Deployment Models are as follows:

Referring now toFIG.8, illustrative cloud computing environment1050is depicted. As shown, cloud computing environment1050includes one or more cloud computing nodes1010with which local computing devices used by cloud consumers, such as, for example, personal digital assistant (PDA) or cellular telephone1054A, desktop computer1054B, laptop computer1054C, and/or automobile computer system54N may communicate. Nodes1010may communicate with one another. They may be grouped (not shown) physically or virtually, in one or more networks, such as Private, Community, Public, or Hybrid clouds as described hereinabove, or a combination thereof. This allows cloud computing environment1050to offer infrastructure, platforms and/or software as services for which a cloud consumer does not need to maintain resources on a local computing device. It is understood that the types of computing devices1054A-N shown inFIG.8are intended to be illustrative only and that computing nodes1010and cloud computing environment1050can communicate with any type of computerized device over any type of network and/or network addressable connection (e.g., using a web browser).

Referring now toFIG.9, a set of functional abstraction layers provided by cloud computing environment1050(FIG.8) is shown. It should be understood in advance that the components, layers, and functions shown inFIG.9are intended to be illustrative only and embodiments are not limited thereto. As depicted, the following layers and corresponding functions are provided:

Hardware and software layer1060includes hardware and software components. Examples of hardware components include: mainframes1061; RISC (Reduced Instruction Set Computer) architecture based servers1062; servers1063; blade servers1064; storage devices1065; and networks and networking components1066. In some embodiments, software components include network application server software1067and database software1068.

Virtualization layer1070provides an abstraction layer from which the following examples of virtual entities may be provided: virtual servers1071; virtual storage1072; virtual networks1073, including virtual private networks; virtual applications and operating systems1074; and virtual clients1075.

Workloads layer1090provides examples of functionality for which the cloud computing environment may be utilized. Examples of workloads and functions which may be provided from this layer include: mapping and navigation1091; software development and lifecycle management1092; virtual classroom education delivery1093; data analytics processing1094; transaction processing1095; and searching knowledge graphs (SKG)1096in accordance with the present subject matter e.g., as described with reference toFIG.2,3,4,5A or6A.

The descriptions of the various embodiments of the present disclosure have been presented for purposes of illustration and are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. In particular, a feature (device-like or method-like) recited in a given embodiment, variant or shown in a drawing may be combined with or replace another feature in another embodiment, variant or drawing, without departing from the scope of the present disclosure. Various combinations of the features described in respect of any of the above embodiments or variants may accordingly be contemplated, that remain within the scope of the appended claims. In addition, many minor modifications may be made to adapt a particular situation or material to the teachings of the present disclosure without departing from its scope. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.