Moving View Field Nearest Neighbor Queries
- 주제(키워드) Nearest neighbor , Spatial database , Computational geometry , Spatial query
- 발행기관 고려대학교 대학원
- 지도교수 정연돈
- 발행년도 2017
- 학위수여년월 2017. 2
- 학위구분 석사
- 학과 대학원 컴퓨터학과(정보대학)
- 세부전공 소프트웨어 전공
- 원문페이지 54 p
- 실제URI http://www.dcollection.net/handler/korea/000000073275
- 본문언어 한국어
- 제출원본 000045897636
초록/요약
In this thesis, we introduce a new type of moving nearest neighbor query expanding the view field nearest neighbor query. The query, named moving view field nearest neighbor (MVFNN), finds the nearest object in the query's view field continuously with the consideration of changes of the query's location and view field. To improve the query processing efficiency, we introduce a novel notion of two-way safe boundaries. The two-way safe boundaries consist of (1) geographical safe boundary and (2) angular safe boundary. Although a query has moved and view field of the query has changed, the re-computation of the query is not necessary if the query's new location is located in the geographical safe boundary and the query's view field is included within the angular safe boundary. Then, we propose an efficient MVFNN query processing method using two-way safe boundaries. The performance of our proposed MVFNN query processing method is evaluated by conducting a series of simulations.
more목차
1 Introduction 1
2 Related Work 6
2.1 R-tree and nearest neighbor queries 6
2.2 Moving nearest neighbor queries 7
2.3 View field nearest neighbor query 10
3 Preliminaries 12
3.1 Angular relation between two vectors 12
3.2 Problem Statement 13
4 The Proposed Method 15
4.1 Two-way safe boundaries 15
4.1.1 Geographical safe boundary 16
4.1.2 Angular safe boundary 21
4.2 MVFNN query processing method 23
4.2.1 Initialization part 23
4.2.2 Update part 29
5 Performance Evaluation 31
5.1 Experimental settings 31
5.2 Varying density of data objects 33
5.3 Varying density of view fi eld 35
5.4 Measure the overhead of proposed method 36
6 Conclusion 41
