運用降維演算於空間資料檢索效能改善之研究

近年來，空間資訊技術廣泛用於車隊管理，減少定位與坐標轉換誤差，可以避免影響後續運送派遣及行車管理的規劃設計。過去在處理坐標轉換時，常遇到需要同時處理非常大量的批次坐標資料轉換問題，我們採用線性轉換坐標方法，先將經緯度之地理坐標轉換至臺灣常用TM2度之平面坐標。本研究是以二維坐標資料製作以Y坐標為主索引的降維資料表，再以二分搜尋法對降維資料表進行檢索，以及對未檢索到的區域進行撿拾補遺搜尋，再對所有候選點計算歐式距離，確保找到最近點。利用空間資料製作降維資料表，藉由快速檢索與減少歐式距離的計算量，為大量GPS資料尋找最近的道路，以提升大型車隊管理效率。本研究隨機取樣1,000筆及2,000筆模擬坐標點位，執行20次試驗，比較降維檢索與二維資料表窮舉計算歐式距離的結果差異，經過實證，降維演算明顯的改善運算效能，能解決龐大空間點位資料的檢索問題。

關鍵字

二分搜尋法；大型車隊管理系統；全球定位系統；降維檢索；撿拾補遺搜尋

並列摘要

In recent years, spatial information technology has been widely used in fleet management to reduce positioning and coordinate conversion errors, which can avoid affecting the planning of dispatch and vehicle management. In the past, when dealing with coordinate conversion, we encountered the problem of converting large-scale batch coordinate data at the same time. First, we used the linear conversion method to convert the geographic coordinates to the plane coordinates of TM2 degrees commonly used in Taiwan. In this study, a dimension reduction data table with Y-coordinates as the main index is made from two-dimensional coordinate data, and the dimension reduction data table is retrieved by a binary search method with missing points search, and then the Euclidean distances are calculated for all candidate points to ensure that the nearest point is found. The dimension reduction data table is made by using spatial data, and the nearest road is found for large-scale GPS data by fast retrieval and reducing the computing time using Euclidean distance to improve the efficiency of large fleet management. This study randomly sampled 1,000 and 2,000 simulated coordinate points and performed 20 experiments to compare the difference between the results of the dimension reduction retrieval with exhaustive method in the two-dimensional data table. Through empirical study, the dimension reduction calculation can obviously improve the computational efficiency and solve the retrieval problem of searching huge spatial point data.