An Efficient Algorithm for Computing Safe Exit Points of Moving Nearest Neighbor Queries in Directed Road Networks
- 발행기관 Ajou University, Computer Engineering
- 지도교수 Tae-Sun Chung
- 발행년도 2014
- 학위수여년월 2014. 6
- 학위명 석사
- 학과 및 전공 Graduate School 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000017350
- 본문언어 영어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
Moving nearest neighbor queries in road networks have been studied extensively in recent years. However, at present there is still a lack of algorithms for moving queries in a directed road networks. In this thesis, we introduce a new algorithm called the Directed Safe Exit Algorithm (DSEA), which can efficiently compute the safe exit points of a moving nearest neighbor (NN) query on directed road networks where each road segment has a particular orientation. The safe region of a query is an area where the query result remains unchanged, provided that the query remains inside the safe region. At each safe exit point, the safe region of a query and its non-safe region meet so that a set of safe exit points represents the border of the safe region. Before reaching a safe exit point, the client (query object) does not have to request the server to re-evaluate the query. This significantly reduce the server processing cost and the communication costs between the server and moving clients. Our experimental results demonstrate that DSEA significantly outperforms a conventional solution in terms of both computational and communication costs.
more목차
ACKNOWLEDGEMENTS I
ABSTRACT II
TABLE OF CONTENTS III
LIST OF FIGURES IV
LIST OF TABLES V
LIST OF ACRONYMS V
1.INTRODUCTION 1
2.BACKGROUND AND RELATED WORKS 4
2.1 BACKGROUND 4
2.2 PROBLEM FORMULATION 7
2.3 RELATED WORK 8
3.PROPOSED IDEA 11
3.1 DIRECTED SAFE EXIT ALGORITHM 11
3.2 COMPUTATION OF THE SAFE EXIT POINTS FOR THE EXAMPLE 21
4.PERFORMANCE EVALUATION 27
4.1 EXPERIMENTAL SETTINGS 27
4.2 EXPERIMENTAL RESULT 28
5.CONCLUSION 35
6.REFERENCES 35
