디지털 라이브러리[ 검색결과 ]
노드 사상 정보를 이용한 효과적인 그래프 편집 거리 학습 모델
http://doi.org/10.5626/JOK.2025.52.1.88
그래프 편집 거리(GED, Graph Edit Distance)는 그래프 사이의 유사도를 정량화하기 위한 가장 대표적인 방법이다. 그러나 정확한 GED 계산은 NP-Hard 문제로 많은 계산 비용을 필요로 한다. 따라서 최근 GED 근삿값을 예측하는 많은 딥러닝 모델들이 제안되었다. 하지만 기존 모델들은 상대 그래프와의 연관 관계를 부분적으로 고려함에 따라 근삿값의 오차가 크고, 노드 매칭 정보를 고려하지 않아 예측한 근삿값에 대한 설명력이 부족한 문제가 있다. 본 논문에서는 두 그래프의 노드 레벨 임베딩을 통해 사상 행렬을 학습하여 GED 근삿값의 설명력을 제공하며 학습 과정에서의 정보 손실을 최소화 하여 보다 정확한 GED를 예측하는 모델을 제안한다. 실험을 통해 제안한 모델이 기존 모델들보다 더 정확하게 GED를 예측하는 것을 보인다.
최적 속성 할당을 이용한 효율적인 다중 속성 유사 레코드 검색 기법
http://doi.org/10.5626/JOK.2019.46.2.193
본 논문은 다중 속성 데이터로 구성된 레코드에 대한 유사 검색 문제를 다룬다. 데이터들 간의 유사도 측정에 사용되는 기존의 유사도 측정 함수들은 레코드의 각 속성들에 대한 유사성을 측정할 수 없으므로 정확한 결과를 얻기 어렵다. 이러한 문제점을 해결하기 위하여 본 논문은 레코드의 속성들에 대한 유사성을 고려하여 레코드 간의 유사성을 측정하는 레코드 유사도를 제안한다. 또한 주어진 레코드 유사도 임계값에 대한 질의의 후보를 효과적으로 생성하는 필터링 기법을 제안하며, 후보가 질의에 대한 답이 될 수 있는 지를 확인하는 효율적인 검증 기법을 제안한다. 그리고 실험을 통하여 제안하는 기법들이 정확하고 효율적으로 유사한 레코드들을 검색하는 것을 보인다.
가변길이 그램의 역리스트 생성을 이용한 효율적인 유사 문자열 검색 기법
유사 문자열 검색을 위해 기존의 기법들은 우선 후보 문자열 집합을 생성한 후에 후보 문자열을 검증하는 방법을 사용한다. 이때, 유사 문자열 검색의 성능을 결정짓는 가장 중요한 요소는 후보 생성방법이다. 기존의 기법들은 질의 문자열로부터 고정길이 q-그램들을 선택하고, 선택된 q-그램에 해당하는 역리스트를 이용해 후보 문자열을 생성한다. 본 논문에서는 질의 문자열 내의 가변길이 그램들을 사용하여 후보 문자열을 생성할 수 있는 기법과 질의 문자열로부터 최적의 가변길이 그램들의 조합을 선택하는 동적 프로그래밍 알고리즘을 제안한다. 실험을 통해 제안하는 기법이 기존의 기법들 보다 유사 문자열 검색의 성능을 향상시킴을 보인다.
유사도 검색을 위한 데이터 재배열을 이용한 공간 효율적인 역 색인 기법
유사도 검색에서는 효율적으로 유사성을 만족하는 문자열을 찾기 위해서 데이터에 대한 역 색인을 구축하여 이용한다. 일반적으로 기존의 기법들은 빠른 응답속도의 질의처리를 위해서 역 색인을 메모리에 상주시킨다. 하지만 구축된 역 색인은 그 크기가 매우 크다는 문제점을 가지고 있다. 따라서 데이터의 크기가 매우 큰 경우나 자원이 제약적인 환경에서는 역 색인을 이용한 질의처리가 불가능할 수 있다. 본 논문에서는 동일한 q-그램을 포함하는 문자열들이 서로 인접한 위치가 되도록 재배치시킨 후 해당 문자열들을 범위로 표현한다. 실험을 통하여 질의처리의 성능을 희생하지 않으면서도 색인의 크기가 줄어드는 것을 보인다.
