Direction-aware bichromatic reverse k nearest neighbor queries and an efficient method for the queries processing = 방향성을 고려한 이종데이터 상의 역최근접 질의와 효율적인 질의 처리 기법

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 366
  • Download : 0
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.
Advisors
Chung, Chin-Wanresearcher정진완
Description
한국과학기술원 : 웹사이언스공학전공,
Publisher
한국과학기술원
Issue Date
2013
Identifier
566505/325007  / 020114432
Language
eng
Description

학위논문(석사) - 한국과학기술원 : 웹사이언스공학전공, 2013.8, [ iv, 27 p. ]

Keywords

direction-aware; query optimization; 역최근접 질의; 사용자 방향성; reverse nearest neighbor; 질의 최적화

URI
http://hdl.handle.net/10203/197099
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=566505&flag=dissertation
Appears in Collection
WST-Theses_Master(석사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0