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

A Study on Improving Spatial Data Retrieval Using Dimension Reduction Algorithm

穆青雲(Ching-Yun Mu)；龔彬(Pin Kung)；陳建甫(Chien-Fu Chen)；周大鈞(Ta-Chun Chou)

二分搜尋法 ； 大型車隊管理系統 ； 全球定位系統 ； 降維檢索 ； 撿拾補遺搜尋 ； Large Fleet Management System ； Global Positioning System ； Binary Search Method ； Missing Points Search ； Dimension Reduction Retrieval

國土測繪與空間資訊

10卷2期（2022 / 07 / 01）

121 - 132

繁體中文

近年來，空間資訊技術廣泛用於車隊管理，減少定位與坐標轉換誤差，可以避免影響後續運送派遣及行車管理的規劃設計。過去在處理坐標轉換時，常遇到需要同時處理非常大量的批次坐標資料轉換問題，我們採用線性轉換坐標方法，先將經緯度之地理坐標轉換至臺灣常用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.

1. 林老生,王奕鈞(2007)。應用神經網路在地籍資料 TWD67 與 TWD97 坐標轉換之研究。台灣土地研究，10(1)，53-69。
   連結：
2. Mu, C.-Y.,Chou, T.-Y.,Hoang, T.V.,Kung, P.,Fang, Y.-M.,Chen, M.-H.,Yeh, M.-L.(2021).Development of multilayer-based map matching to enhance performance in large truck fleet dispatching.ISPRS Int. J. Geo-Inf.,10(2),79.
3. Ott, L.,Longnecker, M.(2015).An Introduction to Statistical Methods and Data Analysis.Boston, MA, USA:Cengage Learning.
4. Yao, X.,Li, G.(2018).Big spatial vector data management: A review.Big Earth Data,2(1),108-129.
5. Ye, S. J.,Yan, T. L.,Yue, Y. L.,Lin, W. Y.,Li, L.,Yao, X. C.,Mu, Q. Y.,Li, Y. Q.,Zhu, D. H.(2016).Developing a reversible rapid coordinate transformation model for the cylindrical projection.Computers and Geosciences,89,44-56.
6. 史天元(2000)。橫麥卡脫（TM）坐標與經緯度轉換。地籍測量，19(2)，1-10。
7. 李昱德(2017)。國立中興大學土木工程學系。
8. 周大鈞(2019)。逢甲大學都市計畫與空間資訊學系。
9. 洪翎嘉(2018)。國立臺灣師範大學地理學系。
10. 楊濃代(2003)。國立成功大學土木工程學系。
11. 趙忠明,周天穎,嚴泰來(2017).空間資訊技術理論及其應用─理論基礎篇.臺北市:儒林圖書公司.
12. 劉時偉(2007)。元智大學資訊管理學系。
13. 穆青雲(2015)。逢甲大學土木及水利工程博士學位學程。