클라이언트가 이동하는 환경에서 효율적인 연속 k-최근접 질의 처리를 위한 색인 구조 (An Index Structure for Efficient k-NN Query Processing on the Moving Client Environments)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 데이타베이스연구 / 26권 / 2호 / 79 ~ 90페이지
· 저자명 : 박용훈, 서동민, 윤종현, 신재룡, 최길성, 유재수

초록

최근 위치 인식 기술과 휴대 장치의 발달로 인해 이동하는 객체를 기반으로 하는 위치 기반 서비스(Location Based Service, LBS)의 관심이 점점 증가하고 있고 그에 관련된 연구들이 활발하게 진행되고 있다. 본 논문에서는 고정된 객체와 이동하는 질의 환경에서 연속 k-최근접 질의를 효율적으로 수행하는 색인구조인 ISR-tree(Incremental Search R-tree)를 제안한다. 이 구조는 단말 노드에서 이웃 노드들의 정보를유지하여 k-최근접 질의 처리시 중간 노드에 대한 탐색횟수를 감소시켰을 뿐만 아니라 연속 질의 처리를 위한질의 재수행시 중간 노드를 탐색하지 않는다. 제안하는 기법의 우수성을 평가하기 위해 R-tree와의 비교를수행하였다.

영어초록

The interest of Location-Based Services (LBS) has highly increased according to the development of location aware techniques and mobile devices and also the researches on LBS have been progressed in recent years. In this paper, we propose ISR-tree (Incremental Search R-tree) which processes continuous k-NN queries efficiently in the environment composed of static objects and moving clients submitting queries. In ISR-tree, the leaf-nodes maintain the entries of their neighbor nodes and the entries help to find the neighbor leaf-nodes without visiting internal nodes when k-NN queries are processed. As a result, ISR-tree saves the cost to visit internal nodes. We prove the superiority of ISR-tree through the comparison with previous works.

참고자료

· 없음