Efficient Algorithms for Spatial Queries over Static and Mobile Objects on Road Networks

• Material Type: 博士論文
• Title: Efficient Algorithms for Spatial Queries over Static and Mobile Objects on Road Networks
• Author/Editor: TIN NILAR WIN
• Author Heading: TIN NILAR WIN
• Publication Date: 2018
• Publication Date (W3CDTF): 2018
• Alternative Title: 道路網上の静的及び動的オブジェクトに対する空間検索の為の高効率アルゴリズム
• Periodical title: 博士論文（埼玉大学大学院理工学研究科（博士後期課程））
• Degree grantor/type: 埼玉大学
• Date Granted: 2018-09-21
• Date Granted (W3CDTF): 2018-09-21
• Dissertation Number: 甲第1102号
• Degree Type: 博士(工学)
• Conferring No. (Dissertation): 甲第1102号
• Text Language Code: eng
• Target Audience: 一般
• Note (General): type:text; Spatial database is one of the active area in database research communities since last three decades, addressing the need of spatial data management and analysis in application such as Geographic Information Systems (GIS). Due to wide availability of relatively inexpensive and compact location position devices such as hand-held Geographical Positioning Systems (GPS) devices and smart-phone, users want an access to the real-time personal information anywhere in the world. To supply the end users with required information, a service provider must collect and process the geolocation information. This service is called location-based services (LBS). LBS has recently attracted significant attention due to its potential to revolutionize the mobile communications technologies by providing a personalized and context-aware services to bring unique and broad value to the end users.There are several applications using LBS such as route assistance, tracking management, identification of objects of interest, fleet management, content management and emergency services. One of the active challenges in LBS is personalization which supports more customized and explicit services according to the users' unpredictable actions and preferences. To fulfill these requirements, we need effective and robust querying methodologies to process geographic information (so called spatial information) to utilize in the real location aware applications.To accomplish the above challenges, we studied spatial query algorithms and analyzed the performance efficiencies under various settings. More specifically, we focused for two types of queries: 1) query evaluates immediately after the query is invoked and the answer is transmitted to the user once which is called a snapshot query, and 2) query evaluates every time instant without user interference to ensure the correctness and validity of the query answer which is called a continuous query. The major challenges for these queries are focused on methods to provide an efficient query processing for either stationary or continuously moving objects with respect to the processing time, CPU time, and main memory utilization.In this thesis, we first study the snapshot query over the static data objects and query objects on several road networks. We use object of interest and data object (point) interchangeably throughout the thesis. We present an efficient solution to answer the reverse k nearest neighbor (RkNN) query using pre-computation approach. we utilize the simple materialized path view (SMPV) structure that can calculate the road network distance with speedy performance and incrementalEuclidean restriction (IER) framework to probe the fast k nearest neighbor (RkNN) query. SMPV structure is constructed by partitioning the whole data space into multiple subgraphs and creating a materialized distance tables for each subgraph. An extensive experimental study was conducted to evaluate the performance characteristics of our proposal for static RkNN query with some road networks showed that it substantially outperforms the competitive approach that do not use any precomputed distance tables. When we used SMPV framework as the underlying structure, our algorithm outperformed in processing time that was 10 to 100 times faster than competitive approach. The key characteristic of our approach is that when the data objects are distributed sparsely on the road network and the arbitrary k value (k > 1 more than one RNN objects) is large, our approach reduced the overall processing time drastically. Especially, we observed on the bichromatic RkNN query with this approach that our approach does not depend on any distribution of rival objects (∈ S) and objects of interest (∈ P) and the processing time was stable.As an expanded studies of spatial queries which evaluate continuously according to the mobile query objects have been studied in this thesis. Suppose, the query object moves freely, the query result changes over time according to the changes of query object locations which make the query processing more complicated than the processing with the static query objects. In addition, while the location of query object is changing, the frequent requests for the up-to-date result to the server occur that cause heavy workload in the server. To address this problem efficiently, an idea of safe-region is utilized. Safe-region method restricts the mobile query object to issue a query update only if mobile object leaves the region. We present how to process the spatial continuous queries effectively in two chapters (4 and 5) in this thesis. In chapter 4, we describe the continuous vicinity queries with the aid of advanced technique called safe-region. The existing approaches for the continuous queries using safe-region require long processing time to generate safe-regions. In addition, these approaches are not applicable for all types of spatial queries, thus, require different safe-region generation mechanism for different spatial queries. To overcome all these limitation, we provide a set of techniques that can generate the safe-region with less processing time and is applicable for various types of vicinity queries. According to the conducted experimental study, the results confirm the efficiency of our proposed methodologies. The detail theoretical explanation and performance study are presented in Chapter 4.The benefits of safe-region approach are maintaining the valid query answers for mobile query object if object is in safe-region and reducing the communication cost between the server and client (query object). This kind of approach is suitable for a kind of trip route planning query (TRPQ) that visits multiple data object categories and processes continuously. Generally, TRPQ requires huge processing time to retrieve the best trip route for snapshot query type. In addition, if a query object (user) is mobile, the user may sometimes deviate from the optimal route while traveling. To cope with these, generally, we can monitor and update the route either at a specified time interval or distance. However, this traditional approach is not applicable for all situation, has many restrictions on the distance and time interval, and there is deterioration in server performance as the interval is reduced. For such cases, we adopt the idea of safe-region and verify the route is optimal if the position of the current object of targeted category is in the safe-region although the user veers from the optimal route. Moreover, safe-region approach has less restrictions compared with the traditional ways.As a first attempt, we proposed a continuous TRPQ on road network using safe-region, and we investigated the generation of safe-region for TRPQ with two approaches. The first approach creates an accurate safe-region and the second approach generates an approximate safe-region. We analyzed the performance of our proposed approaches and basic algorithm in the experimental study section. Our proposed first algorithm needed long processing time when the density of the data object was high. Our second approach required less processing time. However, the size of the generated safe-region by second approach became about 3% to 7% larger than the safe-region size of first approach.In addition, we addressed the solution to solve the processing time problem of the trip route query when the distribution of densities of data object categories are substantially different for each other. For this issue, we introduced a new method which defines the sparse data category as the first visiting data category to shorten the processing time. Because the processing time has a great effect on the visiting order of the data object categories. Our proposed approach dynamically retrieves the sparse category to define the visiting order of the data categories. The theoretical explanation and performance study are presented in chapter 5.; Acknowledgment iAbstract iiiList of Figures xiiiList of Tables xvList of Abbreviations xvii1 Introduction 11.1 Querying Spatial Objects . . . . . . . . . . . . . . . . . . . . . . . . 31.1.1 Querying Spatial Object on Static Environment . . . . . . . 31.1.2 Querying Spatial Object on Dynamic Environment . . . . . 51.1.3 Spatial Queries Proposed in this Thesis . . . . . . . . . . . . 61.2 Objectives and Contributions of this Thesis . . . . . . . . . . . . . 91.2.1 Contributions on Snapshot RkNN Queries . . . . . . . . . . 101.2.2 Contributions on Continuous Vicinity Queries . . . . . . . . 101.2.3 Contributions on Trip Route Planning Queries for Stationary and Moving Objects . . . . . . . . . . . . . . . . . . . . . . 111.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Literature Review 132.1 Spatial Index Structure . . . . . . . . . . . . . . . . . . . . . . . . . 132.1.1 Indexing Methods in Spatial Database . . . . . . . . . . . . 142.2 Road Network Distance Calculation . . . . . . . . . . . . . . . . . . 182.2.1 Description of Algorithms . . . . . . . . . . . . . . . . . . . 192.3 Categories of the Spatial Queries . . . . . . . . . . . . . . . . . . . 272.3.1 Static (Snapshot) Spatial Queries . . . . . . . . . . . . . . . 282.3.2 Continuous Spatial Queries . . . . . . . . . . . . . . . . . . 322.4 Synopsis of Our Proposal . . . . . . . . . . . . . . . . . . . . . . . . 362.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 Reverse k Nearest Neighbor (RkNN) Queries on Road Network 393.1 k Nearest Neighbor (kNN) Queries and Reverse k Nearest Neighbor (RkNN) Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2 Monochromatic RkNN (MRkNN) Queries . . . . . . . . . . . . . . 413.2.1 Basic Method for MRkNN Query . . . . . . . . . . . . . . . 413.2.2 Simple Materialized Path View (SMPV) Structure . . . . . . 433.2.3 MRkNN Query on SMPV Structure . . . . . . . . . . . . . . 453.3 Bichromatic RkNN Queries . . . . . . . . . . . . . . . . . . . . . . 463.3.1 The Concept of BRkNN Query with Voronoi Diagram . . . 483.3.2 Our Approaches for BRkNN Query on Road Network . . . . 493.3.3 Performance Study . . . . . . . . . . . . . . . . . . . . . . . 543.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604 Safe-Region Generation Method for Versatile Continuous Vicinity Queries 614.1 The Approaches for Continuous Queries . . . . . . . . . . . . . . . 614.2 The Basic Principles of Safe-Region Generation . . . . . . . . . . . 644.3 Safe-Region for Vicinity Queries . . . . . . . . . . . . . . . . . . . . 654.4 The Strategy and Architecture of Our Proposed Safe-Region Generation for Vicinity Queries . . . . . . . . . . . . . . . . . . . . . . . . 684.4.1 Distance Range Query . . . . . . . . . . . . . . . . . . . . . 684.4.2 Continuous kNN query on Road Network . . . . . . . . . . . 694.4.3 Typical Principle of Safe-Region Generation . . . . . . . . . 734.4.4 Algorithms for Generating Safe-Region . . . . . . . . . . . . 764.4.5 Variation for Vicinity Queries . . . . . . . . . . . . . . . . . 784.4.6 Determination of the Border of Safe-Region . . . . . . . . . 794.4.7 Improvement on Query Processing Time . . . . . . . . . . . 814.5 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . 874.5.1 Experimental Environment and Settings . . . . . . . . . . . 874.5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . 874.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 975 Continuous Trip Route Planning Queries (CTRPQ) 995.1 Snapshot Trip Route Planning Queries . . . . . . . . . . . . . . . . 1005.1.1 TRPQ Using Progressive Neighbor Exploration (PNE) Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1005.1.2 TRPQ with A* Algorithm . . . . . . . . . . . . . . . . . . . 1025.1.3 Sparse Category First Algorithm for TRPQ . . . . . . . . . 1045.1.4 Euclidean Based TRPQ . . . . . . . . . . . . . . . . . . . . 1065.2 Continuous Trip Route Planning Query . . . . . . . . . . . . . . . . 1085.3 The Strategies to Generate Safe-Region for Continuous TRPQ . . . 1105.3.1 Typical Approaches for Safe-Region Generation . . . . . . . 1125.3.2 The Architecture of Our Proposed Strategies . . . . . . . . . 1145.4 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . 1245.4.1 Experimental Environment and Settings . . . . . . . . . . . 1255.4.2 Performance Evaluation . . . . . . . . . . . . . . . . . . . . 1255.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1426 Conclusion and Future Work 143References 149; 主指導教員 : 大澤裕
• DOI: 10.24561/00018657; https://doi.org/10.24561/00018657
• Persistent ID (NDL): info:ndljp/pid/11346104; https://dl.ndl.go.jp/pid/11346104
• Collection: 障害者向け資料
• Collection (Materials For Handicapped People:1): テキストデータ
• Collection (particular): 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文; https://dl.ndl.go.jp/collections/A00014
• Acquisition Basis: 博士論文（自動収集）
• Date Accepted (W3CDTF): 2019-09-07T00:28:35+09:00
• Date Created (W3CDTF): 2019-07-12
• Format (IMT): application/pdf
• Access Restrictions: 国立国会図書館内限定公開
• Service for the Digitized Contents Transmission Service: 図書館・個人送信対象外
• Availability of remote photoduplication service: 可
• Periodical Title (URI): http://dx.doi.org/10.24561/00018657; http://id.nii.ac.jp/1586/00018657/
• Data Provider (Database): 国立国会図書館 : 国立国会図書館デジタルコレクション; https://dl.ndl.go.jp

Table of Contents

2023-09-05 再収集