Search

KR-20260061633-A - APPARATUS FOR NAVIGATION OF GRAPH AND METHOD USING THE SAME

KR20260061633AKR 20260061633 AKR20260061633 AKR 20260061633AKR-20260061633-A

Abstract

본 발명은 그래프 탐색 장치 및 이를 이용한 방법에 관한 것으로, 본 발명의 일실시예에 따르면 그래프 탐색 장치는, 통신부, 저장부, 상기 통신부 및 상기 저장부와 동작 가능하게 연결되는 프로세서를 포함하고, 상기 프로세서는, 사용자 기기로부터 그래프 데이터를 수신하고, 그래프의 노드들 중 하나를 시작 노드인 제1 노드로 결정하고, 상기 제1 노드의 값을 큐(Queue)에 저장하고, 상기 제1 노드의 인접 노드 중 적어도 하나를 탐색 노드인 제2 노드로 결정하고, 상기 큐에 저장된 값 및 상기 제2 노드의 값을 기초로 상기 제2 노드에 대한 상기 큐의 저장 여부를 판단하도록 구성된다.

Inventors

  • 이임영
  • 윤성철

Assignees

  • 순천향대학교 산학협력단

Dates

Publication Date
20260506
Application Date
20241028

Claims (12)

  1. 통신부; 저장부; 상기 통신부 및 상기 저장부와 동작 가능하게 연결되는 프로세서를 포함하고, 상기 프로세서는, 사용자 기기로부터 그래프 데이터를 수신하고, 그래프의 노드들 중 하나를 시작 노드인 제1 노드로 결정하고, 상기 제1 노드의 값을 큐(Queue)에 저장하고, 상기 제1 노드의 인접 노드 중 적어도 하나를 탐색 노드인 제2 노드로 결정하고, 상기 큐에 저장된 값 및 상기 제2 노드의 값을 기초로 상기 제2 노드에 대한 상기 큐의 저장 여부를 판단하도록 구성된, 그래프 탐색 장치.
  2. 제1항에 있어서, 상기 그래프 데이터는, 그래프, 상기 그래프의 구조 데이터, 탐색 거리 데이터를 포함하도록 구성된, 그래프 탐색 장치.
  3. 제1항에 있어서, 상기 프로세서는, 상기 큐에 저장된 값의 개수가 임계값 미만인 경우, 상기 제2 노드의 값을 상기 큐에 저장하도록 구성된, 그래프 탐색 장치.
  4. 제3항에 있어서, 상기 프로세서는, 상기 큐에 저장된 값의 개수가 임계값 이상인 경우, 상기 제2 노드의 값과 상기 큐에 저장된 값이 동일한지 판단하도록 구성된, 그래프 탐색 장치.
  5. 제4항에 있어서, 상기 프로세서는, 상기 제2 노드의 값과 상기 큐에 저장된 값이 동일한 경우, 상기 제2 노드의 값을 상기 큐에 저장하지 않도록 구성된, 그래프 탐색 장치.
  6. 제4항에 있어서, 상기 프로세서는, 상기 제2 노드의 값과 상기 큐에 저장된 값이 동일하지 않은 경우, 상기 제2 노드의 값을 상기 큐에 저장하도록 구성된, 그래프 탐색 장치.
  7. 프로세서에 의해 구현되는 그래프 탐색 방법으로서, 사용자 기기로부터 그래프 데이터를 수신하는 단계; 그래프의 노드들 중 하나를 시작 노드인 제1 노드로 결정하는 단계; 상기 제1 노드의 값을 큐(Queue)에 저장하는 단계; 상기 제1 노드의 인접 노드 중 적어도 하나를 탐색 노드인 제2 노드로 결정하는 단계; 및 상기 큐에 저장된 값 및 상기 제2 노드의 값을 기초로 상기 제2 노드에 대한 상기 큐의 저장 여부를 판단하는 단계를 포함하는, 그래프 탐색 방법.
  8. 제7항에 있어서, 상기 그래프 데이터는, 그래프, 상기 그래프의 구조 데이터, 탐색 거리 데이터를 포함하는, 그래프 탐색 방법.
  9. 제7항에 있어서, 제2 노드에 대한 상기 큐의 저장 여부를 판단하는 단계는, 상기 큐에 저장된 값의 개수가 임계값 미만인 경우, 상기 제2 노드의 값을 상기 큐에 저장하는 단계;를 포함하는, 그래프 탐색 방법.
  10. 제7항에 있어서, 제2 노드에 대한 상기 큐의 저장 여부를 판단하는 단계는, 상기 큐에 저장된 값의 개수가 임계값 이상인 경우, 상기 제2 노드의 값과 상기 큐의 저장된 값이 동일한지 판단하는 단계;를 더 포함하는, 그래프 탐색 방법.
  11. 제10항에 있어서, 상기 제2 노드의 값과 상기 큐의 저장된 값이 동일한지 판단하는 단계는, 상기 제2 노드의 값과 상기 큐에 저장된 값이 동일한 경우, 상기 제2 노드의 값을 상기 큐에 저장하지 않도록 하는 단계;를 포함하는, 그래프 탐색 방법.
  12. 제10항에 있어서, 상기 제2 노드의 값과 상기 큐의 저장된 값이 동일한지 판단하는 단계는, 상기 제2 노드의 값과 상기 큐에 저장된 값이 동일하지 않은 경우, 상기 제2 노드의 값을 상기 큐에 저장하는 단계;를 포함하는, 그래프 탐색 방법.

Description

그래프 탐색 장치 및 이를 이용한 방법{APPARATUS FOR NAVIGATION OF GRAPH AND METHOD USING THE SAME} 본 발명은 그래프 탐색 장치 및 이를 이용한 방법에 관한 것으로, 보다 구체적으로, 특정 노드를 번갈아가며 탐색하는 토터링 현상의 발생을 방지하는 그래프 탐색 장치 및 이를 이용한 방법에 관한 것이다. 두 그래프의 유사도를 비교하는 방법은 그래프의 구조적인 유사도를 비교하도록 AI를 학습시키고, 학습시킨 AI를 통해 그래프의 구조적 유사도를 비교하는 그래프 유사도 검사 도구가 존재하였다. 이때, 이러한 AI 기반 그래프 유사도 검사 도구는 복잡한 패턴을 효율적으로 인식할 수 있는 장점이 존재한다. 하지만, AI 기반 그래프 유사도 검사 도구는 AI 모델 학습을 위해 그래프에 대한 전처리 과정이 필요하고, 이에 따라 그래프의 구조적 정보가 손실되므로, 모델의 성능 저하를 발생시킬 수 있다. 이러한 문제를 해결하기 위해 그래프 편집 거리 알고리즘이 사용되었는데, 그래프 편집 거리 알고리즘은 두 그래프의 유사도를 비교하는데 사용되는 알고리즘 중 하나이다. 이때, 그래프 편집 거리 알고리즘은 그래프의 유사도를 비교하기 위해 그래프 탐색을 수행할 수 있다. 하지만, NP-Hard 문제로 인해 그래프 편집 거리 알고리즘을 효율적으로 사용하지 못하는 문제가 존재하였다. 도 1은 본 발명의 일실시예에 따른 그래프 탐색 장치의 블록도이다. 도 2는 본 발명의 일실시예에 따른 그래프 탐색 장치에 입력되는 그래프의 예시도이다. 도 3은 본 발명의 일실시예에 따른 그래프 탐색 장치 및 사용자 기기의 흐름도이다. 도 4는 본 발명의 일실시예에 따른 그래프 탐색 장치의 노드 탐색에 대한 순서도이다. 도 5는 본 발명의 일실시예에 따른 그래프 탐색 방법의 순서도이다. 도 6은 본 발명의 일실시예에 따른 기존 그래프 탐색 장치와 본 발명의 그래프 탐색 장치의 k-walk 생성량에 대한 그래프이다. 도 7은 본 발명의 일실시예에 따른 기존 그래프 탐색 장치와 본 발명의 그래프 탐색 장치의 k-walk 생성 시간에 대한 그래프이다. 본 명세서에 개시되어 있는 본 발명의 개념에 따른 실시예들에 대해서 특정한 구조적 또는 기능적 설명들은 단지 본 발명의 개념에 따른 실시예들을 설명하기 위한 목적으로 예시된 것으로서, 본 발명의 개념에 따른 실시예들은 다양한 형태로 실시될 수 있으며 본 명세서에 설명된 실시예들에 한정되지 않는다. 본 발명의 개념에 따른 실시예들은 다양한 변경들을 가할 수 있고 여러 가지 형태들을 가질 수 있으므로 실시예들을 도면에 예시하고 본 명세서에 상세하게 설명하고자 한다. 그러나, 이는 본 발명의 개념에 따른 실시예들을 특정한 개시형태들에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 변경, 균등물, 또는 대체물을 포함한다. 제1 또는 제2 등의 용어를 다양한 구성요소들을 설명하는데 사용될 수 있지만, 상기 구성요소들은 상기 용어들에 의해 한정되어서는 안 된다. 상기 용어들은 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만, 예를 들어 본 발명의 개념에 따른 권리 범위로부터 이탈되지 않은 채, 제1 구성요소는 제2 구성요소로 명명될 수 있고, 유사하게 제2 구성요소는 제1 구성요소로도 명명될 수 있다. 어떤 구성요소가 다른 구성요소에 "연결되어" 있다거나 "접속되어" 있다고 언급된 때에는, 그 다른 구성요소에 직접적으로 연결되어 있거나 또는 접속되어 있을 수도 있지만, 중간에 다른 구성요소가 존재할 수도 있다고 이해되어야 할 것이다. 반면에, 어떤 구성요소가 다른 구성요소에 "직접 연결되어" 있다거나 "직접 접속되어" 있다고 언급된 때에는, 중간에 다른 구성요소가 존재하지 않는 것으로 이해되어야 할 것이다. 구성요소들 간의 관계를 설명하는 표현들, 예를 들어 "~사이에"와 "바로~사이에" 또는 "~에 직접 이웃하는" 등도 마찬가지로 해석되어야 한다. 본 명세서에서 사용한 용어는 단지 특정한 실시예들을 설명하기 위해 사용된 것으로, 본 발명을 한정하려는 의도가 아니다. 단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 명세서에서, "포함하다" 또는 "가지다" 등의 용어는 설시된 특징, 숫자, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것이 존재함으로 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다. 다르게 정의되지 않는 한, 기술적이거나 과학적인 용어를 포함해서 여기서 사용되는 모든 용어들은 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자에 의해 일반적으로 이해되는 것과 동일한 의미를 가진다. 일반적으로 사용되는 사전에 정의되어 있는 것과 같은 용어들은 관련 기술의 문맥상 가지는 의미와 일치하는 의미를 갖는 것으로 해석되어야 하며, 본 명세서에서 명백하게 정의하지 않는 한, 이상적이거나 과도하게 형식적인 의미로 해석되지 않는다. 이하, 실시예들을 첨부된 도면을 참조하여 상세하게 설명한다. 그러나, 특허출원의 범위가 이러한 실시예들에 의해 제한되거나 한정되는 것은 아니다. 각 도면에 제시된 동일한 참조 부호는 동일한 부재를 나타낸다. 도 1은 본 발명의 일실시예에 따른 그래프 탐색 장치의 블록도이다. 도 1을 참조하면, 그래프 탐색 장치(100)는 통신부(110), 저장부(120) 및 프로세서(130)를 포함할 수 있다. 그래프 탐색 장치(100)는 사용자 기기(200)로부터 그래프 데이터를 수신할 수 있다. 이때, 그래프 데이터는 그래프, 상기 그래프의 구조 데이터 및 탐색 거리 데이터(k값)를 포함할 수 있다. 이때, 그래프의 구조 데이터는 그래프가 포함한 노드 및 엣지의 집합일 수 있다. 여기서, 그래프 탐색 장치(100)는 유사도 비교를 수행할 두개의 그래프를 수신할 수 있다. 또한, 적어도 두개의 그래프는 동일한 유형의 그래프일 수 있다. 여기서, 적어도 두개의 그래프는 완전 그래프 또는 연결 그래프 중 하나일 수 있지만, 이에 제한되지는 않는다. 또한, 그래프 탐색 장치(100)는 k-walk 기반의 그래프 편집 거리 휴리스틱 알고리즘을 통해 수신된 그래프에 대한 k-walk를 생성할 수 있다. 이때, 그래프 탐색 장치(100)는 자료구조인 큐(Queue)를 기초로 노드의 재탐색을 방지할 수 있다. 그래프 탐색 장치(100)는 그래프를 입력으로 k-walk 기반의 그래프 편집 거리 휴리스틱 알고리즘을 통해 k-walk를 생성할 수 있다. 이때, 그래프 탐색 장치(100)는 특정 노드에서 시작하여 k 개의 노드를 방문하는 경로를 탐색할 수 있다. 이로 인해, 그래프 탐색 장치(100)는 그래프의 구조를 탐색할 수 있다. 이때, 그래프 탐색 장치(100)는 자료 구조 중 큐(Queue)를 통해 중복 방문을 감지할 수 있다. 여기서, 그래프 탐색 장치(100)는 큐에 저장된 값의 개수가 임계값 이상인지의 판단하고, 탐색 노드 정보의 큐 저장 여부를 판단할 수 있다. 또한, 그래프 탐색 장치(100)는 큐에 저장된 값의 개수가 임계값 이상인경우, 큐의 첫번째 저장된 값과 현재 탐색 노드가 동일한 값인지 판단하여 탐색 노드 정보의 큐 저장 여부를 결정할 수 있다. 이때, 임계값은 2로 설정될 수 있으나, 이에 제한되지는 않는다 이로 인해, 본 발명은 노드 탐색 시에 큐를 이용하여 중복 방문을 감지함으로써, 토터링 현상을 방지할 수 있으므로, 불필요한 k-walk의 생성을 방지하고, 알고리즘 실행시간을 단축시킬 수 있다. 또한, 본 발명은 노드 탐색 시에 큐를 이용하여 중복 방문을 감지함으로써, 불필요한 k-walk의 생성을 방지할 수 있으므로, 그래프 편집 거리 근사값을 도출할 때 편집 비용이 추가 발생하지 않고, 근사값의 정확도를 향상시킬 수 있다. 통신부(110)는 유/무선 통신 네트워크를 통해 사용자 기기(200)와 연결되어 데이터를 송수신할 수 있다. 이때, 통신부(110)는 사용자 기기(200)로부터 그래프 탐색 요청을 수신할 수 있다. 여기서, 통신부(110)는 사용자 기기(200)로부터 앞서 언급된 요청을 수행하기 위한 데이터를 수신할 수 있다. 예를 들어, 통신부(110)는 그래프 탐색 요청을 수행하기 위해 사용자 기기(200)로부터 그래프 데이터를 수신할 수 있다. 이때, 그래프 데이터는 그래프, 상기 그래프의 구조 데이터, 탐색 거리 데이터 등을 포함할 수 있다. 또한, 통신부(110)는 사용자 기기(200)의 그래프 탐색 요청에 따른 결과값인 k-walk를 전송할 수 있다. 한편 이러한 통신부(110)는 유선 통신 포트 또는 무선 회로를 포함할 수 있다. 이때, 유선 통신 포트는 하나 이상의 유선 인터페이스, 예를 들어, 이더넷, 범용 직렬 버스(USB), 파이어 와이어 등을 포함할 수 있다. 또한, 무선 회로는 RF 신호 또는 광학 신호를 통해 외부 디아비스와 데이터를 송수신할 수 있다. 아울러, 무선 통신은 복수의 통신 표준, 프로토콜 및 기술, 예컨대 Zigbee, GSM, EDGE, CDMA, TDMA, 블루투스, Wi-Fi, VoIP, Wi-MAX, 또는 임의의 기타 적합한 통신 프로토콜 중 적어도 하나를 사용할 수 있다. 저장부(120)는 그래프 탐색 장치(100)에서 사용되는 다양한 데이터가 저장될 수 있다. 이때, 저장부(120)는 그래프 편집 거리 휴리스틱 알고리즘, 제공받은 그래프 데이터, 사용자 기기 데이터, 큐(Queue) 값 등이 저장될 수 있다. 다양한 실시예에서, 저장부(120)는 각종 데이터, 명령 및 정보를 저장할 수 있는 휘발성 또는 비휘발성 기록 매체를 포함할 수 있다. 예를 들어, 저장부(120)는 플래시 메모리 타입, 하드디스크 타입, 멀티미디어 카드 마이크로 타입, 카드 타입의 메모리(예를 들어 SD 또는 XD 메모리 등), 램, SRAM, 롬, EEPROM, PROM, 네트워크 저장 스토리지, 클라우드, 블록체인 데이터베이스 중 적어도 하나의 타입의 저장매체를 포함할 수 있다. 프로세서(130)는 통신부(110) 및 저장부(120)와 연결되어 그래