MBR-Safe 변환: 유사 시퀀스 매칭에서 고차원 MBR의 저차원 변환

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 데이타베이스 / 33권 / 7호 / 693 ~ 707페이지
· 저자명 : 문양세

초록

유사 시퀀스 매칭 방법은 다차원 색인을 사용한 검색 속도의 향상을 위해, 많은 수의 고차원 시퀀스를 저차원 변환한 후 이들 변환된 시퀀스들을 포함하는 저차원 MBR을 구성한다. 본 논문에서는 고차원 MBR 자체를 직접 저차원 MBR로 변환하는 정형적인 방법을 제안하고, 이를 사용하면 유사 시퀀스 매칭에서 필요한 저차원 변환 횟수를 획기적으로 줄일 수 있음을 보인다. 이를 위해, 우선 변환의 MBR-safe 개념을 정형적으로 제안한다. 어떤 변환이 MBR-safe하다 함은 고차원 MBR을 직접 변환한 저차원 MBR이 개별 고차원 시퀀스가 변환된 저차원 시퀀스를 모두 포함함을 의미한다. 다음으로, 기존 저차원 변환 중에서 가장 널리 사용되는 DFT와 DCT에 대해 각각 MBR-safe 변환을 제안한다. 먼저, 기존 DFT와 DCT가 MBR-safe하지 않음을 보이고, DFT와 DCT를 확장한 mbrDFT와 mbrDCT를 각각 정의한다. 그리고, 이들 mbrDFT와 mbrDCT가 MBR-safe함을 정형적으로 증명한다. 또한, mbrDFT(혹은 mbrDCT)가 고차원 MBR을 저차원 MBR로 직접 변환하는 DFT(혹은 DCT) 기반의 최적 MBR-safe 변환임을 증명한다. 분석과 실험 결과, 제안한 mbrDFT 및 mbrDCT를 사용하면 저차원 변환 횟수를 획기적으로 줄이고 성능을 크게 향상 시킨 것으로 나타났다. 이 같은 결과를 볼 때, 본 논문에서 제시한 MBR-safe 개념은 고차원 MBR의 저차원 변환이 필요한 많은 응용에 활용될 수 있는 유용한 연구 결과라 사료된다.

참고자료

· 없음