중학생의 과학 그래프 구성에 관한 문제 해결 과정 연구

이재원,박가영,노태희 한국과학교육학회 2019 한국과학교육학회지 Vol.39 No.5

In this study, we investigated the middle school students’ construction processes of scientific graph from the perspective of the problem solving process. Ten 9th graders participated in this study. They constructed a scientific graph based on pictorial data depicting precipitation reaction. The think-aloud method was used in order to investigate their thinking processes deeply. Their activities were videotaped, and semi-structured interviews were also conducted. The analysis of the results revealed that their processes of scientific graph construction could be classified into four types according to the problem solving strategy and the level of representations utilized. Students using the structural strategy succeeded in constructing scientific graph regardless of the level of representation utilized, by analyzing the data and identifying the trend based on the propositional knowledge about the target concept of the graph. Students of random strategy-higher order representation type were able to succeed in constructing scientific graph by systematically analyzing the characteristics of the data using various representations, and considering the meaning of the graph constructed in terms of the scientific context. On the other hand, students of random strategy-lower order representation type failed to construct correct scientific graph by constructing graph in a way of simply connecting points, and checking the processes of graph construction only without considering the scientific context. On the bases of the results, effective methods for improving students’ ability to construct scientific graphs are discussed. 이 연구에서는 중학생들의 과학 그래프 구성 과정을 문제 해결의 관점에서 심층적으로 조사하였다. 중학교 3학년 학생 10명이 연구에 참여하였으며, 이들은 앙금 생성 반응을 묘사한 그림 자료를 바탕으로 과학 그래프를 구성하였다. 학생들이 그래프를 구성할 때 거치는 사고 과정을 심층적으로 조사하기 위하여 발성사고법을 활용하였고, 그래프 구성 과정에 대한 녹화 및 반구조화된 면담을 실시하였다. 연구 결과, 학생들의 과학 그래프 구성 유형은 문제 해결 전략과 활용한 표상의 수준에 따라 네 가지 유형으로 구분할 수 있었다. 구조적 전략을 사용한 학생들은 그래프의 목표 개념에 대한 명제적 지식을 바탕으로 자료를 분석하고 경향성을 파악함으로써 활용한 표상의 수준과 무관하게 과학 그래프 구성에 성공하였다. 임의 전략-고차원 표상 유형의 학생들은 다양한 표상을 활용해 자료의 특징을 체계적으로 분석하고 자신이 구성한 그래프의 의미를 과학적 맥락에서 검토하는 과정을 거치며 과학 그래프 구성에 성공할 수 있었다. 반면, 임의전략-저차원 표상 유형의 학생들은 단순히 점을 연결하는 방식으로 그래프를 구성하였고, 과학적 맥락에 대한 고려 없이 그래프 구성 과정만을 점검하는 수준에 머물며 올바른 과학 그래프 구성에 실패하였다. 연구 결과를 바탕으로 학생들의 과학 그래프 구성 능력을 효과적으로 함양하는 방안을 제안하였다.

대용량 하이퍼그래프에 대한 효율적인 탐색 기법과 분석에의 응용

류충모(Chungmo Ryu),서정혁(Junghyuk Seo),김명호(Myoung Ho Kim) 한국정보과학회 2017 정보과학회 컴퓨팅의 실제 논문지 Vol.23 No.8

하이퍼그래프는 노드와 여러 노드를 연결할 수 있는 하이퍼에지로 구성된다. 하이퍼그래프 분석을 위해 그래프 기본 연산 중 그래프 탐색을 사용할 수 있다. 일반 그래프에 사용되는 DFS, BFS 탐색방법을 하이퍼그래프에 그대로 적용하였을 시 여러 노드를 연결하는 하이퍼에지의 특성을 고려하지 않는 문제가 있다. 본 논문에서는 하이퍼그래프를 위한 DBMS인 hypergraphDB에 저장 된 그래프 탐색 시 에지 단위로 탐색 여부를 판단하는 방법을 제안하고, 제안 탐색 방법을 응용한 하이퍼그래프 분석 실험을 수행하였다. 실험을 통해 일반 그래프의 탐색 기법을 적용한 경우 보다 빠른 속도와 보다 적은 DB 접근 횟수로 그래프 분석 작업을 수행함을 보인다. A hypergraph consists of a set of nodes and hyperedges that connect an arbitrary number of nodes. We employ graph traversal algorithms such as BFS and DFS to analyze or explore hypergraph data. However, the conventional BFS and DFS do not consider the structural characteristics of hyperedges. In this paper, we propose a method to record visited edges and nodes during the traversal algorithm for data stored in hypergraphDB. In the experiments, we conduct various hypergraph analyses that utilize traversal algorithms and show that our method achieves a fewer number of database accesses and faster processing time than the conventional one.

유향그래프에서 동시발생 부분그래프 마이닝

박기성,한용구,이영구 한국정보과학회 2014 데이타베이스 연구 Vol.30 No.2

Recently graph mining algorithms are facing the challenges to deal with mining co-occurrentsubgraphs in directed graph databases. In particular, co-occurrent frequent subgraph mining is animportant technique that can be utilized for pattern analysis and discriminative features for furtheranalysis such as classification and clustering. Recently, co-occurrent subgraph mining techniqueshave been proposed for undirected graph DBs. However, the existing techniques cannot reflectfeature of directed graph because these techniques do not consider orders of between frequentsubgraphs. In this paper, we propose an efficient co-occurrent subgraph minining techniqueconsidering orders between frequent subgraphs. The proposed technique finds co-occurrentsubgraphs efficiently by expressing directed graphs as compression forms of subsequences. Inexperiments, we show that the proposed technique can reduce runtime by up to 30% comparedwith the naive technique. 최근 유향 그래프 DB로부터 다양한 데이터 마이닝 기법을 활용하여 유용한 지식을 찾아내는 기술이 주목받고있다. 특히 동시발생 부분그래프 마이닝 기법은 그래프 DB의 고유한 특성을 나타내는 유용한 특징으로, 패턴 분석도구 및 분류, 군집화와 같은 고차원 분석에 활용되는 중요한 기술이다. 최근 동시발생 부분그래프를 마이닝하기위한 다양한 기술들이 제안되었으나, 부분그래프들 간의 순서를 고려하지 못하여 유향 그래프의 특성을 제대로 반영하지 못하고 있다. 본 논문에서는 유향 그래프 DB에서 순서 정보를 고려한 동시발생 부분그래프를 효율적으로마이닝하는 방법을 제안한다. 제안하는 기법은 그래프를 시퀀스들로 압축 표현하여 순서가 고려된 동시발생 부분그래프를 효율적으로 찾는다. 실험을 통하여 제안하는 동시발생 부분그래프 마이닝 기법이 나이브 기법보다 최대30%까지 수행시간을 단축함을 보인다.

부호형 그래프 요약 기법

조현수,주현진,안종철,진소연,신유경,신기정 한국정보과학회 2022 데이타베이스 연구 Vol.38 No.3

소셜 네트워크 서비스, 전자 상거래 등 다양한 웹 서비스들의 사용량이 폭발적으로 증가하고 있으며, 해당 정보들을 표현하기 위한 그래프의 규모 역시 기하급수적으로 증가하고 있다. 이러한 대용량 그래프를 효율적으로 활용하기 위해 정보손실을 최소화하면서 간결한 요약 그래프를 얻어내는 그래프 요약 방법이 제안되었다. 하지만 기존 그래프 요약 방법은 기본 또는 가중 그래프만을 대상으로 연구되어, 긍정 및 부정적 관계를 포함하고 있는 부호형 그래프를 다루고 있지 않다. 부호형 그래프는 소셜 미디어, 전자 상거래뿐만 아니라 국방 분야의 다양한 군 관련 정보들에서 흔히 나타나는 긍정 및 부정적 관계들을 포함한 그래프이다. 본 논문에서는 부호형 그래프의 간선과 간선의 부호까지 잘 유지하는 비용함수를 사용하여 정보손실을 최소화하는 새로운 그래프 요약 기법을 제안하였다. 또한, 제안 방법이 기존 방법 대비 최대 24.83% 오차가 적었고, 부호형 그래프의 구조적 균형 또한 잘 유지함을 실험적으로 보였다.

그래프 이력 데이터 접근을 위한 효과적인 저장 관리 기법

김기훈(Gihoon Kim),김이나(Ina KIm),최도진(Dojin Choi),김민수(Minsoo Kim),복경수(Kyoungsoo Bok),유재수(Jaesoo Yoo) 한국콘텐츠학회 2018 한국콘텐츠학회논문지 Vol.18 No.2

최근 소셜 네트워크, 인용 네트워크 등 여러 분야에서 다양한 그래프 데이터가 활용되고 있다. 시간에 따라 그래프가 동적으로 변화함에 따라 변경 내용 추적 및 특정 시점 그래프 검색을 위해 그래프 이력 데이터를 관리하는 것이 필요하다. 대부분의 이력 데이터는 시간에 따라 부분적인 변화가 발생하기 때문에 시간 단위로 데이터를 저장할 경우 변경되지 않은 데이터가 중복 저장된다. 본 논문에서는 시간별 그래프의 중복 저장을 최소화하기 위한 그래프 이력 저장 관리 기법을 제안한다. 제안하는 기법은 그래프의 변화를 계속적으로 탐지하여 과거 그래프와 중복되는 서브 그래프를 하나의 중복 스냅샷에 저장한다. 중복 스냅샷에는 다수의 델타 스냅샷이 연결되어 각 시간에 따른 변화 데이터를 유지한다. 중복 스냅샷에 저장된 중복 데이터를 공통으로 관리하여 공간의 효율을 향상시킨다. 또한, 해당 시점의 그래프를 탐색하기 위해서 중복 스냅샷과 델타 스냅샷을 연결하였다. 제안하는 기법의 우수성을 보이기 위해 다양한 성능평가를 수행한다. Recently, various graph data have been utilized in various fields such as social networks and citation networks. As the graph changes dynamically over time, it is necessary to manage the graph historical data for tracking changes and retrieving point-in-time graphs. Most historical data changes partially according to time, so unchanged data is stored redundantly when data is stored in units of time. In this paper, we propose a graph history storage management method to minimize the redundant storage of time graphs. The proposed method continuously detects the change of the graph and stores the overlapping subgraph in intersection snapshot. Intersection snapshots are connected by a number of delta snapshots to maintain change data over time. It improves space efficiency by collectively managing overlapping data stored in intersection snapshots. We also linked intersection snapshots and delta snapshots to retrieval the graph at that point in time. Various performance evaluations are performed to show the superiority of the proposed scheme.

빈발 패턴 기반 효율적인 그래프 스트림 요약 기법

김상혁,이현병,최도진,임종태,복경수,유재수 한국콘텐츠학회 2023 한국콘텐츠학회논문지 Vol.23 No.9

소셜 미디어, 웹 서비스, IoT 응용에서 생성되는 대규모 그래프를 효과적으로 표현하고 처리하기 위해 그래프 요약 기법들이 사용되고 있다. 그래프 요약은 그래프 구조와 의미를 표현할 수 있으며 데이터 크기를 감소시켜 질의 처리 및 그래프 분석 성능을 향상 시킬 수 있다. 하지만 그래프가 시간이 지남에 따라 점점 커지면서 매번 그래프를 요약하는 데 많은 시간이 소요된다. 본 논문에서는 정점의 연결성, 이웃 정점의 수 및 정점 차수의 비율을 고려한 패턴 생성을 통해 그래프를 요약하는 기법을 제안한다. 제안하는 기법은 그래프 스트림에 따라 변화하는 그래프를 요약하기 위해 1-홉의 빈발 패턴을 찾아 DSMatrix로 표현하고 그 빈발 패턴을 N-홉의 패턴으로 확장하여 빈발 패턴 관리 테이블에 저장한다. 저장된 빈발 패턴들을 이웃 점수를 사용하여 요약할 그래프에 적용하여 요약 그래프를 생성한다. 다음 윈도우에서 생성된 N-홉의 빈발 패턴과 빈발 패턴 테이블에 저장된 패턴을 비교하여 빈발 여부를 판단함으로써 패턴 검출 시간을 감소 시킨다. 다양한 성능 평가를 통해 제안하는 기법이 기존 기법에 비해 처리 시간과 정확도 측면에서 성능이 우수함을 보인다.

제한된 메모리를 가진 GPU를 이용한 효율적인 그래프 알고리즘 처리 기법

송상호,이현병,최도진,임종태,복경수,유재수 한국콘텐츠학회 2022 한국콘텐츠학회논문지 Vol.22 No.8

Recently, research on processing a large-capacity graph using GPUs has been conducting. In order to process a large-capacity graph in a GPU with limited memory, the graph must be divided into subgraphs and then processed by scheduling subgraphs. In this paper, we propose an efficient graph algorithm processing scheme in GPU environments with limited memory and performance evaluation. The proposed scheme consists of a graph differential subgraph scheduling method and a graph segmentation method. The bulk graph segmentation method determines how a large-capacity graph can be segmented into subgraphs so that it can be processed efficiently by the GPU. The differential subgraph scheduling method schedule subgraphs processed by GPUs to reduce redundant transmission of the repeatedly used data between HOST-GPUs. It shows the superiority of the proposed scheme by performing various performance evaluations. 최근 대용량 그래프의 반복 처리를 위하여 GPU를 이용하는 연구가 진행되고 있다. 메모리가 제한된 GPU를 이용하여 대용량 그래프를 처리하기 위해서는 그래프를 서브 그래프로 분할한 후 서브 그래프들을 스케줄링 해서 처리해야 한다. 그러나 활성 정점에 따라 서브 그래프가 처리되기 때문에 그래프 처리 과정 속에서 불필요한 데이터 전송이 반복된다. 본 논문에서는 메모리가 제한된 GPU 환경에서 효율적인 그래프 알고리즘 처리 기법을 제안하고 성능 평가를 수행한다. 제안하는 기법은 그래프 차등 서브 그래프 스케줄링 방법과 그래프 분할 방법으로 구성된다. 대용량 그래프 분할 방법은 GPU에서 효율적으로 처리할 수 있도록 대용량 그래프를 서브 그래프로 분할할 수 있는 방법을 결정한다. 차등 서브그래프 스케줄링 방법은 GPU에서 처리하는 서브 그래프를 스케줄링하여 반복적으로 사용되는 HOST-GPU 간의 데이터 중복 전송을 줄인다. 다양한 그래프 처리 알고리즘들의 성능 평가를 수행함으로써 제안하는 기법은 기존 분할 기법 대비 170%, 기존 처리 기법 대비 268% 향상되었다.

출발점과 목표점을 일반화 가시성그래프로 표현된 맵에 포함하기 위한 빠른 알고리즘

유견아,전현주,Yu, Kyeon-Ah,Jeon, Hyun-Joo 한국시뮬레이션학회 2006 한국시뮬레이션학회 논문지 Vol.15 No.2

가시성그래프는 최소 탐색 공간으로 게임환경을 모델링하여 효과적으로 길을 찾을 수 있도록 하는 방법으로 잘 알려져 있다. 일반화 가시성그래프는 가시성그래프의 가장 큰 단점으로 지적되는 "벽-껴안기" 문제를 해결하기 위해 확장된 장애물의 경계 위에 생성된 가시성그래프이다. 일반화 가시성그래프에 의해 구해진 경로는 근사 최적이며 자연스럽게 보이는 장점이 있다. 본 논문에서는 변화하는 출발점과 목표점과 정적인 장애물 사이를 움직이는 게임 캐릭터에 효과적으로 일반화 가시성그래프를 적용하는 방법을 제안한다. 일반화 가시성그래프는 일단 생성되면 최소 탐색공간을 보장하지만 그 생성 자체는 노드사이의 링크의 교차 여부론 일일이 체크하여야 하므로 시간이 많이 소요된다. 아이디어는 먼저 정적인 장애물만으로 지도를 생성해 놓고 출발점과 목표점을 빠르게 포함시키는 것이다. 출발점과 목표점의 포함 부분이 여러 번 반복되어야 하는 과정이므로 출발점과 목표점을 빠르게 포함시키는데에 연산 기하학 분야의 회전 plane-sweep 알고리즘을 이용할 것을 제안한다. 시뮬레이션 결과는 전체 그래프를 매번 생성하는 것보다 제안한 방법의 실행시간이 39%-68% 정도 향상되었음을 보여준다. The visibility graph is a well-known method for efficient path-finding with the minimum search space modelling the game world. The generalized visibility graph is constructed on the expanded obstacle boundaries to eliminate the "wall-hugging" problem which is a major disadvantage of using the visibility graph. The paths generated by the generalized visibility graph are guaranteed to be near optimal and natural-looking. In this paper we propose the method to apply the generalized visibility graph efficiently for game characters who moves among static obstacles between varying start and goal points. Even though the space is minimal once the generalized visibility graph is constructed, the construction itself is time-consuming in checking the intersection between every two links connecting nodes. The idea is that we build the map for static obstacles first and then incorporate start and goal nodes quickly. The incorporation of start and goal nodes is the part that must be executed repeatedly. Therefore we propose to use the rotational plane-sweep algorithm in the computational geometry for incorporating start and goal nodes efficiently. The simulation result shows that the execution time has been improved by 39%-68% according to running times in the game environment with multiple static obstacles.

F-Index: 빠른 부분그래프 매칭을 위한 특징 인덱스

김송현(Song-Hyon Kim),송인철(Inchul Song),이윤준(Yoon-Joon Lee) 한국정보과학회 2013 정보과학회논문지 : 데이타베이스 Vol.40 No.1

본 논문에서는 대규모 데이터베이스 그래프에서 주어진 질의 그래프와 동형인 모든 부분그래프들을 찾는 부분그래프 문제를 다룬다. 최근 빠른 부분그래프 매칭을 위해서 특징 인덱스를 기반으로 하는 기법들이 제안되었다. 이 기법들은 데이터베이스 그래프 정점들과 질의 그래프 정점들을 정점 특징을 사용하여 비교한 후 부분그래프 매칭 작업에서 고려할 필요가 없는 데이터베이스 그래프 상의 정점들을 걸러냄으로써 부분그래프 매칭 비용을 줄인다. 기존 기법들에서는 라벨 분포와 부분구조를 정점 특징으로 사용한다. 하지만 가지치기 능력과 추출비용 사이의 교환 비용을 적절히 고려하지 않았다. 본 논문에서는 빠른 부분그래프 매칭을 위한 F-Index라고 부르는 특징 인덱스를 제안한다. F-Index는 정점 특징의 가지치기 능력과 추출비용 사이의 균형을 고려한다. 제안하는 기법에서는 라벨 분포와 함께 정점 주변의 연결정보를 정점 특징으로 사용한다. 데이터베이스 그래프 상에서 적합하지 않은 정점들을 빠르게 걸러내기 위해 정점 특징을 추출한 후 인덱스를 구축한다. 본 논문에서는 다양한 실험을 통해 제안하는 기법이 기존기법들에 비해서 질의 처리 시간과 인덱스 생성 시간 측면에서 우수함을 보인다. In this paper, we study the subgraph matching problem in a large database graph, which finds all subgraphs in the database graph that are isomorphic to a query graph. Recently, feature index-based methods have been proposed for fast subgraph matching in a large database graph. They adopt the concept of vertex features to easily compare the vertices from a database graph with those from a query graph and filter out vertices in the database graph not eligible for subgraph matching. Previous approaches use various kinds of vertex features such as label distribution and discriminative substructures. However, they do not carefully consider the tradeoff between pruning power and extraction cost of vertex features. In this paper we propose a feature index called F-Index for fast subgraph matching. F-Index strikes a balance between pruning power and extraction cost. It uses the combination of label distribution and connectivity information of neighbors as vertex features. F-Index is constructed over the extracted vertex features for fast filtering of unqualified vertices. Experimental results show that our method outperforms the existing methods in terms of query processing time with comparable index build time.

대용량 그래프에서 효율적인 동적 그래프요약 기법

서호진,김현욱,박기성,이영구 한국정보과학회 2016 데이타베이스 연구 Vol.32 No.1

Graph summarization is a technique for compressing highly dense subgraphs in a massive graph. This technique can be utilized for analyzing the topological characteristics of graphs such as connectivity and skewness of graphs. The state-of-the-art graph summarization technique incrementally divides a large graph into subgraphs based on the hub nodes having higher degrees, and then summarizes each of the divided subgraphs. However, This summarization technique does not consider the frequent changes in a dynamic graph. Therefore, this technique requires a very long execution time since it must summarize the whole graph again whenever the graph changes. In this paper, we propose an efficient dynamic graph summarization technique for a massive graph. The proposed technique updates only the previously summarized subgraphs which are the subjects to be changed. Our technique can identify those summarized subgraphs using the set of hub node candidates without considering the whole graph. In our experiments, we observe that the proposed summarization technique can reduce the runtime by up to 57% compared to the state-of-the-art graph summarization technique. 그래프 요약은 대용량 그래프에서 밀집도가 높은 부분그래프를 압축 표현하는 기법이다. 이러한 그래프 요약은 연결성, 정도 비대칭성 등과 같은 그래프가 갖는 고유한 구조적 정보를 분석하기 위해 사용된다. 기존그래프 요약 기법은 그래프를 차수가 높은 허브 정점을 기준으로 다수의 부분 그래프들로 반복적으로 분할하고, 분할된 부분 그래프들을 각각 요약하였다. 그러나 동적 환경을 고려하지 않아 그래프가 변경될 때마다전체 그래프에 대해 다시 요약 구조를 탐색해야하기 때문에 매우 오랜 수행시간을 갖게 된다. 본 논문은 대용량 그래프에서 효율적인 동적 그래프 요약 기법을 제안한다. 제안하는 기법은 허브 후보 집합과 이전 주기의분할된 부분 그래프를 이용하여 전체 그래프에 대한 재분할 없이 효율적으로 이전 주기의 요약 구조를 갱신한다. 실험을 통하여 제안하는 기법이 기존의 기법보다 최대 57% 수행시간이 향상됨을 보인다.