DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Chung, Chin-Wan | - |
dc.contributor.advisor | 정진완 | - |
dc.contributor.author | Lee, Kyoung-Won | - |
dc.contributor.author | 이경원 | - |
dc.date.accessioned | 2015-04-23T07:06:23Z | - |
dc.date.available | 2015-04-23T07:06:23Z | - |
dc.date.issued | 2013 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=566505&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/197099 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 웹사이언스공학전공, 2013.8, [ iv, 27 p. ] | - |
dc.description.abstract | 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. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | direction-aware | - |
dc.subject | query optimization | - |
dc.subject | 역최근접 질의 | - |
dc.subject | 사용자 방향성 | - |
dc.subject | reverse nearest neighbor | - |
dc.subject | 질의 최적화 | - |
dc.title | Direction-aware bichromatic reverse k nearest neighbor queries and an efficient method for the queries processing | - |
dc.title.alternative | 방향성을 고려한 이종데이터 상의 역최근접 질의와 효율적인 질의 처리 기법 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 566505/325007 | - |
dc.description.department | 한국과학기술원 : 웹사이언스공학전공, | - |
dc.identifier.uid | 020114432 | - |
dc.contributor.localauthor | Chung, Chin-Wan | - |
dc.contributor.localauthor | 정진완 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.