Digital Library[ Search Result ]
An Efficient Algorithm for Diversified Top-k Subgraph Querying
http://doi.org/10.5626/JOK.2024.51.2.103
Subgraph matching is a core and important problem in graph analysis. The subgraph matching problem is to find all embeddings of the query graph in the data graph. However, the output results from previously proposed algorithms often overlap with each other, and thus interesting results are often missed. For this purpose, the diversified top-k subgraph querying problem is proposed. The diversified top-k subgraph querying problem is to find k embeddings that have the highest coverage among embeddings of the query graph in the data graph. In this paper, we present an algorithm for the diversified top-k subgraph querying problem and demonstrate that it finds diversified top-k results efficiently compared to existing algorithms.
An Efficient Continuous Subgraph Matching Technique for Graph Stream Processing in a Memory-constrained Environment
Somin Lee, Sanghyeuk Kim, Hyeonbyeong Lee, Dojin Choi, Jongtae Lim, Kyoungsoo Bok, Jaesoo Yoo
http://doi.org/10.5626/JOK.2022.49.12.1154
Recently, with the proliferation of social network services, the size of graph data has been becoming increasingly vast and graph data are changed in real-time. Therefore, it is necessary to perform continuous query processing on real-time graph streams. Moreover, it is difficult keep the entire large graph data in the main memory since its size is constrained in real-world application environments. Consequently, continuous subgraph matching techniques are required by considering memory-constrained environments. In this paper, we propose a continuous subgraph matching technique for graph streams in a memory-constrained environment. The proposed technique consists of modules such as index manager, query processor, and cache manager for efficient continuous subgraph matching. We conduct performance evaluations to demonstrate the superiority of the proposed technique.
New Adaptive Matching Order and Performance Comparison for Subgraph Matching Problem
Seunghwan Min, Wonseok Shin, Chaewon Kim, Kunsoo Park
http://doi.org/10.5626/JOK.2022.49.1.1
In recent years, graph analysis has been used in various applications. One of the fundamental problems in graph analysis is the subgraph matching problem. Given a data graph and a query graph, the subgraph matching problem is to find all embeddings of the query graph in the data graph. Many backtracking-based algorithms have been studied to solve this problem. In this paper, we analyzed the problems in adaptive matching order proposed by DAF, a state-of-the-art algorithm that solves this problem, and introduced an improved adaptive matching order. Furthermore, we conducted experiments with real data graphs to demonstrate that the proposed matching order was more effective than the previous matching orders if the pruning technique was not used or the elapsed time was not very short even if the pruning technique was used.
An Efficient Continuous Subgraph Matching Scheme Considering Data Reuse
Dojin Choi, Kyoungsoo Bok, Jaesoo Yoo
http://doi.org/10.5626/JOK.2019.46.8.842
With an increase in the utilization of graph streams in various applications, a continuous subgraph matching scheme is required to search the subgraphs that undergo changes in real time. In this paper, we propose an efficient continuous subgraph matching scheme that reuses indexing and performs distributed processing in graph stream environments. In order to perform distributed processing, we propose a query decomposition method based on the degree and subsequently manage the decomposed subqueries as an index. The proposed scheme reuses indexing information to reduce the load on the index caused by the environment in which multiple queries are entered. We also conduct query allocation through a cost model that calculates the indexing load of each server. For efficient performance of distributed processing in stream environments, the proposed scheme was implemented in Storm. Various performance evaluations were conducted to demonstrate the superiority of the proposed scheme.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr