Multi-level caching method and multi-level caching system for enhancing graph processing performance

1. A multi-level caching method comprising:

receiving a query request for graph data;

searching for the graph data within a first cache memory in which data output in response to a previous query request is stored;

re-searching for the graph data within a second cache memory in which neighboring data with prior access to the data stored within the first cache memory is stored when the graph data is not found in the first cache memory;

outputting first neighboring data found by the re-searching for the graph data when a response to the query request is output;

storing the first neighboring data within the first cache memory;

selecting data with prior access to the first neighboring data as new neighboring data;

replacing previously-stored neighboring data with the new neighboring data within the second cache memory;

identifying a list of vertices constituting a subgraph, for each previous query recorded in a query history table;

extracting a query pattern including a first vertex with a high frequency of use from the subgraph based on the list; and

setting a time-to-live (TTL) value of the first vertex based on a number of first vertices in the query pattern and a pattern weight assigned to the first vertex.

2. The multi-level caching method of claim 1 , wherein the storing of the first neighboring data comprises, when the first cache memory does not have an available storage space:

comparing a TTL value set for data found in the second cache memory to a minimum TTL value among TTL values set for the data in the first cache memory; and

replacing data with the minimum TTL value in the first cache memory by data of the second cache memory, when the TTL value is greater than the minimum TTL value.

3. The multi-level caching method of claim 1 , wherein the new neighboring data is selected from data with prior access to the first neighboring data within a predetermined number of hops, based on a number of accesses.

4. The multi-level caching method of claim 3 , wherein the previously-stored neighboring data is deleted from the second cache memory as the new neighboring data is stored within the second cache memory.

5. The multi-level caching method of claim 1 , wherein

the graph data comprises a plurality of vertices constituting a subgraph corresponding to the query request, and edges connecting the plurality of vertices, and

the outputting of the first neighboring data comprises, when a portion of the plurality of vertices is found in the first cache memory, combining a portion of the vertices found in the first cache memory and remaining vertices found by the re-searching and outputting the combined vertices as the graph data.

6. The multi-level caching method of claim 1 , wherein the extracting of the query pattern comprises:

arranging the list in a descending order based on a frequency of use;

calling each of the vertices in the list in an order of the arranged list and generating a frequent-pattern (FP) tree based on an edge indicating a number of accesses between the vertices; and

extracting the query pattern using the FP tree.

7. The multi-level caching method of claim 1 , further comprising:

additionally recording the query in the query history table when the query request is received; and

updating the TTL value of the first vertex, further based on a pattern weight assigned to a second vertex of a query pattern extracted using the additionally recorded query.

8. A multi-level caching system comprising:

a searcher configured to receive a query request for graph data and search for the graph data within a first cache memory in which data output in response to a previous query request is stored, the searcher further configured to re-search for the graph data within a second cache memory in which neighboring data with prior access to the data stored within the first cache memory is stored, when the graph data is not found in the first cache memory; and

an outputter configured to output first neighboring data found by the re-searching for the graph data when a response to the query request is output; and

a memory manager configured to store the first neighboring data within the first cache memory, select data with prior access to the first neighboring data as new neighboring data, and replace previously-stored neighboring data with the new neighboring data within the second cache memory;

a pattern extractor configured to identify a list of vertices constituting a subgraph for each previous query recorded in a query history table, and to extract a query pattern including a first vertex with a high frequency of use from the subgraph based on the list; and

a memory manager configured to set a time-to-live (TTL) value of the first vertex based on a number of first vertices in the query pattern and a pattern weight assigned to the first vertex.

9. The multi-level caching system of claim 8 , wherein the previously-stored neighboring data is deleted from the second cache memory as the new neighboring data is stored within the second cache memory.

10. The multi-level caching system of claim 8 , wherein the memory manager is configured to additionally record the query in the query history table when the query request is received, and to update the TTL value of the first vertex, further based on a pattern weight assigned to a second vertex of a query pattern extracted using the additionally recorded query.