Efficient Processing of Proximity-Aware Spatial Queries in Road Networks
Efficient Processing of Proximity-Aware Spatial Queries in Road Networks
- 주제(키워드) Computer Engineering
- 발행기관 아주대학교
- 지도교수 Tae-Sun Chung
- 발행년도 2017
- 학위수여년월 2017. 8
- 학위명 박사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000025915
- 본문언어 영어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
With the explosive growth in spatial information and emergence of new technologies, a number of applications such as GIS, VLSI and decision support systems are exploiting the location dimension to provide services. Moreover, the rapid technological advances in wireless networks and development of smartphones have popularized location-based services. Majority of these applications uses proximity-aware spatial queries to provide services. A proximity-aware spatial queries computes the results based on the closeness of objects. Reverse k nearest neighbor queries (RkNN), top-k spatial preference queries and top-k spatial keyword queries are some of the important proximity-aware spatial queries. In this thesis, we provide efficient techniques for processing these queries in road networks. In this thesis, we present efficient techniques to continuously monitor RkNN queries where both query and data objects are moving. The main challenge in continuous RkNN queries is to maintain the freshness of query results because results may nullify due to movement of query or data objects. We propose a safe exit-based algorithm called CORE-X for efficiently computing the safe exit points of both query and data objects. Within the safe region, the query result remains unchanged provided that query and data objects remains inside their respective safe regions. Furthermore, we also provide efficient solution for processing RkNN queries in dynamic road networks where the network distance changes depending on the traffic conditions. Top-k preference queries are crucial for a wide range of location based services such as hotel browsing and apartment searching. In recent years, a lot of research has been conducted on processing of top-k spatial preference queries in Euclidean space. While few algorithms study top-k preference queries in road networks, they all focus on undirected road networks. To the best of our knowledge, we are the first to investigate the problem of processing the top-k spatial preference queries in directed road networks where each road segment has a particular orientation. To the best of our knowledge, this is the first study to address this problem. We propose a pruning and grouping of feature objects to reduce the number of feature objects which improve the query processing time. Additionally, we present an efficient algorithm called TOPS that can process top-k spatial preference queries in directed road networks. Top-k keyword queries can be used for a wide range of applications in recommendation systems and decision support systems. Several solutions have been proposed for top-k spatial keyword queries in Euclidean space. However, few algorithms study top-k keyword queries in undirected road networks where every road segment is undirected. Even worse, insufficient attention has been given to the processing of keyword queries in directed road networks where each road segment has a particular orientation. In this study, we are the first to address this issue and proposed efficient techniques for processing top-k spatial keyword queries in directed road networks. All the approaches we propose have been validated through extensive experimental evaluation on real road networks. The results we obtained show that our proposed techniques significantly improves the performance of these proximity-aware spatial queries in road networks.
more목차
CHAPTER 1. Introduction 1
1.1 Motivation 1
1.2 Contributions 3
1.3 Thesis Outline 5
CHAPTER 2. Background 6
2.1 Spatial Databases 6
2.1.1 Modeling 6
2.2 Proximity-Aware Spatial Queries 9
2.3 Related Work 12
2.3.1 Reverse Nearest Neighbor Queries 13
2.3.2 Top-k Spatial Preference Queries 16
2.3.3 Top-k Spatial Keyword Queries 19
CHAPTER 3. Various Proximity-Aware Spatial Queries in Road Networks 21
3.1 Processing Reverse k Nearest Neigbhor Queries 21
3.1.1 Overview 21
3.1.2 Preliminaries 25
3.1.3 Safe Exit Algorithm for Moving RkNN Queries and Moving Objects 29
3.1.4 RkNN Queries in Dynamic Road Networks 49
3.2 Top-k Spatial Preference Queries in Directed Road Networks 52
3.2.1 Overview 52
3.2.2 Preliminaries 54
3.2.3 Pruning and Grouping 58
3.2.4 Top-k Spatial Prefernce Query Algorithm 73
3.3 Top-k Spatial Keyword Queries in Directed Road Networks 82
3.3.1 Overview 82
3.3.2 Preliminaries 84
3.3.3 Query Processing System 86
CHAPTER 4. Performance Evaluation 91
4.1 Performance Evaluation of CORE-X 91
4.1.1 Experimental Settings 91
4.1.2 Experimental Results for Static Road Networks 93
4.1.3 Experimental Results for Dynamic Road Networks 97
4.2 Performance Evaluation of TOPS 101
4.2.1 Experimental Settings 102
4.2.2 Experimental Results for Query Processing Time 103
4.2.3 Experimental Results for Materialization and Incremental Maintenance Costs 108
4.3 Performance Evaluation of eSPAK 111
4.3.1 Experimental Settings 111
4.3.2 Experimental Results 113
CHAPTER 5. Conclusion 117
References 119
Publications List 127
