서지주요정보
Direction-aware bichromatic reverse k nearest neighbor queries and an efficient method for the queries processing = 방향성을 고려한 이종데이터 상의 역최근접 질의와 효율적인 질의 처리 기법
서명 / 저자 Direction-aware bichromatic reverse k nearest neighbor queries and an efficient method for the queries processing = 방향성을 고려한 이종데이터 상의 역최근접 질의와 효율적인 질의 처리 기법 / Kyoung-Won Lee.
저자명 Lee, Kyoung-Won ; 이경원
발행사항 [대전 : 한국과학기술원, 2013].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8025670

소장위치/청구기호

학술문화관(문화관) 보존서고

MWST 13003

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

This thesis presents a novel type of queries in spatial databases, called the direction-aware bichromatic reverse k nearest neighbor(DBRkNN) queries, which extend the bichromatic reverse nearest neighbor queries. Given two disjoint sets, P and S, of spatial objects, and a query object q in S, the DBRkNN query returns a subset P` of P such that k nearest neighbors of each object in P` include q and each object in P` has a direction toward q within a pre-defined distance. I formally define the DBRkNN query, and then propose an efficient algorithm, called DART, for processing the DBRkNN query. My method utilizes a grid-based index to cluster the spatial objects, and the B+tree to index the direction angle. I adopt a filter-refinement framework that is widely used in many algorithms for reverse nearest neighbor queries. In the filtering step, DART eliminates all the objects that are away from the query object more than the pre-defined distance, or have an invalid direction angle. In the refinement step, remaining objects are verified whether the query object is actually one of the k nearest neighbors of them. From extensive experiments, I show that DART outperforms an R-tree-based naive algorithm in both indexing time and query processing time.

본 학위논문에서는 방향성을 고려하는 이종데이터 상의 역최근접 질의를 제안한다. 공간 데이터 집합 P와 S, S 집합에 속해있는 질의 객체 q가 주어졌을 때, DBRkNN 질의는 q 객체를 최대 k번째 최근접 객체로 여기고 방향이 q 객체로 향해있으며 사전에 정의된 거리 내에 소유하는 모든 부분집합 P`을 반환한다. 본 학위논문에서는 DBRkNN 질의를 정의하고, DART라는 DBRkNN 질의를 처리하기 위한 효율적인 알고리즘을 제안한다. DART는 그리드 기반의 색인을 하여 공간 객체들을 클러스터하고 B+트리를 이용하여 방향을 색인한다. 역최근접 질의 처리에서 자주 사용되는 Filter-refinement 프레임워크를 적용하였다. Filtering 단계에서는 사전에 정의된 거리보다 질의 객체로부터 멀리 떨어진 객체를 제외하고, 또한 올바르지 않은 방향을 가진 객체도 제외한다. Refinement 단계에서는 남겨진 객체들에 대해서 실제로 각 객체가 질의 객체를 최대 k번째 최근접 객체로 여기는지를 확인한다. 실험을 통해서 DART 알고리즘이 R 트리 기반의 나이브 알고리즘보다 색인과 질의 처리부분에서 더 효율적임을 보였다.

서지기타정보

서지기타정보
청구기호 {MWST 13003
형태사항 iv, 27 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 이경원
지도교수의 영문표기 : Chin-Wan Chung
지도교수의 한글표기 : 정진완
학위논문 학위논문(석사) - 한국과학기술원 : 웹사이언스공학전공,
서지주기 References : p. 21-23
주제 reverse nearest neighbor
direction-aware
query optimization
역최근접 질의
사용자 방향성
질의 최적화
QR CODE qr code