KR102796540B1 - Method and apparatus for matching sub graph - Google Patents

Abstract

A subgraph matching method and device are disclosed. According to one embodiment of the disclosure, the subgraph matching device includes a serialization module that obtains a plurality of graph data and generates a single data stream by combining the obtained plurality of graph data, a graph restoration module that converts the data stream into a graph stream, and a matching module that searches for a graph pattern matching a preset subgraph query for the graph stream.

Description

METHOD AND APPARATUS FOR MATCHING SUB GRAPH

An embodiment of the present invention relates to a subgraph matching technique.

A graph is a way to express data relationships, and the relationships between each object in the graph structure are expressed as edges. Here, subgraph matching is one of the graph mining tasks that finds graph patterns that match a query subgraph in a large graph.

Recently, graph models such as RDF (Resource Description Framework) have been used to represent and exchange data on the Semantic Web, and the size of RDF graph data is increasing exponentially. Therefore, it is essential to develop efficient storage and query mechanisms for large-scale RDF graph data.

These development tasks include not only information changes but also immediate updates of the results of graph mining tasks. However, it is inefficient to re-perform graph mining tasks (e.g., subgraph matching, etc.) every time there is a change in the original graph data.

Publication of Patent Publication No. 10-2020-0002027 (2020.01.07)

An embodiment of the present invention provides a subgraph matching method and device capable of improving work efficiency by retrieving results for subgraph queries only for newly changed data.

A sub-graph matching device according to one embodiment of the present disclosure includes a serialization module for obtaining a plurality of graph data and generating a single data stream by combining the obtained plurality of graph data; a graph restoration module for converting the data stream into a graph stream; and a matching module for searching a graph pattern matching a preset sub-graph query for the graph stream.

The above serialization module can extract edge information from each of the plurality of graph data and connect the extracted edge information in a row to create a single data stream.

The above serialization module divides the one data stream into batch sizes of preset units, and the graph restoration module can restore graph data for each time stamp for each data stream based on edge information of each divided data stream and convert it into a graph stream.

The above matching module can generate a stream graph table by tracking edge information that changes according to a change in a timestamp in the graph stream, and search for a graph pattern matching the subgraph query using the generated stream graph table.

The above stream graph table may include columns of edge label, added index, added edges, removed index, and removed edges, wherein the edge label may be a column storing a set of starting and arriving vertex labels of each edge of the graph, the added index may be a column storing an index of an edge added to the graph, the added edges may be a column storing a set of edges associated with each edge label, the removed index may be a column storing an index of an edge removed from the graph, and the removed edges may be a column storing a set of edges removed associated with each edge label.

The above matching module generates sequential edges information for the subgraph query, and the sequential edges information is information about the sequence of each edge included in the subgraph query, and the information for each edge can be composed of the ID of the starting vertex and the ID of the arrival vertex of the corresponding edge.

The above matching module can search for items matching the sequential edge information for the subgraph query in the edge label and added edges columns of the stream graph table.

The above matching module generates a subgraph matching result table for each time stamp of the graph stream according to the result of the search, and the subgraph matching result table may sequentially arrange the IDs of each vertex in a graph pattern matching the graph pattern of the subgraph query.

A subgraph matching method according to one embodiment of the present disclosure is a method performed in a computing device having one or more processors and a memory storing one or more programs executed by the one or more processors, the method including: obtaining a plurality of graph data; generating a single data stream by combining the obtained plurality of graph data; converting the data stream into a graph stream; and searching for a graph pattern matching a preset subgraph query for the graph stream.

The step of generating the above one data stream may include the step of extracting edge information from each of the plurality of graph data; and the step of connecting the extracted edge information in a row to generate the one data stream.

The above subgraph matching method further includes a step of dividing the one data stream into batch sizes of preset units, and the step of converting into a graph stream may be performed by restoring graph data for each time stamp for each data stream based on edge information of each of the divided data streams and converting the data into a graph stream.

The above-described searching step may include a step of generating a stream graph table by tracing edge information that changes according to a change in a timestamp in the graph stream; and a step of searching for a graph pattern matching the sub-graph query using the generated stream graph table.

The above stream graph table may include columns of edge label, added index, added edges, removed index, and removed edges, wherein the edge label may be a column storing a set of starting and arriving vertex labels of each edge of the graph, the added index may be a column storing an index of an edge added to the graph, the added edges may be a column storing a set of edges associated with each edge label, the removed index may be a column storing an index of an edge removed from the graph, and the removed edges may be a column storing a set of edges removed associated with each edge label.

The above searching step further includes a step of generating sequential edges information for the subgraph query, wherein the sequential edges information is information about the sequence of each edge included in the subgraph query, and the information for each edge may be composed of an ID of a starting vertex and an ID of a destination vertex of the corresponding edge.

The above searching step can search for items matching the sequential edge information for the subgraph query in the edge label and added edges columns of the stream graph table.

The above searching step may further include a step of generating a subgraph matching result table for each time stamp of the graph stream according to a result of the search, and the subgraph matching result table may be a table in which the IDs of each vertex are sequentially arranged in a graph pattern matching the graph pattern of the subgraph query.

According to the disclosed embodiment, by generating a stream graph table for a graph stream and storing information about edges added or deleted whenever the graph is updated, only matching results for newly added or deleted edges need to be searched based on previous subgraph matching results for a subgraph query, thereby improving the efficiency of subgraph matching work while reducing the workload.

FIG. 1 is a diagram illustrating a graph stream in one embodiment disclosed.
FIG. 2 is a diagram illustrating a graph pattern matching process when a subgraph query is given in an embodiment disclosed herein.
FIG. 3 is a block diagram showing a subgraph matching device according to one embodiment of the present invention.
FIG. 4 is a diagram schematically illustrating a state in which a serialization module combines multiple graph data to generate one data stream in one embodiment of the present invention.
FIG. 5 is a diagram showing a stream graph table according to one embodiment of the present invention.
FIG. 6 is a diagram showing sequential edge information for a subgraph query (query q) in one embodiment of the present invention.
FIG. 7 is a diagram illustrating a process of searching edge information matching a subgraph query at time stamp t=0 in one embodiment of the present invention.
FIG. 8 is a diagram showing a stream graph table when a graph stream changes from time stamp t=0 to time stamp t=1 in one embodiment of the present invention.
FIG. 9 is a diagram illustrating a process of searching edge information matching a subgraph query at time stamp t=1 in one embodiment of the present invention.
FIG. 10 is a diagram showing a stream graph table when a graph stream changes from time stamp t=1 to time stamp t=2 in one embodiment of the present invention.
FIG. 11 is a diagram illustrating a process of searching edge information matching a subgraph query at time stamp t=2 in one embodiment of the present invention.
Figure 12 is a flow chart showing a subgraph matching method according to one embodiment of the present invention.
FIG. 13 is a block diagram illustrating a computing environment including a computing device suitable for use in exemplary embodiments.

Hereinafter, specific embodiments of the present invention will be described with reference to the drawings. The following detailed description is provided to help a comprehensive understanding of the methods, devices, and/or systems described herein. However, this is only an example and the present invention is not limited thereto.

In describing embodiments of the present invention, if it is judged that a detailed description of a known technology related to the present invention may unnecessarily obscure the gist of the present invention, the detailed description will be omitted. In addition, the terms described below are terms defined in consideration of their functions in the present invention, and may vary depending on the intention or custom of the user or operator. Therefore, the definitions should be made based on the contents throughout this specification. The terms used in the detailed description are only for describing embodiments of the present invention, and should never be limited. Unless clearly used otherwise, the singular form includes the plural form. In this description, expressions such as "comprises" or "comprising" are intended to indicate certain features, numbers, steps, operations, elements, parts or combinations thereof, and should not be construed to exclude the presence or possibility of one or more other features, numbers, steps, operations, elements, parts or combinations thereof other than those described.

Also, while the terms first, second, etc. may be used to describe various components, the components should not be limited by the terms. The terms may be used to distinguish one component from another. For example, without departing from the scope of the present invention, the first component may be referred to as the second component, and similarly, the second component may also be referred to as the first component.

A graph is represented as G = (V, E), where V represents a set of vertices (i.e., V={v1, v2, ??, vn}) and E represents a set of edges (i.e., E=(e1, e2, ??, en}). Each vertex can contain characteristics or information about the vertex, and similarly, each edge can contain information such as information about the edge and the relationship between vertices. In addition, a graph stream is a flow of graph events in which insertion and deletion of vertices and insertion and deletion of edges continuously occur over time.

FIG. 1 is a diagram illustrating a graph stream in an embodiment disclosed. Referring to FIG. 1, when changing from time t=0 to t=1, a vertex (A2) is added to the graph and an edge (A2, B1) is added accordingly, and when changing from time t=1 to t=2, an edge (C2, D1) is deleted from the graph. Meanwhile, these graph streams can be generated in different devices (e.g., cloud servers, SNS servers, etc.). In addition, each graph stream can be distributed and stored in multiple databases.

FIG. 2 is a diagram illustrating a graph pattern matching process when a subgraph query is given in one embodiment of the disclosure.

Referring to Fig. 2, when a subgraph query is given as in (b) of Fig. 2, the search result of a graph pattern matching the subgraph query at each time stamp (t=0, t=1, t=2) of the graph stream is shown. Here, the matching includes not only an exact match of the graph pattern but also an approximate match.

When the timestamp t=0, the number of graph patterns matching the subgraph query is 2. When the timestamp t=1, the number of graph patterns matching the subgraph query increases to 4 as a vertex (A2) and an edge (A2, B1) are added to the graph. When the timestamp t=2, the number of graph patterns matching the subgraph query decreases again to 2 as an edge (C2, D1) is deleted from the graph.

FIG. 3 is a block diagram illustrating a subgraph matching device according to one embodiment of the present invention.

Referring to FIG. 3, the subgraph matching device (100) may include a serialization module (102), a graph restoration module (104), and a matching module (106). In an exemplary embodiment, the subgraph matching device (100) may be configured to perform subgraph matching in a multi-graph stream environment, but is not limited thereto.

The serialization module (102) can obtain a plurality of graph data. Here, each graph data can be a graph expressed as G = (V, E). V is a set of vertices, and E is a set of edges.

In an exemplary embodiment, the serialization module (102) can receive multiple graph data in parallel from different source devices (e.g., a database or a cloud server, etc.). However, the manner in which the serialization module (102) obtains the multiple graph data is not limited thereto.

The serialization module (102) can combine multiple graph data to generate a single data stream. At this time, the serialization module (102) can extract edge information from each graph data and connect the extracted edge information in a row to generate a single data stream.

FIG. 4 is a diagram schematically illustrating a state in which a serialization module (102) combines multiple graph data to generate a single data stream in one embodiment of the present invention. Referring to FIG. 4, the serialization module (102) can obtain first graph data (G1), second graph data (G2), and third graph data (G3) from three different source devices, respectively.

The serialization module (102) can extract first edge information (e1-e2-e3) from the first graph data (G1), second edge information (e4-e5-e6) from the second graph data (G2), and third edge information (e4-e5-e6) from the third graph data (G3). In addition, the serialization module (102) can generate one data stream by connecting the first edge information, the second edge information, and the third edge information.

Here, each edge information also includes information on vertices associated with each edge due to its nature. That is, since one edge is composed of a pair of vertices, the edge information also includes information on vertices associated with the corresponding edge.

In the disclosed embodiment, since multiple graph data received in parallel through the serialization module (102) are combined to generate a single data stream, a synchronization problem for graph data received in parallel does not occur.

The serialization module (102) can divide one data stream into batch sizes of preset units. Here, the batch size can be determined according to the memory size of the subgraph matching device (100).

The graph restoration module (104) can convert each data stream (i.e., a data stream of a size corresponding to the batch size) divided by the serialization module (102) into a graph stream. That is, since each data stream divided by the serialization module (102) is in a form in which only edge information is connected, it can be restored into a graph stream having a graph structure.

The graph restoration module (104) can convert each data stream into a graph stream based on the edge information of each divided data stream. That is, since the edge information includes information on vertices associated with each edge due to its nature, the data stream can be converted into a graph stream based on the edge information and vertex information.

The graph restoration module (104) can restore graph data for each data stream at each time stamp and convert it into a graph stream. The converted graph stream can be updated as a graph stream that is the target of subgraph matching. The graph stream can include a corresponding graph for each time stamp.

The matching module (106) can search for a graph pattern matching a preset subgraph query for the graph stream converted by the graph restoration module (104).

The matching module (106) can track edge information that is changed (e.g., added or deleted) according to changes in the timestamp in the graph stream. At this time, a stream graph table can be used to track the edge information. The matching module (106) can output a new search result using the previous search result and the changed edge information.

Here, the stream graph table may be a table that stores information about edges of a graph that is updated whenever the graph changes. The stream graph table may be provided to indicate the location of edges that are added or deleted from the graph.

FIG. 5 is a diagram illustrating a stream graph table according to one embodiment of the present invention. Here, the stream graph table represents a table for a graph when t=0 in the graph stream illustrated in FIG. 1.

Referring to FIG. 5, the stream graph table can be composed of five columns: edge label, added index, added edges, removed index, and removed edges.

Edge label) can be a column that stores a set of starting and ending vertex labels of each edge of the graph. That is, the edge label can be composed of the label of the starting vertex and the label of the ending vertex of each edge. For example, if the edge label is AB, the edge becomes an edge that has the vertex with the label A as the starting vertex and the vertex with the label B as the ending vertex.

The added index can be a column that stores the index of the edge added to the graph. Here, if the value of the added index is -1, it can mean that the added edge was not updated (i.e., there is no added edge).

Added edges can be a column that stores a set of edges related to each edge label. At this time, the added edge can be composed of the ID of the starting vertex (a unique number of the vertex) and the ID of the destination vertex of the edge related to each edge label. For example, in the case of edge label AB, there is one edge related to AB, and the edge is expressed as (1, 2) as 1, which is the ID of the vertex with the label A, and 2, which is the ID of the vertex with the label B.

And, if the edge label is BC, there are two edges related to BC, and one of them is expressed as (2, 4), which is composed of 2, which is the ID of the vertex with the label B, and 4, which is the ID of the vertex with the label C. And, the other edge is expressed as (2, 5), which is composed of 2, which is the ID of the vertex with the label B, and 5, which is the ID of the vertex with the label C.

The removed index may be a column that stores the index of the edge removed from the graph. Here, if the value of the removed index is -1, it may mean that the removed edge was not updated (i.e., there is no removed edge).

Removed edges may be a column that stores a set of edges removed for each edge label. Removed edges may consist of the ID of the starting vertex and the ID of the destination vertex of the removed edge for each edge label.

Meanwhile, when a subgraph query is given, the matching module (106) can extract edge information matching the subgraph query based on the stream graph table for the graph stream.

Specifically, when a subgraph query (query q) is given, the matching module (106) can generate sequential edges information for the subgraph query. Here, the sequential edges information is information about the sequence of each edge included in the subgraph query, and each edge can be composed of the ID of the starting vertex and the ID of the destination vertex of the corresponding edge. FIG. 6 is a diagram illustrating sequential edges information for a subgraph query (query q) according to one embodiment of the present invention.

The matching module (106) can search for items matching the sequential edge information for the subgraph query (query q) in the edge label and added edges columns of the stream graph table. FIG. 7 is a diagram illustrating a process of searching for edge information matching the subgraph query at time stamp t=0 in one embodiment of the present invention.

Referring to FIG. 7, the matching module (106) can search for an edge matching edge (1, 2) among the sequential edge information for a subgraph query (query q) in the added edges column of the corresponding edge label AB. In addition, the matching module (106) can search for an edge matching edge (2, 3) among the sequential edge information in the added edges column of the corresponding edge label BB.

In this way, the matching module (106) can search for items matching the sequential edge information for the subgraph query (query q) and generate a subgraph matching result table at time stamp t=0. Here, the subgraph matching result table can be a table in which the IDs of each vertex are sequentially arranged in the graph pattern (P1, P2) matching the graph pattern of the subgraph query.

FIG. 8 is a diagram showing a stream graph table when a graph stream changes from a time stamp t=0 to a time stamp t=1 in one embodiment of the present invention. Referring to FIG. 8, at a time stamp t=1, an edge related to an edge label AB is added, and information about the edge, i.e., (7,2), can be added in the added edges column of the edge label AB.

FIG. 9 is a diagram illustrating a process of searching for edge information matching a subgraph query at time stamp t=1 according to one embodiment of the present invention. Referring to FIG. 9, since edge (7,2) is added to the added edges column of edge label AB at time stamp t=1, the matching module (106) synthesizes a subgraph matching result table for the edge (7,2) newly added to the subgraph matching result table at time stamp t=0 to generate a subgraph matching result table at time stamp t=1. Here, it can be seen that the number of graph patterns (P1, P2, P3, P4) matching the subgraph query has increased to four.

FIG. 10 is a diagram showing a stream graph table when a graph stream changes from time stamp t=1 to time stamp t=2 in one embodiment of the present invention, and FIG. 11 is a diagram showing a process of searching for edge information matching a subgraph query at time stamp t=2 in one embodiment of the present invention.

Referring to FIG. 10 and FIG. 11, an edge associated with edge label CD is removed at time stamp t=2, and information about the corresponding edge, i.e., (5, 6), can be added to the removed edges column of edge label CD.

And, the matching module (106) can delete the information part about the deleted edge in the subgraph matching result table at time stamp t=1 to generate the subgraph matching result table at time stamp t=2. Here, it can be seen that the number of graph patterns (P1, P3) matching the subgraph query is reduced to two again.

According to the disclosed embodiment, by generating a stream graph table for a graph stream and storing information about edges added or deleted whenever the graph is updated, only matching results for newly added or deleted edges are returned based on previous subgraph matching results for subgraph queries, thereby improving the efficiency of subgraph matching work while reducing the workload.

In this specification, the term "module" may mean a functional and structural combination of hardware for performing the technical idea of the present invention and software for operating the hardware. For example, the "module" may mean a logical unit of a given code and hardware resources for performing the given code, and does not necessarily mean physically connected code or a type of hardware.

Fig. 12 is a flowchart illustrating a subgraph matching method according to one embodiment of the present invention. In the illustrated flowchart, the method is described by dividing it into a plurality of steps, but at least some of the steps may be performed in a different order, combined with other steps and performed together, omitted, divided into detailed steps, or performed by adding one or more steps that are not illustrated.

Referring to Fig. 12, the subgraph matching device (100) can obtain multiple graph data in parallel (S 101). At this time, the multiple graph data can be obtained from different source devices.

Next, the subgraph matching device (100) can combine multiple graph data to generate one data stream (S 103). The subgraph matching device (100) can extract edge information from each graph data and connect the extracted edge information in a row to generate one data stream.

Next, the subgraph matching device (100) can divide one data stream into batch sizes of preset units (S 105).

Next, the subgraph matching device (100) can convert each divided data stream into a graph stream based on edge information of each divided data stream (S 107).

Next, the subgraph matching device (100) can generate a stream graph table by tracking edge information that changes according to changes in timestamps in the graph stream (S 109). The subgraph matching device (100) can update the stream graph table for each timestamp of the graph stream.

Next, the subgraph matching device (100) can generate sequential edges information for a preset subgraph query (S 111).

Next, the subgraph matching device (100) can search for items matching the sequential edge information for the subgraph query (query q) in the edge label and added edges columns of the stream graph table to generate a subgraph matching result table (S 113).

FIG. 13 is a block diagram illustrating a computing environment (10) including a computing device suitable for use in exemplary embodiments. In the illustrated embodiment, each component may have different functions and capabilities other than those described below, and may include additional components other than those described below.

The illustrated computing environment (10) includes a computing device (12). In one embodiment, the computing device (12) may be a subgraph matching device (100).

A computing device (12) includes at least one processor (14), a computer-readable storage medium (16), and a communication bus (18). The processor (14) may cause the computing device (12) to operate in accordance with the exemplary embodiments described above. For example, the processor (14) may execute one or more programs stored in the computer-readable storage medium (16). The one or more programs may include one or more computer-executable instructions, which, when executed by the processor (14), may be configured to cause the computing device (12) to perform operations in accordance with the exemplary embodiments.

A computer-readable storage medium (16) is configured to store computer-executable instructions or program code, program data, and/or other suitable forms of information. A program (20) stored in the computer-readable storage medium (16) includes a set of instructions executable by the processor (14). In one embodiment, the computer-readable storage medium (16) may be a memory (volatile memory such as random access memory, non-volatile memory, or a suitable combination thereof), one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, any other form of storage medium that can be accessed by the computing device (12) and capable of storing desired information, or a suitable combination thereof.

A communication bus (18) interconnects various other components of the computing device (12), including the processor (14) and computer-readable storage media (16).

The computing device (12) may also include one or more input/output interfaces (22) that provide interfaces for one or more input/output devices (24) and one or more network communication interfaces (26). The input/output interfaces (22) and the network communication interfaces (26) are coupled to the communication bus (18). The input/output devices (24) may be coupled to other components of the computing device (12) via the input/output interfaces (22). Exemplary input/output devices (24) may include input devices such as a pointing device (such as a mouse or trackpad), a keyboard, a touch input device (such as a touchpad or a touchscreen), a voice or sound input device, various types of sensor devices and/or photographing devices, and/or output devices such as a display device, a printer, speakers, and/or a network card. The exemplary input/output devices (24) may be included within the computing device (12) as a component that constitutes the computing device (12), or may be coupled to the computing device (12) as a separate device distinct from the computing device (12).

Although representative embodiments of the present invention have been described in detail above, those skilled in the art will understand that various modifications can be made to the above-described embodiments without departing from the scope of the present invention. Therefore, the scope of the rights of the present invention should not be limited to the described embodiments, but should be determined not only by the claims described below but also by equivalents of the claims.

100 : Subgraph Matching Device
102: Serialization module
104 : Graph Restoration Module
106 : Matching module

Claims (17)

A serialization module that acquires multiple graph data and combines the acquired multiple graph data to generate a single data stream;
A graph restoration module that converts the above data stream into a graph stream; and
Includes a matching module that searches for a graph pattern matching a preset subgraph query for the above graph stream,
The above serialization module is a subgraph matching device that extracts edge information from each of the plurality of graph data and connects the extracted edge information in a row to create a single data stream.
delete In claim 1,
The above serialization module divides the one data stream into batch sizes of preset units,
The above graph restoration module is a subgraph matching device that restores graph data for each time stamp based on edge information of each divided data stream and converts it into a graph stream.
In claim 1,
The above matching module,
A subgraph matching device that generates a stream graph table by tracking edge information that changes according to a change in a timestamp in the above graph stream, and searches for a graph pattern matching the above subgraph query using the generated stream graph table.
In claim 4,
The above stream graph table is,
Contains columns of edge label, added index, added edges, removed index, and removed edges,
A subgraph matching device, wherein the edge label is a column storing a set of departure and arrival vertex labels of each edge of the graph, the added index is a column storing an index of an edge added to the graph, the added edges is a column storing a set of edges related to each edge label, the removed index is a column storing an index of an edge removed from the graph, and the removed edges is a column storing a set of edges removed related to each edge label.
In claim 5,
The above matching module,
Generate sequential edges information for the above subgraph query,
The above sequential edge information is information about the sequence of each edge included in the subgraph query, and the information for each edge is composed of the ID of the starting vertex and the ID of the arrival vertex of the corresponding edge, a subgraph matching device.
In claim 6,
The above matching module,
A subgraph matching device that searches for items matching sequential edge information for the subgraph query in the edge label and added edges columns of the above stream graph table.
In claim 7,
The above matching module,
Based on the results of the above search, a subgraph matching result table is generated for each time stamp of the graph stream,
The above subgraph matching result table is a subgraph matching device in which the IDs of each vertex in a graph pattern matching the graph pattern of the above subgraph query are arranged sequentially.
one or more processors, and
A method performed on a computing device having a memory storing one or more programs executed by one or more processors,
A step of acquiring multiple graph data;
A step of combining the acquired plurality of graph data to generate a single data stream;
a step of converting the above data stream into a graph stream; and
Comprising a step of searching for a graph pattern matching a preset subgraph query for the above graph stream,
The step of generating the above one data stream is:
A step of extracting edge information from each of the above multiple graph data; and
A subgraph matching method comprising a step of generating a single data stream by connecting the extracted edge information in a row.
delete In claim 9,
The above subgraph matching method is,
Further comprising a step of dividing the above one data stream into batch sizes of preset units,
The step of converting into the above graph stream is a subgraph matching method in which the graph data is restored for each time stamp for each data stream based on the edge information of each of the divided data streams and converted into a graph stream.
In claim 9,
The above search steps are:
A step of generating a stream graph table by tracking edge information that changes according to changes in timestamps in the above graph stream; and
A subgraph matching method, comprising a step of searching for a graph pattern matching the subgraph query using the generated stream graph table.
In claim 12,
The above stream graph table is,
Contains columns of edge label, added index, added edges, removed index, and removed edges,
A subgraph matching method, wherein the edge label is a column storing a set of departure and arrival vertex labels of each edge of the graph, the added index is a column storing an index of an edge added to the graph, the added edges is a column storing a set of edges related to each edge label, the removed index is a column storing an index of an edge removed from the graph, and the removed edges is a column storing a set of edges removed related to each edge label.
In claim 13,
The above search steps are:
Further comprising a step of generating sequential edges information for the above subgraph query,
The above sequential edge information is information about the sequence of each edge included in the subgraph query, and the information for each edge is composed of the ID of the starting vertex and the ID of the arrival vertex of the corresponding edge, a subgraph matching method.
In claim 14,
The above search steps are:
A subgraph matching method for searching for items matching sequential edge information for the subgraph query in the edge label and added edges columns of the above stream graph table.
In claim 15,
The above search steps are:
Further comprising the step of generating a subgraph matching result table for each time stamp of the graph stream according to the result of the above search,
A subgraph matching method in which the above subgraph matching result table sequentially arranges the IDs of each vertex in a graph pattern matching the graph pattern of the above subgraph query.
A computer program stored in a non-transitory computer readable storage medium,
The computer program comprises one or more instructions, which, when executed by a computing device having one or more processors, cause the computing device to:
A step of acquiring multiple graph data;
A step of combining the acquired plurality of graph data to generate a single data stream;
a step of converting the above data stream into a graph stream; and
Perform a step of searching for a graph pattern matching a pre-set subgraph query for the above graph stream,
The step of generating the above one data stream is:
A step of extracting edge information from each of the above multiple graph data; and
A computer program comprising a step of connecting the extracted edge information in a row to generate a single data stream.