패스 표현의 효과적인 처리

Abstract

최근 GIS, network, WWW, 멀티미디어 상연물등과 자료 변화의 순서가 중요한 영역의 문제들을 자연스럽게 표현할 수 있는 그래프 타입에 대한 연구가 이루어 지고 있다. 이 논문에서는 DAG(directed acyclic graph)로 표현되는 멀티미디어 상연물을 이용하여 DAG의 패스를 효과적으로 검색 처리하는 코드 시스템인 노드 코드(node code) 시스템을 소개한다. 노드 코스 시스템은 그래프의 각 노드마다 유일한 2진 문자열(binary string)을 부여한다. 두 노드 사이의 노드 코드의 비교하면 그래프 횡단 없이 두 노드가 연결되어 있느지를 확인할 수 있다. 노드 코드를 이용하여 두 노드 사이의 패스의 건설을 전통적인 그래프 횡단을 이용한 방법보다 효과적으로 수행하는 알고리즘도 소개한다.

Recently, there has been a lot of research on graph-type data because it can model the application domains such as GIS, network, WWW, multimedia presentations etc., and domains in which the data sequence is important. In this paper, an efficient code system, called node code system, is proposed to evaluate paths of DAG in a multimedia presentation graph. The node code system assigns a unique binary string to each node of a graph. The comparison of node codes of two nodes tells the connectivity between the nodes. The method using the property of the node code system allows us to construct the paths between two nodes more efficiently than the method using conventional graph traversals. The algorithms to construct paths using the node code system are provided.

Recently, there has been a lot of research on graph-type data because it can model the application domains such as GIS, network, WWW, multimedia presentations etc., and domains in which the data sequence is important. In this paper, an efficient code system, called node code system, is proposed to evaluate paths of DAG in a multimedia presentation graph. The node code system assigns a unique binary string to each node of a graph. The comparison of node codes of two nodes tells the connectivity between the nodes. The method using the property of the node code system allows us to construct the paths between two nodes more efficiently than the method using conventional graph traversals. The algorithms to construct paths using the node code system are provided.