효율적인 최근접 질의 처리를 위한 Voronoi 다이어그램 기반 그리드 검색 구조 (A Voronoi Diagram-Based Grid Structure for Efficient Nearest Neighbor Query Processing)

서지정보

· 발행기관 : 한국컴퓨터정보학회
· 수록지 정보 : 한국컴퓨터정보학회논문지 / 13권 / 1호 / 11 ~ 20페이지
· 저자명 : 권동섭

초록

최근접 질의(nearest-neighbor query)는 멀티미디어 시스템이나 GIS 시스템과 같은 여러 가지 응용 분야에서 사용되는 중요한 질의 처리 기법 중 하나이다. 최근접 검색 기법들을 위한 다양한 연구가 제안되었으나 이러한 기법들은 질의 수행 시 데이터를 검색하여 최근접 질의를 처리하므로 성능의 한계가 있었다. 본 논문에서는 정적인 데이터에 대하여 Voronoi 다이어그램을 이용한 전처리를 통하여 최근접 질의의 결과를 미리 계산하고 이 결과를 그리드 기반 검색 구조를 이용하여 저장하는 기법을 제안한다. 이 기법은 데이터 자체를 색인하는 기존의 기법과는 달리, 질의의 결과를 미리 색인하므로 대량의 데이터에 대해서도 기존의 기법보다 빠르게 최근접 질의를 처리할 수 있다.

영어초록

Nearest-neighbor searches are essential operations in various applications such as multimedia systems and GIS systems. Although numbers of research works for nearest-neighbor search have been proposed, they have a limitation on the performance since they process queries on the fly with indexes on data. This paper proposes a new nearest-neighbor search algorithm based on a grid-based data structure, which preprocesses and stores the result of nearest-neighbor queries using Voronoi diagrams over static data. While traditional techniques try to index data itself, the proposed technique attempts to index the result of the queries. Therefore, it performs nearest-neighbor queries more efficiently.

참고자료

· 없음