A Safe exit based approach for Reverse Nearest Neighbors in Directed Road Networks
- 주제(키워드) A Safe exit based approach for Reverse Nearest Neighbors in Directed Road Networks
- 발행기관 아주대학교
- 지도교수 Tae-Sun Chung
- 발행년도 2016
- 학위수여년월 2016. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000021519
- 본문언어 영어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
The world has seen rapid growth in GPS-based devices and location aware systems in the past decade or so which has contributed a lot to location based services (LBSs) that deliver services based on the geographic location. One of the popular LBS application is continuous k reverse nearest neighbors (RkNN) in directed road network, where a road segment can have a particular orientation. A RkNN query returns a set of data objects that take query point as their nearest neighbor. A challenging task in this type of query is to keep the result fresh as the query moves freely in the road network. This is a significant task as evaluating a query at timestamps will create a significant burden on the server and communication costs will be much higher. In order to address this problem, we propose an efficient approach for computing the safe region and safe exit points for moving RkNN query in a directed road network. A safe region of query is a location in the road network where the answer objects of the query remains unchanged. A safe exit point is a point where safe region and non-safe region meet and as long as the query has not passed the safe exit point, it is guaranteed that the query result is valid hence no communication is required between the server and the client. In contrast, previous RkNN algorithms only work for undirected road networks or Euclidian space.
more목차
1. Introduction 1
2. Background and Related Work 4
2.1 Background 4
2.1.1 Commonly Used Terms 4
2.1.2 Classification of Queries 5
2.2 Preliminaries 6
2.2.1 Road Network 6
2.2.2 Nodes Classification 7
2.2.3 Sequences 7
2.3 Related Work 7
2.3.1 Reverse Nearest Neighbor in Euclidean and Road Networks 7
2.3.2 Limitations of Undirected Algorithms in Directed Graphs 9
2.3.3 Problem Formulation 11
3. SWIFT Algorithm 12
3.1 Pruning Rules 12
3.1.1 Lemma 1. 12
3.1.2 Lemma 2. 12
3.2 Overview of SWIFT 13
3.3 Running Example 15
3.4 Extension of SWIFT to continuous directed road networks 17
3.4.1 Influence Region 17
3.4.2 Influence Region in Running Example 19
3.4.3 Safe Exit 20 4. Simulation 22
4.1 Experimental setup 22
4.2 Results Evaluation 23
4.2.1 Effect of k on CPU time 23
4.2.2 Effect of POIs on CPU time 24
4.2.3 Effect of k on pruned nodes 25
4.2.4 Effect of speed on number of queries 26
