In-Memory Caching for Enhancing Subgraph Accessibility
Graphs have been utilized in various fields because of the development of social media and mobile devices. Various studies have also been conducted on caching techniques to reduce input and output costs when processing a large amount of graph data. In this paper, we propose a two-level caching schem...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-08-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/10/16/5507 |
| _version_ | 1827710779294482432 |
|---|---|
| author | Kyoungsoo Bok Seunghun Yoo Dojin Choi Jongtae Lim Jaesoo Yoo |
| author_facet | Kyoungsoo Bok Seunghun Yoo Dojin Choi Jongtae Lim Jaesoo Yoo |
| author_sort | Kyoungsoo Bok |
| collection | DOAJ |
| description | Graphs have been utilized in various fields because of the development of social media and mobile devices. Various studies have also been conducted on caching techniques to reduce input and output costs when processing a large amount of graph data. In this paper, we propose a two-level caching scheme that considers the past usage pattern of subgraphs and graph connectivity, which are features of graph topology. The proposed caching is divided into a used cache and a prefetched cache to manage previously used subgraphs and subgraphs that will be used in the future. When the memory is full, a strategy that replaces a subgraph inside the memory with a new subgraph is needed. Subgraphs in the used cache are managed by a time-to-live (TTL) value, and subgraphs with a low TTL value are targeted for replacement. Subgraphs in the prefetched cache are managed by the queue structure. Thus, first-in subgraphs are targeted for replacement as a priority. When a cache hit occurs in the prefetched cache, the subgraphs are migrated and managed in the used cache. As a result of the performance evaluation, the proposed scheme takes into account subgraph usage patterns and graph connectivity, thus improving cache hit rates and data access speeds compared to conventional techniques. The proposed scheme can quickly process and analyze large graph queries in a computing environment with small memory. The proposed scheme can be used to speed up in-memory-based processing in applications where relationships between objects are complex, such as the Internet of Things and social networks. |
| first_indexed | 2024-03-10T17:43:33Z |
| format | Article |
| id | doaj.art-2ff104f0d89745e890b7f929097f633f |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T17:43:33Z |
| publishDate | 2020-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-2ff104f0d89745e890b7f929097f633f2023-11-20T09:36:17ZengMDPI AGApplied Sciences2076-34172020-08-011016550710.3390/app10165507In-Memory Caching for Enhancing Subgraph AccessibilityKyoungsoo Bok0Seunghun Yoo1Dojin Choi2Jongtae Lim3Jaesoo Yoo4Department of SW Convergence Technology, Wonkwang University, Iksandae 460, Iksan, Jeonbuk 54538, KoreaDepartment of Information and Communication Engineering, Chungbuk National University, Chungdae-ro 1, Seowon-Gu, Cheongju, Chungbuk 28644, KoreaDepartment of Information and Communication Engineering, Chungbuk National University, Chungdae-ro 1, Seowon-Gu, Cheongju, Chungbuk 28644, KoreaDepartment of Information and Communication Engineering, Chungbuk National University, Chungdae-ro 1, Seowon-Gu, Cheongju, Chungbuk 28644, KoreaDepartment of Information and Communication Engineering, Chungbuk National University, Chungdae-ro 1, Seowon-Gu, Cheongju, Chungbuk 28644, KoreaGraphs have been utilized in various fields because of the development of social media and mobile devices. Various studies have also been conducted on caching techniques to reduce input and output costs when processing a large amount of graph data. In this paper, we propose a two-level caching scheme that considers the past usage pattern of subgraphs and graph connectivity, which are features of graph topology. The proposed caching is divided into a used cache and a prefetched cache to manage previously used subgraphs and subgraphs that will be used in the future. When the memory is full, a strategy that replaces a subgraph inside the memory with a new subgraph is needed. Subgraphs in the used cache are managed by a time-to-live (TTL) value, and subgraphs with a low TTL value are targeted for replacement. Subgraphs in the prefetched cache are managed by the queue structure. Thus, first-in subgraphs are targeted for replacement as a priority. When a cache hit occurs in the prefetched cache, the subgraphs are migrated and managed in the used cache. As a result of the performance evaluation, the proposed scheme takes into account subgraph usage patterns and graph connectivity, thus improving cache hit rates and data access speeds compared to conventional techniques. The proposed scheme can quickly process and analyze large graph queries in a computing environment with small memory. The proposed scheme can be used to speed up in-memory-based processing in applications where relationships between objects are complex, such as the Internet of Things and social networks.https://www.mdpi.com/2076-3417/10/16/5507graph cachingsubgraphprefetchingreplacementused cacheprefetched cache |
| spellingShingle | Kyoungsoo Bok Seunghun Yoo Dojin Choi Jongtae Lim Jaesoo Yoo In-Memory Caching for Enhancing Subgraph Accessibility Applied Sciences graph caching subgraph prefetching replacement used cache prefetched cache |
| title | In-Memory Caching for Enhancing Subgraph Accessibility |
| title_full | In-Memory Caching for Enhancing Subgraph Accessibility |
| title_fullStr | In-Memory Caching for Enhancing Subgraph Accessibility |
| title_full_unstemmed | In-Memory Caching for Enhancing Subgraph Accessibility |
| title_short | In-Memory Caching for Enhancing Subgraph Accessibility |
| title_sort | in memory caching for enhancing subgraph accessibility |
| topic | graph caching subgraph prefetching replacement used cache prefetched cache |
| url | https://www.mdpi.com/2076-3417/10/16/5507 |
| work_keys_str_mv | AT kyoungsoobok inmemorycachingforenhancingsubgraphaccessibility AT seunghunyoo inmemorycachingforenhancingsubgraphaccessibility AT dojinchoi inmemorycachingforenhancingsubgraphaccessibility AT jongtaelim inmemorycachingforenhancingsubgraphaccessibility AT jaesooyoo inmemorycachingforenhancingsubgraphaccessibility |