다차원 데이터공간에서 가장 가까운 이웃의 탐색을 위한 프레임워크

전문가 제언

○ 가장 가까운 이웃 탐색(nearest neighbor search: nn-탐색)은 거리공간(metric space)에서 가까운 점을 발견하는 최적 문제다. 이는 거리공간 안에 주어진 점집합에서 질의(query) 점으로부터 가장 근접한 점을 찾는 프로세스로서 유사탐색(similarity search)에 속한다.

○ 유사탐색은 컨텐츠 기반 영상 검색, 시계열, 공간 데이터베이스, 데이터 마이닝 및 멀티미디어 데이터베이스와 같은 응용분야에 널리 사용된다. 유사탐색의 유용한 방법은 객체를 특징 벡터로 사상하고 벡터들이 존재하는 다차원 공간에서 근접 이웃 질의로서 탐색을 모델화하는 것이다.

○ 이 프로세스의 중요한 핵심으로는 벡터들 사이에 근접성을 측정하는 데 사용될 거리함수를 결정하는 일과 탐색을 촉진할 인덱스 방법을 찾는 일이다. 특히 멀티미디어 데이터베이스에서의 유사탐색에 있어서는 모든 데이터베이스 객체마다 그의 특징 벡터인 다차원 공간(특징 공간)의 점을 찾는 프로세스와 이 특징 공간에서의 fs-거리(feature space distance)와 인덱스의 선택이다.

○ 이 논문에서는 특징 공간을 조직하기 위하여 사용될 거리와 인덱스 구조의 선택에서 사용자에게 높은 자유도를 제공하는 유사검색을 수행할 프레임워크를 제안한다. 특히 다차원 사각형 영역에서 특징 공간을 구분할 인덱스 구조와 함께 사용될 수 있는 거리 함수에 근사한 함수를 도입한다. 또한 프레임워크의 응용성과 총 경비를 보여주는 사용 사례와 실험 결과가 제시된다.

○ 디지털 영상이나 게임과 같은 멀티미디어 데이터 공간에서 유사탐색은 유용한 기능으로 웹 환경에서 널리 사용되는 기술이다. 이는 PC의 정보처리 능력과 하드웨어의 발전 및 초고속 인터넷 활성화와 디지털 이미지의 발전에 기인한다. 더구나 최근에 부상하고 있는 스마트폰의 영향으로 기존의 포털 환경에서 사용 중인 검색 엔진보다 더욱 진보된 앱스토어 환경에서 효율적인 유사검색 기능이 필요해질 것으로 여겨지므로 이 분야에 대한 연구도 앞으로 기대된다.

저자

Manuel Barrena, Elena Jurado, Pablo Marquez-Neila, Carlos Pachon

자료유형

학술정보

원문언어

영어

기업산업분류

정보통신

연도

2010

권(호)

69

잡지명

Data & Knowledge Engineering

과학기술
표준분류

정보통신

페이지

116~136

분석자

김*기

분석물

• 다차원 데이터공간에서 가장 가까운 이웃의 탐색을 위한 프레임워크.pdf [415,338 byte]

이미지변환중입니다.