A safe-region approach to a moving k-RNN queries in a directed and Dynamic road network
- 주제(키워드) Final dissertation
- 발행기관 아주대학교
- 지도교수 Tae-Sun Chung
- 발행년도 2015
- 학위수여년월 2015. 8
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000020191
- 본문언어 영어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
The advancement of Wi-Fi and GPS technologies contribute a lot to location-based services (LBSs) that deliver services based on the geographic location. One of the most popular LBS applications is a moving k-range nearest neighbor (MkRNN) search. In road networks, a moving k-range nearest neighbor (kRNN) queries locate the k-NN for all the points that are found on the road segments, in a given spatial region defined by the user, based on the network distance. This is a significant task because the user’s location information may be inaccurate; furthermore, users may be unwilling to reveal their exact location for privacy reasons. Therefore, under this type of specific situation, evaluating the query results at each timestamp will create significant burden for the client. We therefore propose an efficient approach for computing a safe segment region and the safe exit points of a moving k-range nearest neighbor (MkRNN) query in a directed and dynamic road network. The safe region of a query is an area where the query result remains unchanged, so that the client is not required to evaluate the query answer returned by the location-based server (LBS) within the safe segment region. In addition, our safe-region-based query processing algorithm is designed for a directed and road network, in which each road network has exactly one defined direction and the network distances are not symmetric and dynamic road network, in which the time elapsed to travel each road segment, differs based on the traffic condition at some particular time. In contrast, previous kRNN research has produced algorithms that operate only in undirected road networks.
more목차
Contents
1. Introduction 1
2. Background and related works 4
2.1 Classification of queries 6
2.2 Evaluation of k-Range Nearest Neighbor 7
2.3 Related Work 12
3. Preliminaries and problem definition 14
3.1 Definitions and notations 15
3.2 Problem Definition 17
4. Safe region based k-RNN query technique 18
4.1 Overview of the query technique 19
4.2 Computation of safe segment for inside road segments 19
5. Performance study 26
5.1 Experimental settings 26
5.2 Experimental results 28
6. Conclusion 32
3.1 REFERENCES 32
