數奇雜記  

기술보고서 "고유 색인어 수와 문서적재 및 검색 시간에 관한 고찰" 
김진숙 기술보고서 2003-08-10 (2007년 6월 21일 재수정)

고유 색인어 수와 문서적재 및 검색 시간에 관한 고찰

본 문서는 문서 데이터베이스에서 출현하는 고유색인단위의 숫자와 적재 및 검색 시간에 대해 살펴보고자 한다. 일반적으로 정보검색 대상 문서의 경우에는 구분되는 단위(DBMS의 field나 IR 분야의 section 단위) 각각에 대해 미리 정해진 색인 방법이 지정되므로 일반사용자의 경우에는 DB 전체에서 추출되는 색인어의 수에 대해서 신경을 쓸 이유는 없다. 다만 이 문서는 고유한 색인어의 수가 문서를 적재하고 검색하는 데 미치는 영향을 살펴봄으로써 향후 이미지 및 멀티미디어 처리 등과 같이 색인의 단위가 모호한 경우 새로운 색인 기법을 연구하고자 하는 이들에게 하나의 척도로써 도움이 되었으면 한다.

이 실험에 사용된 문서집합은 PIR-NREF라는 단백질 서열 데이터베이스이다. PIR-NREF는 미국의 조지타운대학교 Protein Information Resource(PIR)에서 구축하고 있는 세계 최대의 단백질 서열 데이터베이스이다. URL은 http://pir.georgetown.edu/pirwww/search/pirnref.shtml 이다. 실험에 사용된 데이터는 FASTA 포맷으로 배포되는 버전을 사용했으며 총 127만여건으로 구성되어 있다. 실험은 Pentium Xeon 2.4GHz Dual CPU, 메모리 4GB, Ultra160 SCSI HDD를 장착한 리눅스 장비에서 수행하였다. 서열 부분을 색인하기 위해 5개의 색인방식을 구현하고 적재 및 검색 속도를 실험하였다. 실험결과는 그림1과 같다.

그림1에서 Loading/Indexing time은 단위가 시간이며 편의상 실제 시간의 2배를 표시하였다. 검색시간은 초단위이다. 약간의 편차는 있으나 고유색인어의 수와 적재시간은 대략 비례하며 검색시간과는 반비례하는 것을 볼 수 있다. 표 1에서는 그림 1의 데이터를 숫자로 표시하였다.

색인방법은 P, N-gram 길이, 아미노산 알파벳 크기의 순서로 표기하였다. 자연계에는 총 21개의 아미노산이 존재하는 데 유사한 그룹들을 묶어서 하나의 아미노산으로 처리하면 13개의 그룹으로 구분할 수 있다. 따라서 색인에서는 아미노산 전체를 사용하는 tetra-gram 색인 일 경우에는 P421, 13개의 아미노산 그룹을 사용할 경우에는 P413이 된다. N그램의 알파벳의 크기가 다르므로 이론적인 고유 색인어의 수는 N그램의 길이와 알파벳의 크기로 결정된다 (표 1의 이론적인 고유색인어수 참조). 하지만 실제로 나타나는 색인어의 빈도는 이보다는 조금 작다 (표 1의 실제 고유색인어 수 참조).

그림 1과 표 1에서 보듯이 적재시간은 고유 색인어의 수에 비례하여 증가하지만 검색시간은 반비례하는 것을 알 수 있다.

그림 1과 표 1은 속도 측면에서의 실험결과를 보여주었다. 그림 2는 100여 개의 질의 서열을 대상으로 한 정확도-재현율 실험결과이다. 각 질의 서열은 100~500개 정도의 아미노산 서열을 가지는 단백질들로 선정하였다. 또한 서열 정렬 소프트웨어인 BLAST의 align 결과를 정답 서열로 선정하였다. KRISTAL의 벡터공간 모델을 사용하여 질의 서열에 대한 검색결과와 BLASTP의 검색결과를 비교함으로써 11점 정확도 그래프를 얻었다.

그림 2에서 보여주는 바와 같이 고유 색인어의 수가 많을수록 검색성능은 더 좋아지는 것을 여기서도 알 수 있다. 성능이 가장 뛰어난 P521 색인방법의 경우에는 상위 10% 내에서 BLAST와 88% 이상 동일한 검색 결과를 보여준다.

이 실험을 통해 실제로 단백질 서열 색인 및 검색 방법론을 제공하기 위해 KristaL 정보검색관리엔진 에서는 P521 색인방법 (penta-gram과 21개 아미노산 전체 사용)을 단백질 서열 색인 방법론으로 채택하였다.

문의나 조언은 메일로... | 저작권처음으로