Road Network Distance Based Efficient Algorithms Suitable in Location Based Services

• Material Type: 博士論文
• Title: Road Network Distance Based Efficient Algorithms Suitable in Location Based Services
• Author/Editor: Aye, Thida Hlaing
• Author Heading: Aye, Thida Hlaing
• Publication, Distribution, etc.: 埼玉大学大学院理工学研究科
• Publication Date: 2015
• Publication Date (W3CDTF): 2015
• Alternative Title: 位置情報サービスに適した道路網距離に基づく高効率アルゴリズム
• Periodical title: 博士論文（埼玉大学大学院理工学研究科（博士後期課程））
• Degree grantor/type: 埼玉大学
• Date Granted: 2015-03-24
• Date Granted (W3CDTF): 2015-03-24
• Dissertation Number: 甲第981号
• Degree Type: 博士(工学)
• Conferring No. (Dissertation): 甲第981号
• Text Language Code: eng
• Target Audience: 一般
• Note (General): type:text; This thesis describes the studying of efficient algorithms for real-time monitoring, shortest path finding and Reverse k nearest neighbor (R-kNN) query applying on road network distances for Location Based Services (LBS). In recent time, finding shortest path in real road networks is crucial for many applications including location-based services and mobile computing. Since mobility is constantly increasing, we can observe that also an increase in the time dependency of spatial information related to human activities. The role of location-based services is rising as the increasing numbers of users are requesting the location-based information. The main idea of LBS is to provide the service that depends on the positional information which associated with the user, most importantly, the user's current location. The service may also be dependent on other information, such as personal preferences and interests of the user. For example, finding the cheapest hotel within 20 km, where is the nearest gas station, how long it will take to go to Italy restaurant, are some specic user's queries in location-based services. Also a service may inform its users about traffic jams, weather situation, the position of emergency vehicles, hazardous materials or public transportation. Moreover, in other related activities like parcel management, tourism planning, bus routes queries for Urban planning, checking movement of terrorists in emergency situations for crime prevention, etc., require LBS services based on spatial information. For all these requirements, studying on some typical queries like nearest neighbor queries, range queries, spatial join queries, and reverse nearest neighbor queries has been demanded.Various route queries in road networks have gained signicant research interests due to advances in GIS and mobile computing such as car navigation system. The main challenge of processing such a query is how to efficiently monitor the moving object and how to retrieve the route rapidly. In recent time, much work has been conducted on a real time monitoring of moving objects (cars and humans). Some studies adopted to get high accuracy tracking of moving objects with less communication between moving objects and server. However, their studies assumed the moving object is moving in Euclidian space or in fixed route. This thesis proposes a real time monitoring method aiming for both thick client and thin client. We will discuss these two kind of clients detail later. Using the“ frequently used routes ”(FUR) information, we offer high scalability monitoring system with empirical comparisons of the proposed method and the conventional dead-reckoning on road network method.Despite the importance of spatial networks in real-life applications, most of the spatial query methods focus on Euclidean distance, where the distance between two objects is determined solely by their relative position in space. However, in practice, objects can usually move only on a pre-defined set of routes as specied by the real road network (road, railway, river etc.). Thus, the important measure is the network distance, i.e., the length of the shortest trajectory connecting two objects, rather than their Euclidean distance. Only using Euclidean distance on spatial network databases (SNDB) is scarce and too restrictive for emerging applications such as mobile computing and location-based queries.The main difference between using Euclidean distance and road-network distanceis based on their calculation costs. As considering, the Euclidean distance betweentwo arbitrary points can be computed easily, however, in the road-network distance, it takes longer processing time. For example, if the river or mountain liesbetween two points, there is totally difference between the Euclidean distance andthe road-network distance, and the costs of the distance calculation as well. Inthe conventional methods, to promptly acquire the distance between two terminal points for spatial queries in LBS applications, we can use well-known shortestpath finding algorithms, Dijkstra's algorithm and A* algorithm. However, due tothe complexity of some queries, for example, ANN (aggregate nearest neighbor)queries, RNN (reverse nearest neighbor) queries, skyline queries, k-NN queries andseveral kind of TPR (trip planning route) queries, needed efficient algorithm to find the shortest paths between starting point and target point.Dijkstra's algorithm and A* algorithm can be directly applied to these queries,nevertheless these two algorithms take very long processing time and that willcause high calculation cost. Therefore, we propose another efficient shortest path finding algorithm, based on materialized-path-view constructed only on partitionedsubgraphs to compute this road network distance.As a shortest path query is a basic operation in several types of queries, efficient path computation is essential in such kind of queries, for example, k-NN queries, ANN queries, R-kNN queries and trip planning queries. In existing path finding algorithms, Dijkstra's and A* algorithms, require pre-computed all-pair shortest paths and store them on-line. A* algorithm can reduce the path computation but it is not efficient for the re-computation or update of the flat path view for large networks.Other Materialize Path View (MPV) approaches also have been proposed for a shortest path query based on the pre-computed distance table. This method needs O(n2) space when the given number of the nodes is n. For this reason, it is not suitable for the large network as well. Distance materialization methods based on types of roads have been used also in Japan car navigation system. There are several types of roads according to the road classication in Japan, for example, highways or express ways, national roads and residential roads etc. In most existing studies, their methods are suitable for searching long distance trip path and mostly aiming for using express ways. However, in location based services applications, there are requested to search shortest path finding in small area and points of interest (POIs) are normally existed on residential roads, and not on highways or express ways. Therefore, we propose a fast shortest path query strategy suitable for LBS as in small search area and trip is also considered for usual roads.Then, several hierarchical representation methods have been proposed to reduce the amount of data. In HEPV (hierarchical encoded path view) and HiTi graph methods, using hierarchical representation and semi-materialized approach have been proposed to reduce the large amount of data. In this thesis, we propose the shortest path finder with light materialized path view. Our study is closely related with their works, however, their searching assumes the hierarchical structure essentially and we will discuss this difference detail in other session.Using partitioned subgraphs, we study one more efficient algorithm for Reverse k-Nearest Neighbors (R-kNN) query on road network distance. According to our knowledge, the existing methods for R-kNN queries required to find kNN search on every visited node. This causes a large number of node expansions and the processing time is increase simultaneously. Therefore, we propose a fast R-kNN search algorithm that running based on a simple materialized path view (SMPV) structure and we adopted incremental Euclidean restriction strategy for kNN queries which is the main function in R-kNN queries.; Abstract 11 Introduction 91.1 Some Types of Spatial Queries in Location Based Services (LBS) . . 101.2 Incremental Euclidean Restriction Framework of LBS . . . . . . . . 111.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.4 Experimental Environments . . . . . . . . . . . . . . . . . . . . . . 141.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 Related Work 152.1 Shortest Path Finding Algorithms . . . . . . . . . . . . . . . . . . . 152.1.1 Dijkstra's Algorithm . . . . . . . . . . . . . . . . . . . . . . 172.1.2 A* Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 192.1.3 Materialized Path View . . . . . . . . . . . . . . . . . . . . 232.2 Real-time Monitoring for LBS . . . . . . . . . . . . . . . . . . . . . 282.3 RkNN Queries in LBS . . . . . . . . . . . . . . . . . . . . . . . . . 292.4 Spatial Indexing Method . . . . . . . . . . . . . . . . . . . . . . . . 322.4.1 General indexing methods used in spatio-temporal databases 322.4.2 R-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 Real-time Monitoring of Moving Objects Using Frequently Used Routes 373.1 Real-time Monitoring of Moving Objects . . . . . . . . . . . . . . . 373.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.3 Moving Object Monitoring with FUR . . . . . . . . . . . . . . . . . 403.3.1 System conguration . . . . . . . . . . . . . . . . . . . . . . 403.3.2 Frequently used routes . . . . . . . . . . . . . . . . . . . . . 423.3.3 FUR description . . . . . . . . . . . . . . . . . . . . . . . . 433.4 Moving Object Tracking Algorithms for thick client . . . . . . . . . 463.4.1 Moving object tracking for thick client . . . . . . . . . . . . 463.4.2 Moving object side algorithm for thick client . . . . . . . . . 483.4.3 Server side algorithm for thick client . . . . . . . . . . . . . 523.4.4 Experimental results of thick client model . . . . . . . . . . 543.5 Monitoring Algorithms for thin client . . . . . . . . . . . . . . . . . 553.5.1 Basic concepts in thin client model . . . . . . . . . . . . . . 563.5.2 Server side Algorithm for thin client . . . . . . . . . . . . . 573.5.3 Moving object side algorithm for thin client . . . . . . . . . 623.5.4 Minimization of data storage capacity and communication cost 663.6 Experimental results of thin client model . . . . . . . . . . . . . . . 683.6.1 Comparison of communication cost . . . . . . . . . . . . . . 683.6.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694 Shortest Path Finder With Light Materialized Path View for LBS 714.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 724.2 Shortest Path Finder . . . . . . . . . . . . . . . . . . . . . . . . . . 744.2.1 Data structure . . . . . . . . . . . . . . . . . . . . . . . . . 744.2.2 Simple Path Finder Algorithm . . . . . . . . . . . . . . . . . 774.2.3 Distance calculation method inside subgraph . . . . . . . . . 824.3 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . 844.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905 Efficient Reverse kNN Query Algorithm on Road Network Distances Using Partitioned Subgraphs 915.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925.2 Basic method for RkNN search . . . . . . . . . . . . . . . . . . . . 935.3 RkNN query algorithm on partitioned subgraph . . . . . . . . . . . 965.3.1 kNN query using an IER framework . . . . . . . . . . . . . 965.3.2 RkNN query on an SMPV structure . . . . . . . . . . . . . . 975.3.3 Simple Path Finder Algorithm Using in RkNN Query . . . . 1025.3.4 Limitation of referring tables for distance calculation . . . . 1055.4 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . 1065.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136 Conclusion 115Acknowledgement 119; 指導教員 : 大澤裕
• DOI: 10.24561/00010357; https://doi.org/10.24561/00010357
• Persistent ID (NDL): info:ndljp/pid/9921978; https://dl.ndl.go.jp/pid/9921978
• Collection: 障害者向け資料
• Collection (Materials For Handicapped People:1): テキストデータ
• Collection (particular): 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文; https://dl.ndl.go.jp/collections/A00014
• Acquisition Basis: 博士論文（自動収集）
• Date Accepted (W3CDTF): 2016-04-01T14:32:40+09:00
• Date Created (W3CDTF): 2015-12-16
• Format (IMT): application/pdf
• Access Restrictions: 国立国会図書館内限定公開
• Service for the Digitized Contents Transmission Service: 図書館・個人送信対象外
• Availability of remote photoduplication service: 可
• Periodical Title (URI): https://doi.org/10.24561/00010357; http://id.nii.ac.jp/1586/00010357/
• Data Provider (Database): 国立国会図書館 : 国立国会図書館デジタルコレクション; https://dl.ndl.go.jp

Table of Contents

2023-09-05 再収集